Could you provide a convincing explanation, or a mathematical proof, to why the following function calculates the negabinary representation of a given number?
function quickNegabinary(number) {
var mask = 0xAAAAAAAA;
return ((number + mask) ^ mask).toString(2);
}
Negabinary notation
Negabinary notation uses a radix of -2. This means that, as in every number system with a negative base, every other bit has a negative value:
position: ... 7 6 5 4 3 2 1 0
binary: ... 128 64 32 16 8 4 2 1
negabinary: ... -128 +64 -32 +16 -8 +4 -2 +1
Quick conversion method
The quick binary→negabinary conversion method adds and then xor's a number with 0xAAAAAAAA, or binary ...10101010 (a mask which indicates the odd positions which have a negative value in negabinary notation), e.g. for the value 82:
binary: 01010010 = 82 (binary: 64 + 16 + 2)
mask: 10101010 = 170
bin+mask 11111100 = 252
(bin+mask) XOR mask: 01010110 = 82 (negabinary: 64 + 16 + 4 - 2)
How it works: one set bit
It is easy to see how the method works, if you take the example of a number with only one set bit in binary notation. If the set bit is at an even position, nothing changes:
binary: 00000100 = 4 (binary: 4)
mask: 10101010 = 170
bin+mask 10101110 = 174
(bin+mask) XOR mask: 00000100 = 4 (negabinary: 4)
However, if the set bit is at an odd position:
binary: 00001000 = 8 (binary: 8)
mask: 10101010 = 170
bin+mask 10110010 = 178
(bin+mask) XOR mask: 00011000 = 8 (negabinary: 16 - 8)
the set bit is shifted left (by adding 1 to it), and is then combined with the negative of its original value (by XOR-ing with the mask), so that a bit with value 2n is replaced by 2n+1 - 2n.
So you can think of the quick conversion method simply as: "replace every 2 by 4 - 2, every 8 by 16 - 8, every 32 by 64 - 32, and so on".
How it works: multiple set bits
When converting a number with several set bits, the results of converting a number with one set bit, as described above, can simply be added together. Combining e.g. the single-set-bit examples of 4 and 8 (see above) to make 12:
binary: 00001100 = 12 (binary: 8 + 4)
mask: 10101010 = 170
bin+mask 10110110 = 182
(bin+mask) XOR mask: 00011100 = 12 (negabinary: 16 - 8 + 4)
Or, for a more complicated example, where some digits are carried:
binary: 00111110 = 62 (binary: 32 + 16 + 8 + 4 + 2)
mask: 10101010 = 170
bin+mask 11101000 = 232
(bin+mask) XOR mask: 01000010 = 62 (negabinary: 64 - 2)
What happens here is that in the sum which describes the binary number:
32 + 16 + 8 + 4 + 2
32 is converted into 64 - 32, 8 into 16 - 8 and 2 into 4 - 2, so that the sum becomes:
64 - 32 + 16 + 16 - 8 + 4 + 4 - 2
where the two 16's are then carried to become a 32 and the two 4's are carried to become an 8:
64 - 32 + 32 - 8 + 8 - 2
and the -32 and +32 cancel each other out, and the -8 and +8 cancel each other out, to give:
64 - 2
Or, using negabinary arithmetic:
+1 +1 (carry)
0 1 -1 0 0 0 0 0 = 32 (negabinary: 64 - 32)
0 0 0 1 0 0 0 0 = 16 (negabinary: 16)
0 0 0 1 -1 0 0 0 = 8 (negabinary: 16 - 8)
0 0 0 0 0 1 0 0 = 4 (negabinary: 4)
+ 0 0 0 0 0 1 -1 0 = 2 (negabinary: 4 - 2)
----------------------
= 0 1 0 0 0 0 -1 0 = 62 (negabinary: 64 - 2)
Negative values
The quick conversion method also works for negative numbers in two's complement notation, e.g.:
binary: 11011010 = -38 (two's complement)
mask: 10101010 = -86 (two's complement)
bin+mask 10000100 = -124 (two's complement)
(bin+mask) XOR mask: 00101110 = -38 (negabinary: -32 - 8 + 4 - 2)
binary: 11111111 11011010 = -38 (two's complement)
mask: 10101010 10101010 = -21846 (two's complement)
bin+mask 10101010 10000100 = -21884 (two's complement)
(bin+mask) XOR mask: 00000000 00101110 = -38 (negabinary: -32 - 8 + 4 - 2)
Range and overflow
The range of a negabinary number with n bits (where n is an even number) is:
-2/3 × (2n-1) → 1/3 × (2n-1)
Or, for common bit depths:
8-bit: -170 ~ 85
16-bit: -43,690 ~ 21,845
32-bit: -2,863,311,530 ~ 1,431,655,765
64-bit: -1.23e+19 ~ 6.15e+18
80-bit: -8.06e+23 ~ 4.03e+23
This range is lower than both signed and unsigned standard integer representations with the same bit depth, so both signed and unsigned integers can be too large to be represented in negabinary notation with the same bit depth.
Although the quick conversion method can seemingly run into overflow for negative values below -1/6 × (2n-4), the result of the conversion is still correct:
binary: 11010011 = -45 (two's complement)
mask: 10101010 = -86 (two's complement)
bin+mask 11111111 01111101 = -131 (two's complement)
overflow truncated: 01111101 = 125 (two's complement)
(bin+mask) XOR mask: 11010111 = -45 (negabinary: -128 + 64 + 16 + 4 - 2 + 1)
binary: 11111111 11010011 = -45 (two's complement)
mask: 10101010 10101010 = -21846 (two's complement)
bin+mask 10101010 01111101 = -21891 (two's complement)
(bin+mask) XOR mask: 00000000 11010111 = -45 (negabinary: -128 + 64 + 16 + 4 - 2 + 1)
Reverse function
Negabinary numbers can be converted back to standard integer values by reversing the addition and XOR-ing with the mask, e.g.:
uint64_t negabinary(int64_t bin) {
if (bin > 0x5555555555555555) throw std::overflow_error("value out of range");
const uint64_t mask = 0xAAAAAAAAAAAAAAAA;
return (mask + bin) ^ mask;
}
int64_t revnegabin(uint64_t neg) {
// const uint64_t even = 0x2AAAAAAAAAAAAAAA, odd = 0x5555555555555555;
// if ((neg & even) > (neg & odd)) throw std::overflow_error("value out of range");
const uint64_t mask = 0xAAAAAAAAAAAAAAAA;
return (mask ^ neg) - mask;
}
(If the reverse function is only called on negabinary numbers created by the negabinary() function, there is no risk of overflow. However, 64-bit negabinary numbers from other sources could have a value below the int64_t range, so then overflow checking becomes necessary.)
"0xAAAAAAAA" is one of those magic numbers which contains a sequence of 10(binary ) pattern. This is used as a mask because you are performing a bitwise XOR operation. When you add the number to this mask and do an XOR, the result would be affected only by those bits provided by the number, the rest would be 0 in the result. [Since XOR of two same bits is 0]. Finally, toString(2) is converting the result into binary
Example: ->Consider 3 is your number. Add 3 to 2863311530 [which is the decimal representation of 0xAAAAAAAA]. ->XOR the sum(mask + 3) with 0xAAAAAAAA, which is ....101010101101 ^ ....10101010. This gives you 111 (since last 3 corresponding bits in mask and the sum are different) ->Convert 111 to binary, which is 7
© 2022 - 2024 — McMap. All rights reserved.