LeetCode1017.负二进制转换-20230406.md

LeetCode刷题1017.负二进制转换

算法思想： 进制转换

补充 ：正负数的原码、反码、补码：

计算机中存储整数的时候都是使用的补码表示，浮点数有另一套标准，这是计算机组成原理中的内容 应该是 机器数与真值那一章，不管是哪本教材，这是必有的知识点。

[+0]原码=0000 0000，   [-0]原码=1000 0000
[+0]反码=0000 0000，   [-0]反码=1111 1111
[+0]补码=0000 0000，   [-0]补码=0000 0000   


[+1]原码=0000 0001，   [-1]原码=1000 0001
[+1]反码=0000 0001，   [-1]反码=1111 1110
[+1]补码=0000 0001，   [-1]补码=1000 0001  

正数的原码,补码,反码都相同,都等于它本身
负数的补码是:符号位为1,其余各位求反,末位加1
负数的反码是:符号位为1,其余各位求反

当我们想将整数 $n$ 转换为 $x(x>1)$进制时，原理 除基取余，倒序排列：令 $n_0 = n$

• 计算第0位上的数字时，此时 $\left[ n_1 = \lfloor \frac{n_0}{x} \rfloor , n_0 = n_1 \times x + r, 0 \leq r < x \right]$ ;
• 计算第i位上的数字时，此时 $\left[ n_{i+1} = \lfloor \frac{n_i}{x} \rfloor , n_i = n_{i+1} \times x + r_i, 0 \leq r_i < x \right]$ ;
• 按照上述计算方式进行计算，直到满足 $n_i = 0$ 结束。

如果x位负数，只要能确定余数的可能取值，上述方法同样适用

由于负二进制表示中的每一位都是 $0或1$ ,实际上负二进制 的余数可能有 $0、1、-1$ , 但实际表示上不能有负数  ，因此余数只可能是 $0或1$ , 所以将 $n$ 转换为 负二进制，如下：

• $n=0$ 时返回" $0$ " , $n = 1$ 时返回 " $1$ ";
• 如果 $n > 1$ 则使用一个字符串记录余数，将整数 $n$ 转为 负二进制，重复以下操作，直到 $n = 0$
  1. 计算当前 $n$ 的余数，由于当前的余数只能为 $0或1$ ，有符号整数均采用补码表示，最低位奇偶性保持不变，因此可以直接取 $C$ 的最低位即可, 可以直接用 n & 1, 得到最低位的余数。然后将余数拼接到字符串末尾。
  2. 将 $n$ 值减去余数，然后将 $n$ 的值除以 $-2$ 。

上述操作结束之后，将字符串翻转之后得到负二进制数。

class Solution {
public:
    string baseNeg2(int n) {
        if(n == 0 || n == 1){
            return to_string(n);
        }
        string res;
        while (n != 0)
        {
            int remainder = n & 1;
            res.push_back('0' + remainder);//将余数转为字符后，添加到字符串末尾
            n -= remainder;
            n /= -2;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

以 n=2 为例

第一轮
remainder = n & 1 = 2 & 1 = 0
res = "0"
n = n - remainder = 2-0 = 2
n = 2 / -2 = -1 ..... 0

第二轮
remainder = n & 1 = -1 & 1 = 1
res = "01"
n = -1 - 1 = -2
n = -2 / -2 = 1 ..... 0

第三轮
remainder = 1 & 1 = 1
res = ""011"
n = 1-1 = 0
n = 0 / -2 = 0

循环条件不满足，然后，逆转字符串，即为结果

复杂度分析

时间复杂度： $O(log \ n)$ , $n$ 为给定的整数， 对应的「负二进制」表示的长度是 $log \ n$

空间复杂度： $O(1)$