6 Pythonic Bit Manipulation Recipes
Some reusable python recipes for manipulating bits to perform fast arithmetic.
1. Double an Integer Using Bit Manipulation
<< operator to shift bits one place to the
left, thereby doubling an integer.
2. Halve an Integer Using Bit Manipulation
>> 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
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
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.
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!