Convert to Base -2
Problem
Given a non-negative integer n, return a string representing its value in base -2 (negative two). The returned string never has leading zeros, except the string "0" itself. In base -2 the place values alternate sign: position 0 is 1, position 1 is -2, position 2 is 4, position 3 is -8, and so on.
n = 6"11010"def base_neg2(n):
if n == 0:
return "0"
digits = []
while n != 0:
remainder = n & 1
digits.append(str(remainder))
n = -(n >> 1)
return "".join(reversed(digits))function baseNeg2(n) {
if (n === 0) return "0";
const digits = [];
while (n !== 0) {
const remainder = n & 1;
digits.push(String(remainder));
n = -(n >> 1);
}
return digits.reverse().join("");
}class Solution {
public String baseNeg2(int n) {
if (n == 0) return "0";
StringBuilder sb = new StringBuilder();
while (n != 0) {
int remainder = n & 1;
sb.append(remainder);
n = -(n >> 1);
}
return sb.reverse().toString();
}
}string baseNeg2(int n) {
if (n == 0) return "0";
string digits;
while (n != 0) {
int remainder = n & 1;
digits += char('0' + remainder);
n = -(n >> 1);
}
reverse(digits.begin(), digits.end());
return digits;
}Explanation
Converting to base -2 works like normal base conversion, but with a twist in how we shrink n each step. We still peel off one digit at a time from the least-significant end.
The next digit is n & 1 (the low bit, either 0 or 1). After recording it, we update n = -(n >> 1). That extra negation is what accounts for the alternating-sign place values 1, -2, 4, -8, ... of a negative base.
We collect the digits least-significant first, then reverse them at the end to read most-significant first. The n == 0 case is handled up front by returning "0".
Example: n = 6. Bit 6 & 1 = 0, then n = -(6>>1) = -3. Bit -3 & 1 = 1, then n = -(-3>>1) = 2. Continuing yields collected digits 0,1,0,1,1, which reversed is "11010".
You can verify: "11010" means 16 - 8 - 2 = 6, matching the input.