This site is supported by donations to The OEIS Foundation.

Negabinary

From OeisWiki
Jump to: navigation, search

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

256s−128s64s−32s16s−8s4s−2s1s
111011001

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 odd, , and the bit pattern is "11" followed by zeroes e.g., , 11000.

Conversely, for powers of 4 multiplied by −1, with even, , the bit pattern is "11" followed by zeroes, e.g., , 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.