JZX轻语：简

LeetCode 1017 - 负二进制转换

发表于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

题目链接：https://leetcode.cn/problems/convert-to-base-2/