Redundant Binary Representation - Logical Operations

Logical Operations

Implementing logical operations in a RBR using digital logic is more complicated than in usual representations. For example, the expected result of the bitwise AND operation on a pair of representations of 1 is expected to have value 1 in usual representations. Since there are many ways to represent 1 in a RBR, it is not possible to simply use the basic logic gate AND between every digit. The same problem apply to the OR and XOR operations. While it is possible to do bitwise operations directly on the underlying bits inside a RBR, it is not clear that this is a meaningful operation. Assuming one wants the result to represent the same integer value as if the operation had been carried out using a standard non-redundant binary representation, it is necessary to convert the two operands first to non-redundant representations. Consequently, logical operations are slower in a RBR. 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.