Negabinary

This article needs more work.

Please help by expanding it!

Negabinary is like the binary numeral system with the crucial difference that powers of −2 (see A122803) are used rather than 2.

For example, the negabinary representation of 201 is

$(-2)^{8}$	$(-2)^{7}$	$(-2)^{6}$	$(-2)^{5}$	$(-2)^{4}$	$(-2)^{3}$	$(-2)^{2}$	$(-2)^{1}$	$(-2)^{0}$
256s	−128s	64s	−32s	16s	−8s	4s	−2s	1s
1	1	1	0	1	1	0	0	1

We verify that 256 − 128 + 64 + 16 − 8 + 1 = 201.

The powers of 4 have the same representation in negabinary that they have in binary (indeed we can say this of all numbers that are the sum of distinct powers of 4, see A000695). The other powers of 2 are represented in negabinary by the next higher power of 4 minus that power of 2, thus, with $n$ odd, $2^{n}=(-2)^{n+1}+(-2)^{n}$, and the bit pattern is "11" followed by $n$ zeroes e.g., $8=(-2)^{4}+(-2)^{3}=16-8$, 11000.

Conversely, for powers of 4 multiplied by −1, with $n$ even, $-(2^{n})=(-2)^{n+1}+(-2)^{n}$, the bit pattern is "11" followed by $n$ zeroes, e.g., $-16=(-2)^{5}+(-2)^{4}=-32+16$, 110000.

Negabinary offers some theoretical advantages over binary, such as the unambiguous representation of negative numbers. The following chart shows the representation of –1 in a few different combinations of systems and data widths:

	Negabinary	Absolute value in binary prefixed by sign bit	Two's complement in binary
Byte	00000011	10000001	11111111
Word	0000000000000011	1000000000000001	1111111111111111
Double word	00000000000000000000000000000011	10000000000000000000000000000001	11111111111111111111111111111111

When we cast these to unsigned data types of appropriate width in binary and view the result in decimal, the lack of ambiguity in negabinary becomes quite clear:

	Negabinary	Absolute value in binary prefixed by sign bit	Two's complement in binary
Byte	3	129	255
Word	3	32769	65535
Double word	3	2147483649	4294967295

Binary of course has the practical advantage of half a century of research and development.

Reinterpreting the negabinary representations of positive integers as binary gives us the sequence A005351, while doing the same for negative integers gives us A005352. The number 0 in negabinary is of course 0. A053985 gives the binary representations of the non-negative integers reinterpreted as negabinary.