# 6 Pythonic Bit Manipulation Recipes

Posted on August 22, 2020 in Tips & Tricks

# 6 Pythonic Bit Manipulation Recipes

Some reusable python recipes for manipulating bits to perform fast arithmetic. Image credit: https://pxhere.com/en/photo/1458897

### 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 ← creturn 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 ← 0while b ≠ 0    if (b and 1) ≠ 0        c ← c + a    left shift a by 1    right shift b by 1return 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!