# Bit Manipulation Tricks

If programming is a craft, then it is best learned by imitation and lots of practice. These bit manipulation techniques are little programming tricks that manipulate integers in a smart and efficient manner like a master craftsman.

Please note that, If you are not familiar with binary system and/or bitwise operators, I recommend that you read Binary Computation and Bitwise Operators post first.

## Check if the integer is even or odd

This is a well known bit trick among embedded systems programmers.

``````def even_or_odd_checker(num: int) -> str:
if (num & 1) == 0:
return f"{num} is EVEN"
else:
return f"{num} is ODD"
``````

An integer is odd if and only if the least significant bit (LSB) is 1. By using AND (`&`) operator between given number (num) and 1, we are eliminating all bits other than LSB. After this operation, if the result is 0, that means LSB is 0 and the number is even. Otherwise, it is odd.

Let’s try it with 54;

``````   0011 0110  (binary of 54)
0000 0001  (binary of 1)
& -----------
0000 0000  --> 0, so 54 is EVEN
``````

And let’s try it with an odd number, 37;

``````   0010 0101  (binary of 37)
0000 0001  (binary of 1)
& -----------
0000 0001  --> 1, so 37 is ODD
``````

## Test if the n-th bit is set

This bit trick uses the same logic with the previous one to check if n-th bit is set or not.

``````def check_nth_bit(num, n: int) -> str:
if num & (1 << n):
return f"{num} = {bin(num)} (binary) and {n}th bit is set"
else:
return f"{num} = {bin(num)} (binary) and {n}th bit is NOT set"
``````

Left shift (`<<`) finds the correct position of the bit which we want to test

``````1         0000 0001
1 << 1    0000 0010
1 << 2    0000 0100
1 << 3    0000 1000
1 << 4    0001 0000
1 << 5    0010 0000
and so on...
``````

If the result after this AND (`&`) operation is 0, then checked bit is 0, otherwise that bit was set.

Let’s try with 175 and check if 5th bit is set;

``````   1010 1111  (binary of 175)
0010 0000  (1 << 5)
& -----------
0010 0000 --> 5th bit is set
``````

## Set the n-th bit if it is not already set

We are going to use left shift trick that we learn previously.

``````def set_nth_bit(num, n: int) -> str:
if num & (1 << n):
return f"{num} (decimal) = {bin(num)} (binary) and {n}th bit is ALREADY set"
else:
set_nth_bit_result = num | (1 << n)
return f"{n}th bit is set ({bin(num)} is changed to {bin(set_nth_bit_result)})"
``````

Result of `num | (1 << n)` operation sets the targeted bit. Because using OR (`|`) operator on any value with 0 leaves the value the same but if we use OR (`|`) operator with 1, it changes the value to 1.

Suppose we have 113 and trying the 2nd bit.

``````   0111 0001   (binary of 113)
0000 0100   (1 << 2)
| -----------
0111 0101  --> 2nd bit is set
``````

## Unset n-th bit if it is not already unset

``````def unset_nth_bit(num, n: int) -> str:
if num & (1 << n):
unset_nth_bit_result = num & ~(1 << n)
return f"{n}th bit is unset ({bin(num)} is changed to {bin(unset_nth_bit_result)})"
else:
return f"{num} (decimal) = {bin(num)} (binary) and {n}th bit is ALREADY unset"
``````

Most important part of this trick is `num & ~(1 << n)` operation. It turns all bits on except the targetted one.

One’s complement operator (`~`);

``````~1           1111 1110
~(1 << 1)    1111 1101
~(1 << 2)    1111 1011
~(1 << 3)    1111 0111
~(1 << 4)    1110 1111
~(1 << 5)    1101 1111
and so on...
``````

By using the AND (`&`) operator with Left shifted One’s complement, we are eliminating the targetted bit.

Supporse that we want to unset 4th bit of 83;

``````   0101 0011   (binary of 83)
1110 1111   ~(1 << 4)
& -----------
0100 0011  --> 4th bit is unset
``````

