Description
Given a number N, return a string consisting of “0”s and “1”s that represents its value in base -2 (negative two).
The returned string must have no leading zeroes, unless the string is “0”.
给出数字 N，返回由若干 “0” 和 “1”组成的字符串，该字符串为 N 的负二进制（base -2）表示。
除非字符串就是 “0”，否则返回的字符串中不能含有前导零。
题目链接：https://leetcode.com/problems/convert-to-base-2/
Difficulty: medium
Example 1:
Input: 2
Output: "110"
Explantion: (-2) ^ 2 + (-2) ^ 1 = 2
Example 2:
Input: 3
Output: "111"
Explantion: (-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3
Example 3:
Input: 4
Output: "100"
Explantion: (-2) ^ 2 = 4
Note:
- 0 <= N <= 10^9
分析
- 逐步计算负二进制的末位（逆序），其中每一位的数字是正负交替变化的，用index记录当前位的正负情况，初始为-1；
- 若N是奇数，则当前位是“1”，N加上index，增加当前位的数值；
- 若N是偶数，则当前位是“0”；
- N除以2，index取反；
- 若N不等于0，继续回到第二步；
- 返回记录结果s。
参考代码
class Solution(object):
def baseNeg2(self, N):
index=-1
s=""
if N==0:
return "0"
while(N>0):
if N%2==1:
s="1"+s
N+=index
else:
s="0"+s
N//=2
index*=-1
return s