题目链接：1017. Convert to Base -2

概述

这个题目要求很简单，就是实现一个十进制到负二进制的转换。

思路

在实现前，先回顾下进制转换的方法：除k取余法

以十进制下的N = 5转为二进制为例：
第一步：5整除2，商为2，余1；
第二步：2整除2，商为1，余0；
第三步：1整除2，商为0，余1；
由于到第三步时商已经等于0，故算法结束。所以，5₁₀=101₂

进一步，我们可以使用位运算来取余数或做除法。

设X对Y求余，Y等于2^N，公式为：X & (2^N - 1) 或 X&(~Y)。

因此，在求余数的时候，我们只要使用N & 1即可。完整的二进制转换代码如下：

/**
 * @param {number} N
 * @return {string}
 */
var base2 = function(N) {
    if(N == 0){
        return "0";
    }
    let remainders = [];
    while(N != 0){
        var x = N & 1;
        remainders.push(x);
        N = N >> 1;
    }
    return remainders.reverse().join("");
};

前面举的例子都是二进制的，那负二进制呢？类似的，我们在转换为负二进制时，只需要将除数改为-2即可。

实现

/**
 * @param {number} N
 * @return {string}
 */
var baseNeg2 = function(N) {
    if(N == 0){
        return "0";
    }
    let remainders = [];
    while(N != 0){
        var x = N & 1;
        remainders.push(x);
        N = -(N >> 1); // 注意这里多了个负号
    }
    return remainders.reverse().join("");
};

题解合集

种星星

LeetCode题解|1017. Convert to Base -2

概述

思路

实现