## Toggle the n-th bit

So, we want to toggle the value of the nth bit to 1 if it is 0 and to 0 if it is 1.

``````def toggle_nth_bit(num, n: int) -> str:
toggled_number = num ^ (1 << n)
return f"{n}th bit of {bin(num)} toggled and the result is {bin(toggled_number)}"
``````

XOR (`^`) operator in `num ^ (1 << n)` toggles the value from 0 to 1 or vice versa.

As an example, let’s try to toggle 4th bit of 111;

``````   0110 1111   (binary of 111)
0001 0000   (1 << 4)
^ -----------
0111 1111  --> 4th bit toggled
``````

## Turn off the rightmost 1-bit

We are going to turn off the rightmost 1-bit. For example, 1001 1100 (rightmost 1-bit is the bold one) will turn into 1001 1000.

``````def turn_off_rightmost_1bit(num: int) -> str:
rightmost_1bit_turned_off = num & (num - 1)
return f"Rightmost 1-bit in {bin(num)} is turned off and the result: {bin(rightmost_1bit_turned_off)}"
``````

`num & (num - 1)` does the trick but how?

For example;

``````   1001 1100   (num)
1001 1011   (num - 1)
& -----------
1001 1000  --> rightmost 1-bit is turned off
``````
``````   1111 1111   (num)
1111 1110   (num - 1)
& -----------
1111 1110  --> rightmost 1-bit is turned off
``````
``````   0100 0000   (num)
0011 1111   (num - 1)
& -----------
0000 0000  --> rightmost 1-bit is turned off
``````

Substracting 1 from the original number sets all the lower bits to 1 and applying AND (`&`) operation sets all of them to 0 including the rightmost 1-bit.

## Isolate the rightmost 1-bit

We want to find rightmost 1-bit and set all other bits to 0. For example, 1001 1100 (rightmost 1-bit is the bold one) will turn into 0000 0100.

``````def isolate_rightmost_1bit(num: int) -> str:
isolated_number = num & (-num)
return f"Rightmost 1-bit in {bin(num)} is isolated and the result: {bin(isolated_number)}"
``````

`num & (-num)` does the isolation. We are going to use Two’s Complement for negative numbers method to be able to calculate `-num`.

``````   1011 1100   (num)
0100 0100   (-num)
& -----------
0000 0100  --> isolated rightmost 1-bit
``````

In Two’s Complement, `-num = ~num + 1` so adding `+1` because of Two’s Complement rules makes the trick here.

## Isolate the rightmost 0-bit

``````def isolate_rightmost_0bit(num: int) -> str:
isolated_number = ~num & (num + 1)
return f"Rightmost 0-bit in {bin(num)} is isolated and the result: {bin(isolated_number)}"
``````

`~num & (num + 1)` does the isolation. It finds the rightmost zero, turns other bits to 0 and sets isolated bit to 1.

If 1011 1100 is the number, bold 0 will be isolated;

``````   0100 0011   (~num)
1011 1101   (num + 1)
& -----------
0000 0001  --> rightmost 0 (zero) is isolated
``````

## Turn on the rightmost 0-bit

``````def turn_on_rightmost_0bit(num: int) -> str:
rightmost_0bit_turned_on = num | (num + 1)
return f"Rightmost 0-bit in {bin(num)} is turned on and the result: {bin(rightmost_0bit_turned_on)}"
``````

`num | (num + 1)` trick turns on the rightmost 0-bit. For example it turns 1010 1011 to 1010 1111

``````   1010 1011   (num)
1010 1100   (num + 1)
| -----------
1010 1111  --> rightmost 0 (zero) turned on
``````

If you like these tricks, you can check Peter’s Blog for more. Also, Bit Twiddling Hacks by Sean Eron Anderson has a very good collection of these tricks.

There is even a book entirely about these tricks called Hacker’s Delight by Henry S. Warren.