Bit tricks every programmer should know
Tags: rust, bitwise, programming, tutorial
Published: 2022-06-02 19:06:30

---
title: Bit tricks every programmer should know
published: true
description: Simple, but quite interesting bitwise tricks written in Rust
tags: rust, bitwise, programming, tutorial
cover_image: https://64.media.tumblr.com/d77af5430465d72779430b74f3d2b8a8/f17886a2117f2172-36/s540x810/6493a0833ca7843badc4fa126dbd1c1676a148d0.jpg
---

## 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:**
```Rust
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:**
```Rust
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:**
```Rust
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:**
```Rust
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:**
```Rust
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:**
```Rust
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:**
```Rust
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:**
```Rust
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!).