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

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

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

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

提示：

• 0 <= n <= 10 9

Solutions

class Solution {
    public String baseNeg2(int n) {
        if(n==0) return "0";
        String ans="";
        for(int i=0;n>0;i++){
            ans=(n&1)+ans;
            if((i&1)==1){n+=(n&1)<<1;}
            n>>=1;
        }
        return ans;
    }
}

Ideas

• 十进制转二进制的过程是：十进制数对2取余，把余数放到二进制表示的最高位，然后十进制数除以2，不断重复这个过程，直到十进制数为0.

  参考以上过程，求解十进制数转负二进制时，我们可以将十进制数对-2取余，将余数放到负二进制表示的最高位，然后十进制数除以-2，不断重复这个过程，直到十进制数为0.

  但这么做会出现一些问题：

  （1）十进制数对-2取余，余数有三种情况：-1，0，1，而-1是不能直接放到负二进制表示的最高位的。

  （2）按题目所说，十进制数-1的负二进制表示为11，假设已把-1对-2取余的余数放到负二进制表示的最高位，那么此时应将十进制数-1除以-2，理论上应得到1，这样才能让最终的负二进制为11，但-1/(-2)=0。

  针对问题（1），我的解决方案是将三种情况并为两种，也即余数为0和1，也就是说，只需要判断此时的十进制数是否为奇数，若是，则余数为1，否则余数为0.

  针对问题（2），实际上出现问题（2）是因为十进制数表示为负二进制数并不是同增同减的关系，简单来说，十进制数加减1，并不一定会让其对应的负二进制数加减1，若在计算时直接将十进制数除以（-2），可能会吞没一些信息，导致计算不准，我的解决方案是，每次将十进制数除以（-2）之前，都把已确定的信息去除，让下一轮的信息是正确信息，比如，已确定-3在当前轮要在负二进制数的最高位上放1，那就将-3减1，使其变为-4，这样就能保证除以（-2）之后为2，而不是变为1。