janmr blog

Bitwise Operators and Negative Numbers

When representing integers using a fixed number of bits, negative numbers are typically represented using two's complement. If using bit numbers, the two's complement of a number with is . But what do you do if you want to work with unbounded/multiple-precision integers? Fixing and letting the number of bits go to infinity, you will notice that increasing by one simply adds a 1 at the left. For instance,

  •    (with )
  •    (with )
  •    (with )
  •    (with )

(This can be made more rigorous using 2-adic numbers). Conversely, every binary number with infinitely many 1s to the left corresponds to a negative integer.

Notice the important special case . If denotes bitwise not of , where each bit is flipped from to and vice versa, we observe that

from which we have the important identity

This makes bitwise not equivalent to a simple subtraction. Notice how bitwise not turns a non-negative integer into a negative integer and vice versa.

Let us turn to general bitwise operators. Consider a function that maps two bits to a single bit. Given such a function and two non-negative integers, we can apply the function to the zeroth bit of both numbers to obtain the zeroth bit of the result, then apply the function to the first bit of both numbers to obtain the first bit of the result, and so forth. In this way, any binary bit-operator can be extended to work on any non-negative integer (and as we shall see, any integer). There are 16 possible binary bit-operators:

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

The first column of the table enumerates the functions from 0 to 15 (such that the binary representation of each number corresponds to the outputs). We see that exactly the functions 0–7 map to , meaning that only these functions will map two non-negative integers to a non-negative integer.

The second column shows expressions for the functions using the well-known operators bitwise and, , bitwise or (inclusive or), , bitwise xor (exclusive or), , and bitwise not, . The table simultaneously define these operators.

We can now formulate the goal of this article: Using only the bitwise operators that map non-negative integers to non-negative integers, together with usual integer arithmetic, how can we implement all 16 functions? The approach is quite simple: Use bitwise not to transform any negative integer into a non-negative integer, apply one of the functions 0–7, and then possibly apply bitwise not again to obtain the result.

Before proceeding, we need some fundamental identities. First, symmetry:

Then, De Morgan's laws:

Finally some useful rules for exlusive or:

All of these are easily proved since they (by definition) operate bitwise. This means that you only have to consider one-bit numbers, which means only four different cases to check.

The only non-trivial operators among the functions 0–7 are , , , and . We will use the notation . Note how is not symmetric. The only non-trivial operators among the functions 8–15 are , , , and . Considering these eight cases, along with whether and are negative or not, we get the following table:

, , , ,

Here, we have used only the identities shown earlier. Of course, we need to convert each bitwise not into a subtraction to complete the task. For instance, with , we have

This way, the bitwise and-operation is being applied to non-negative numbers and we see that the result is always negative.

We can now, with assistance from the table above, apply any of the 16 binary bitwise operators to any pair of integers, without restricting ourselves to working with a fixed number of bits.

For further reading related to the binary representation of numbers, I recommend The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques and Binary Decision Diagrams by Donald E. Knuth and Hacker's Delight by Henry S. Warren, Jr.