6 Pythonic Bit Manipulation Recipes

Some reusable python recipes for manipulating bits to perform fast arithmetic.

1. Double an Integer Using Bit Manipulation

Use the << operator to shift bits one place to the left, thereby doubling an integer.

2. Halve an Integer Using Bit Manipulation

Use the >> operator to shift bits one place to the right, thereby halving an integer.

3. Perform Addition Using Bit Manipulation

This is more complicated. The pseudocode algorithm is:

while a ≠ 0
    c ← b and a
    b ← b xor a
    left shift c by 1
    a ← c
return b

Which, in principle, uses a loop which ends when the first integer reaches 0 — all of its bits have been added to the second integer.

Here we use the & (AND) and the ^ (XOR) operators.

4. Perform Multiplication Using Bit Manipulation

This is also complicated and it requires the previous addition method. Here is the pseudocode algorithm:

c ← 0
while b ≠ 0
    if (b and 1) ≠ 0
        c ← c + a
    left shift a by 1
    right shift b by 1
return c

Which again loops until zero is reached.

5. Perform Subtraction Using Bit Manipulation

This is hairy! First, we need to make the minuend negative using the ~ operator (find it’s complement). Then we find the bitwise AND of the minuend and the subtrahend. Then keep halving the subtrahend until it goes to 0.

Easy, right?

6. Perform Division Using Bit Manipulation

This is also gnarly!

And just like the multiplication and addition examples, division is repeated subtraction. This implementation returns a tuple, the first element contains the quotient and the second element contains the remainder.

I hope you enjoyed this!