The challenge
In this challenge you must convert integers numbers from and to a negative-base binary system.
Negative-base systems can accommodate all the same numbers as standard place-value systems, but both positive and negative numbers are represented without the use of a minus sign (or, in computer representation, a sign bit); this advantage is countered by an increased complexity of arithmetic operations.
To help understand, the first eight digits (in decimal) of the Base(-2) system is:
[1, -2, 4, -8, 16, -32, 64, -128]
Example conversions:
Decimal, negabinary
6, '11010'
-6, '1110'
4, '100'
18, '10110'
-11, '110101'
The solution in Java code
Option 1:
public class Solution {
public static String intToNegabinary(int i) {
return Integer.toBinaryString((i+0xAAAAAAAA)^0xAAAAAAAA);
}
public static int negabinaryToInt(String s) {
return s.chars().map(i->i-'0').reduce(0,(a,v)->v-2*a);
}
}
Option 2:
public class Solution {
public static String intToNegabinary(int i) {
var sb = new StringBuilder();
while (i != 0) {
int remainder = Math.abs(i) % 2;
sb.append(remainder);
if (i < 0 && remainder > 0) i--;
i /= -2;
}
var result = sb.reverse().toString();
return result.isEmpty() ? "0" : result;
}
public static int negabinaryToInt(String s) {
var strReversed = new StringBuilder(s).reverse();
int result = 0;
for (int i = 0; i < strReversed.length(); i++)
if (strReversed.charAt(i) == '1')
result += Math.pow(-2, i);
return result;
}
}
Option 3:
public class Solution {
public static String intToNegabinary(int i) {
return Integer.toUnsignedString(toNegabinary(i), 2);
}
public static int negabinaryToInt(String s) {
return fromNegabinary(Integer.parseUnsignedInt(s, 2));
}
public static int toNegabinary(int i) {
return (i + NEGATIVE_DIGITS) ^ NEGATIVE_DIGITS;
}
public static int fromNegabinary(int i) {
return (i ^ NEGATIVE_DIGITS) - NEGATIVE_DIGITS;
}
private static final int NEGATIVE_DIGITS = 0xAAAAAAAA;
}
Test cases to validate our solution
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class SolutionTest {
@Test
public void testIntToNegabinary() {
assertEquals("11010", Solution.intToNegabinary(6));
assertEquals("1110", Solution.intToNegabinary(-6));
}
@Test
public void testNegabinaryToInt() {
assertEquals(6, Solution.negabinaryToInt("11010"));
assertEquals(-6, Solution.negabinaryToInt("1110"));
}
}