TOPICS
Search

Negabinary


The negabinary representation of a number n is its representation in base -2 (i.e., base negative 2). It is therefore given by the coefficients a_na_(n-1)...a_1a_0 in

n=sum_(i=0)a_i(-2)^i
(1)
=...+a_2(-2)^2+a_1(-2)^1+a_0(-2)^0,
(2)

where a_i=0,1.

Conversion of n to negabinary can be done using the Wolfram Language code

  Negabinary[n_Integer] := Module[
    {t = (2/3)(4^Floor[Log[4, Abs[n] + 1] + 2] - 1)},
    IntegerDigits[BitXor[n + t, t], 2]
  ]

due to D. Librik (Szudzik). The bitwise XOR portion is originally due to Schroeppel (1972), who noted that the sequence of bits in n is given by ...01010101.

The following table gives the negabinary representations for the first few integers (OEIS A039724).

nnegabinarynnegabinary
111111111
21101211100
31111311101
41001410010
51011510011
6110101610000
7110111710001
8110001810110
9110011910111
10111102010100

If these numbers are interpreted as binary numbers and converted to decimal, their values are 1, 6, 7, 4, 5, 26, 27, 24, 25, 30, 31, 28, 29, 18, 19, 16, ... (OEIS A005351). The numbers having the same representation in binary and negabinary are members of the Moser-de Bruijn sequence, 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, ... (OEIS A000695).


See also

Base, Binary, Moser-de Bruijn Sequence, Negadecimal

Explore with Wolfram|Alpha

References

Gardner, M. Knotted Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman, p. 101, 1986.Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1998.Schroeppel, R. Item 128 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 24, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/flows.html#item128.Sloane, N. J. A. Sequences A000695/M3259, A005351/M4059, and A039724 in "The On-Line Encyclopedia of Integer Sequences."Szudzik, M. "Programming Challenge: A Mathematica Programming Contest." Wolfram Technology Conference, 1999.

Referenced on Wolfram|Alpha

Negabinary

Cite this as:

Weisstein, Eric W. "Negabinary." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Negabinary.html

Subject classifications