Redundant binary representation

An RBR is unlike usual binary numeral systems, including two's complement, which use a single bit for each digit.

There is no single sign bit that tells if a redundantly represented number is positive or negative.

An integer value can be converted back from an RBR using the following formula, where n is the number of digits and dk is the interpreted value of the k-th digit, where k starts at 0 at the rightmost position: The conversion from an RBR to n-bit two's complement can be done in O(log(n)) time using a prefix adder.

Also, for this translation table, flipping all bits (NOT gate) corresponds to finding the additive inverse (multiplication by −1) of the integer represented.

Redundant representations are commonly used inside high-speed arithmetic logic units.

Many hardware multipliers internally use Booth encoding, a redundant binary representation.

More precisely, they take a time proportional to log(n) (where n is the number of digit) compared to a constant-time in two's complement.

It is, however, possible to partially convert only the least-significant portion of a redundantly represented number to non-redundant form.