Bit tricks every programmer should know

Intro

Hey everyone, I bet during a regular day at work you guys rarely shift bits left and right, applying ^ (XOR) or & (AND). So today I want to shed some light on a few basic bit tricks that you all might find helpful (or maybe not).

Left Shift

The basic one, but let's refresh our memories here and look at examples of how the left shift <<< operator works.

Example:
Let's say we want to shift number 3 (11 in binary) by one bit to the left and it gives us 6 (110).
3 << 1 = 110 = 6
3 << 2 = 1100 = 12
3 << 3 = 11000 = 24

Code:

fn left_shift(num: usize, offset: usize) -> usize {
    num << i
}

Check if the Nth bit is set

This one is a bit trickier, it tells us whether the Nth bit from the right side is set to 1. And we gonna use & (AND) operator to do so.

Example:
Let's say we want to check if 0 or 3rd bits are set to 1 in number 8 (1000 in binary).

8 = 1000
if offset == 0:
1000 & 0001 = 0 -> false (not set)
if offset == 3:
1000 & 1000 = 1 -> true (set)

Code:

fn is_set(num: usize, offset: usize) -> bool {
    (num & (1 << offset)) != 0
}

Set Nth bit to 1

Ok, here we're actually going to set a particular bit to 1 in case it's 0, or keep it as 1 if it's already set to 1.

Example:
Let's continue playing with the number 8 (1000 in binary).
(8) 1000 set 3rd and 0th bit (from right) to 1
1000 | 1000 = 1000 == 8 (nothing changed since it was already 1)
1000 | 0001 = 1001 = 9 (set first bit to 1)

Code:

fn set_bit(num: usize, offset: usize) -> usize {
    num | (1 << offset)
}

Flip Nth bit

Here we continue playing with one bit at a time. Similar to the previous one, we do not only set the bit to 1 but actually flip the actual value of a bit. For this, we gonna use ^ (XOR)!

Example:
Again 8 is 1000 in binary
1000(8) ^ 1000(8) = 0 (flipped left 1 to 0)
1000 ^ 1001 = 1001 (flipped right 1)

Code:

fn flip_bit(num: usize, offset: usize) -> usize {
    num ^ (1 << offset)
}

Number complement (NOT)

This is another standard operator many people don't even know what is it for. ! (NOT) (in java it would be ~) inverts all bits of a particular number.

Example:
Let's take 9 as our integer (1001 in binary)
We can represent 9 as u8, u32, etc, let's consider u32 to resolve confusion.
!1001 = 11111111111111111111111111110110
Because = 1001 in 32-bit representation is actually:
00000000000000000000000000001001, so inverting all bits gives us 11111111111111111111111111110110, which is 4294967286 in decimal.

Code:

fn not(num: u32) -> u32 {
    !num
}

Clear Nth bit

This one is pretty straightforward, though the concept is quite interesting. The goal is to set Nth bit to zero.

Example:
Again the integer is going to be 9 (1001).
Then let's say we want to clear the first bit from the right side.
As we already know ! operator (complement) inverts all the bits for us. So we can shift 1 by offset to find the bit we're looking for.

1. 1 << offset = 1 in our case (0th bit)
2. !1 = 1111111*0* (depending on type, let's keep u8)
3. return 1001 & 11111110 = 1000 (8)

Code:

fn clear_bit(num: usize, offset: usize) -> usize {
    let mask = !(1 << offset);
    num & mask
}

Calculating Hamming weight

Hamming weight is essentially a number of ones in a binary representation of a number. There is an interesting observation has been made by Brian Kernighan,coauthor of first C language Book, which we're going to use here.
Every time we apply n & (n - 1) where n is 32-bit integer, the rightmost bit becomes 0.

Example:
Let's take binary 01010101.
1st iteration: 01010100
2nd iteration: 01010000
3rd iteration: 01000000
So by counting a number of iterations we can calculate the number of ones.

Code:

fn hamming_weight (mut n: usize) -> usize {
    let mut count = 0;
    while n != 0 {
        n &= n - 1;
        count += 1;
    }
    return count;
}

Check if exactly one bit is set

Here is another interesting observation. If our number is a power of 2, then we can say that only one bit is set. To check this, we just need to subtract one and apply & operator!

Example:
8 = 1000
8 - 1 = 7 = 0111
1000 & 0111 = 0000 -> TRUE!

Code:

fn check_exactly_one_bit_is_set(num: usize) -> bool {
    num != 0 && (num & (num - 1)) == 0
}

Conclusion

I hope you find those little tricks as fascinating as I think of them and maybe even apply them in your regular job (but don't forget about code readability!).

Comments

[Georgi Slavov]

Thanks! Helped me a lot!