发表于 2024.04.28

• 首先对数字按正常的二进制展开，然后如果某个二进制位在新的表示法中属于负数，则需要”往前借一位”，比如，第3个比特在新的表示法中是-8，如果需要表示8，则需要利用第4个比特，即8 = -8 + 16，然后再进一步处理16之后的数字(前面的处理结果已经固定了，无后效)。如果某一位比特不仅原来的表示法需要使用到，且前面的数字又存在进位，则需要合并、往后面继续进位，如24 = 8 + 16 = -8 + 16 + 16 = -8 + 32，后面再继续处理32 = -32 + 64，最终结果为24 = -8 - 32 + 64。因此，最终的思路为从小往大处理比特位，如果某个比特按正常的表示法需要使用到，则进一步判断在新的表示法中是否为负数，如果是，则置为1向左边的比特位进位；如果某个比特不仅原表示法需要使用到，且存在进位，则置为0继续进位。

  class Solution:
      def baseNeg2(self, n: int) -> str:
          if n == 0:
              return '0'
          bit = 0  # 当前处理的比特
          advance = False  # 是否有进位
          q = collections.deque()
          while n or advance:
              if n & 1:  # 原表示法需要使用到
                  if not advance:  # 如果不存在进位
                      q.appendleft('1')  # 无论是否为负数, 该位均需要置为1
                      if bit % 2:  # 如果该位为负数, 则需要进一位, 即 8 = -8 + 16
                          advance = True
  
                  else:  # 前面有进位, 合并后继续进位(如24 = 8 + 16 = -8 + 16 + 16 = -8 + 32...), 本bit设置为0
                      q.appendleft('0')
              elif advance:  # 如果该位为0, 但有进位, 则该位需要使用到
                  advance = False
                  q.appendleft('1')
                  if bit % 2:
                      advance = True
              else:
                  q.appendleft('0')
              n >>= 1
              bit += 1
          return ''.join(q)

• LC 题目链接