[每日一题] 1017.负二进制转换

2024 年 04 月 28 日

93 次浏览

465字数

> https://leetcode.cn/problems/convert-to-base-2/description/?envType=daily-question&envId=2024-04-11

### 进位

负二进制下偶数位的含义和二进制的一样，而奇数位的含义则变为原来的相反数。因此要获得原本奇数位的数只需要往上进一位即可。比如 $2$ 的二进制表示为 $010$ ，而在负二进制下 $010$ 表示的数为 $-2$ ，往上进一位 $110$ ，得到 $4 - 2 = 2$ 。

```c++
class Solution {
public:
    std::string baseNeg2(int n) {
        if (n == 0)
            return "0";

const int MAX_SIZE = 40;
        std::bitset<MAX_SIZE> bin(n);
        for (int i = 1, j; i <= MAX_SIZE; i += 2) {
            if (bin[i]) {
                j = i + 1;
                while (bin[j])
                    bin.reset(j++);
                bin.set(j);
            }
        }
        std::cout << std::endl;

std::string res = bin.to_string();
        res.erase(0, res.find_first_not_of('0'));
        return res;
    }
};
```

- 时间复杂度 $O(C)$ ，其中 $C = 40$ 。int 型为 32 位，所以理论上 $C$ 取 32 即可，这里是留了点冗余。
- 空间复杂度 $O(C)$ 。这里用了 `bitmap` 优化空间存储。

### 进制转换

我们平时计算 $k$ 进制的时候，先通过 `n % k` 求出当前位的值，然后再执行 `n = n / k` ，重复上面的过程直到 `n == 0` 。当 $k < 0$ 时，这种方法也可以成立。

需要注意的是 `n = n / k` 是直接截断小数部分，而我们想要的是向下取整，两者是有区别的。

```c++
class Solution {
public:
    std::string baseNeg2(int n) {
        if (n == 0 || n == 1)
            return std::to_string(n);

std::string res;
        while (n != 0) {
            int remainder = n & 1;
            res.push_back('0' + remainder);
            n -= remainder;
            n /= -2;
        }

std::reverse(res.begin(), res.end());
        return res;
    }
};
```

- 时间复杂度 $O(logn)$ 。
- 空间复杂度 $O(1)$ 。除了返回值不需要额外的辅助空间。

最后修改：2024 年 05 月 06 日