题目大意：
负二进制转换
给出数字 N，返回由若干 "0" 和 "1"组成的字符串，该字符串为 N 的负二进制（base -2）表示。
除非字符串就是 "0"，否则返回的字符串中不能含有前导零。
示例 1：
输入：2 输出："110" 解释：(-2) ^ 2 + (-2) ^ 1 = 2
示例 2：
输入：3 输出："111" 解释：(-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3
示例 3：
输入：4 输出："100" 解释：(-2) ^ 2 = 4
提示：
0 <= N <= 10^9
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1017
解题思路分析：
这是一道2进制的题目。 对于普通的2进制数，每一位上的1都相当于十进制中的2的n次方（n为当前位）。例如：
1 // 2的0次方 相当于10进制的1 10 // 2的1次方 相当于10进制的2 100 // 2的2次方 相当于10进制的4 111 // 111 = 1 + 10 + 100 = 1 + 2 + 4 = 7;
不过本题有些特殊，这个2进制数的每一位代表的并不是2的n次方，而是-2的n次方 ，这时需要注意的地方。那么如何将10进制数转化为负二进制数呢？利用位运算是最简单的解决办法，我们可以将N看做是一个正常的二进制数，每次取出最低位加入到返回结果中，接下来很关键，为了取二进制下一位，我们需要将N向右平移一位，这时最低位就变成了原先的下一位。不过，本题是负二进制数，因此，在向右平移一位之后，我们应该将N乘以-1。
简单啰嗦一下位运算的计算方法。
一，如何取最低位的数字。比如N = 2，对应的负二进制为：110。取最低位（最右一位）的方法是利用与（＆）运算。 与运算的原则是1与1为1，1与0为0。
110 ＆ 1 = 0; // 与运算两数位数不同是，长度短的前补零。即110 ＆ 001 = 000 = 0 111 ＆ 1 = 1; // 111 ＆ 001 = 001 = 1
二，如何向右平移一位。还比如 N = 2，对应的负二进制为：110。 此时我们已经取到了最低位0，接下来要取高一位的1，我们可以利用>>将数字向右平移。
110 >> 1 = 11 // >> 1 表示向右平移1位，即删除最低一位 110 >> 2 = 1 // >> 2 表示向右平移2位 110 >> 3 = 0 // >> 3 表示向右平移3位
看下完整代码：
public String baseNeg2(int N) {
if(N==0) return "0"; // 如果N为0，直接返回0
String res = ""; // 定义返回结果
while(N!=0){ // 当N不为0
int n = N & 1; // 取得N的最低位数字
res = n +res; // 将最低位加入到返回结果
N = -(N>>1); // 将N向右平移一位，同时取负
}
return res;
} 本解法运行时间为1ms。
Runtime: 1 ms, faster than 95.72% of Java online submissions for Convert to Base -2.
Memory Usage: 34.5 MB, less than 100.00% of Java online submissions for Convert to Base -2.
如果大家对负二进制的题比较感兴趣，可看下，leetcode 1073. Adding Two Negabinary Numbers 这道题目，如果没有思路，请参考我之前的文章 LEETCODE 1073. Adding Two Negabinary Numbers 解题思路分析
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1017-convert-to-base-2-解题思路分析/