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
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).
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, NegadecimalExplore with Wolfram|Alpha
More things to try:
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
NegabinaryCite this as:
Weisstein, Eric W. "Negabinary." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Negabinary.html