Bit Manipulation Tricks

12 minute read

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;

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

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

0101  (binary of 37)
0001  (binary of 1)
& -----------
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

       0000 0001
<< 1    0000 0010
<< 2    0000 0100
<< 3    0000 1000
<< 4    0001 0000
<< 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 5^th bit is set;

1111  (binary of 175)  
0000  (1 << 5)
& -----------
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 2^nd bit.

0001   (binary of 113)
0100   (1 << 2)
| -----------
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 4^th bit of 83;

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

Toggle the n-th bit

So, we want to toggle the value of the n^th 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 4^th bit of 111;

1111   (binary of 111)
0000   (1 << 4)
^ -----------
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;

1100   (num)
1011   (num - 1)
& -----------
1000  --> rightmost 1-bit is turned off

1111   (num)
1110   (num - 1)
& -----------
1110  --> rightmost 1-bit is turned off

0000   (num)
1111   (num - 1)
& -----------
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.

1100   (num)
0100   (-num)
& -----------
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;

0011   (~num)
1101   (num + 1)
& -----------
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

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

References

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.

Share on

Twitter Facebook LinkedIn

Emre Bolat