negabinary

Negabinary is a base -2 numeral system that uses only the digits 0 and 1. In this system, numbers are represented as a sum of digits multiplied by powers of -2; a typical representation is written as a_k a_{k-1} ... a_1 a_0 with value sum a_i (-2)^i. Unlike standard binary, the base is negative, which allows negative as well as positive integers to be represented without a separate sign.

Every integer has a unique negabinary representation, and zero is written as 0. Leading zeros are not used.

Converting from decimal to negabinary: repeatedly divide by -2, recording remainders 0 or 1. In practice compute r = n mod 2 (0 or 1) and set n = (n - r)/(-2). Continue until n becomes 0. Example: decimal 2 -> 110 in negabinary; -5 -> 1111 in negabinary.

Converting from negabinary to decimal is the reverse operation: sum the bits times powers of -2.

Arithmetic: addition and subtraction can be performed similarly to binary, with carries determined to keep digits 0 or 1; the negative base means carries may propagate in different directions, but standard algorithms exist for negabinary addition and subtraction.

Context: Negabinary is a simple example of a negative-base numeral system, illustrating that a positional notation can express all integers without a sign bit. It has mainly theoretical interest and occasional applications in digital logic and algorithm design.