# 6 Pythonic Bit Manipulation Recipes

Posted on August 22, 2020 in Tips & Tricks

# 6 Pythonic Bit Manipulation Recipes

### 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!