Add two negabinary integers
About Negabinary
Negabinary means base negative two (-2). That is, the $n$th place value is determined by $(-2)^n$.
Negabinary numbers can be evaluated just like any other base system. For example, we can parse the numbers 101, 110, and 1010 as follows:
| -8 | 4 | -2 | 1 | value |
|---|---|---|---|---|
| 1 | 0 | 1 | 5 | |
| 1 | 1 | 0 | 2 | |
| 1 | 0 | 1 | 0 | -10 |
Challenge
Given two negabinary integers, output the sum of them in negabinary.
You may take inputs in any format that makes sense. However, the output of the function/program must be in the same format as the input
The following ungolfed example takes in two 0-indexed arrays, with the nth entry being the nth place of each number.
function addNegabinary(first, second) {
let carry = 0;
let result = [];
let place = 0;
while(place < first.length || place < second.length || carry) {
let num = (first[place] || 0) + (second[place] || 0) + carry;
let bit;
switch (num) {
case -1: bit = 1; carry = 1; break;
case 0: bit = 0; carry = 0; break;
case 1: bit = 1; carry = 0; break;
case 2: bit = 0; carry = -1; break;
case 3: bit = 1; carry = -1; break;
}
result.push(bit);
place++;
}
return result;
}
Some test cases
1 + 0 = 1
1 + 1 = 110 // 1 + 1 = 2
1 + 110 = 111 // 1 + 2 = 3
10 + 1 = 11 // -2 + 1 = -1
10 + 1011 = 110101 // -2 + -9 = -11
1010101 + 1110100 = 110011001
Japt, 8 bytes Input as an a …
3y ago
[Jelly], 6 bytes ḅSbɗ-2 …
3y ago
[Ruby], 75 bytes -> …
3y ago
3 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
Japt, 8 bytes
Input as an array of negabinary digit arrays, output as a negabinary digit array.
xì2n)ì2n
Try it or run all test cases (headers & footers convert to & from digit arrays)
xì2n)ì2n :Implicit input of 2D digit array
x :Reduce by addition after
ì : Converting each from base
2n : -2
) :End reduce
ì2n :Convert to base -2 digit array
0 comment threads
Jelly, 6 bytes
ḅSbɗ-2
Takes input and output as a pair of lists of digits. The Footer converts to and from.
Jelly's generalised base conversion works for all integer bases, and allows converting from complex bases.
How it works
ḅSbɗ-2 - Main link. Takes [a, b] on the left
ɗ-2 - Last 3 links as a dyad f([a,b], -2):
ḅ - Convert from base -2
S - Sum
b - Convert to base -2
0 comment threads
Ruby, 75 bytes
->t,u{g=->a{a.reduce{-2*_1+_2}};('%b'%(g[t]+g[u]+(y=43690)^y)).to_i.digits}
Uses latest ruby features, so tio link will look different.
Takes two digit arrays, and returns an array which represents the negabinary integer.
Borrows from a conversion technique used here.
0 comment threads
0 comment threads