题目

给你一个整数 n ，以二进制字符串的形式返回该整数的 负二进制（base -2） 表示。

注意，除非字符串就是 "0"，否则返回的字符串中不能含有前导零。

示例 1：

输入：n = 2
输出：”110”
解释：(-2)^2^ + (-2)^1^ = 2

示例 2：

输入：n = 3
输出：”111”
解释：(-2)^2^ + (-2)^1^ + (-2)^0^ = 3

示例 3：

输入：n = 4
输出：”100”
解释：(-2)^2^ = 4

提示：

  • 0 <= n <= 109

题解

10进制中314写成314是3 * 10^2^ + 1 * 10^1^ + 4 * 10^0^。所以2的二进制是10，1 * 2^1^ + 0 * 2^0^, 2的负二进制是110， 1*(-2)^2^ + 1*(-2)^1^ + 0*(-2)^0^。
十进制转二进制方法是 除2取余数逆序排序。
bedi

被除数 除数 商 余数
2 2 1 0
1 2 0 1

2的负二进制为(-1)0，其中一位是负数，被除数=除数*商+余数

被除数 除数 商 余数
2 -2 -1 0
-1 -2 0 -1

进制转换

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def baseNeg2(self, n: int) -> str:
        if n == 0 or n == 1:
            return str(n)
        res = []
        while n:
            remainder = n & 1 
            res.append(str(remainder))
            n -= remainder
            n //= -2
        return ''.join(res[::-1])

数学

1
2
3
4
5
6
7
8
9
10
class Solution:
    def baseNeg2(self, n: int) -> str:
        val = 0x55555555 ^ (0x55555555 - n)
        if val == 0:
            return "0"
        res = []
        while val:
            res.append(str(val & 1))
            val >>= 1
        return ''.join(res[::-1])

模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def baseNeg2(self, n: int) -> str:
        if n == 0:
            return "0"

        bits = [0] * 32
        for i in range(32):
            if n == 0:
                break
            if n & 1:
                bits[i] += 1
                if i & 1:
                    bits[i + 1] += 1
            n >>= 1

        carry = 0
        for i in range(32):
            val = carry + bits[i]
            bits[i] = val & 1
            carry = (val - bits[i]) // -2

        pos = 31
        res = ""
        while pos >= 0 and bits[pos] == 0:
            pos -= 1
        while pos >= 0:
            res += str(bits[pos])
            pos -= 1
        return res