algorithm - Calculating the negabinary representation of a given number without loops

Question

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);
}

Answer 1

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 2ⁿ is replaced by 2ⁿ⁺¹ - 2ⁿ.

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 × (2ⁿ-1) → 1/3 × (2ⁿ-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 × (2ⁿ-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.)