Bit Manipulation

DISCLAIMER: If you don’t know what a binary number is, then don’t read the rest of this page.

Basics

1s Complement

Flip all the bits of a binary number

2s Complement

Calculate 1s Complement
Add 1 to it

How are negative numbers stored in memory?

A positive number is represented as itself while a negative number is represented as the 2s complement of its absolute value, with a 1 in its sign bit to indicate that a negative value
In simple words, the binary representation of -K as a N-bit number is concat(1, 2^(N-1) - K)
More simpler words, invert the bits in the positive representation and then add 1
Example: +7 = 0 111
Calculating -7 ?
Flip the bits of +7 = 000
Add 1 to it = 001
Prefix with sign bit -7 = 1 001

Rules

Equation	Result
`x ^ 0`	`x`
`x ^ 1`	`~x`
`x ^ x`	`0`
`x & 0`	`0`
`x & 1`	`x`
`x & x`	`x`
`x \| 0`	`x`
`x \| 1`	`1`

Arithmetic vs. Logical Right Shift

There are 2 types of right shift operators
Arithmetic Right Shift essentially divides by 2 (shifts the bits to the right and fills the MSB with sign bit)
Example, -75 = 1 0110101
-75 >> 1 = 1 1011010 = -38
Logical Right Shift does exactly what we think right shifting means (shifts the bits to the right and fills the MSB with 0)
Example, -75 = 1 0110101
-75 >>> 1 = 0 1011010 = 90

Tricks

Multiplication by 2^x

Lets calculate 0110 * 2
which is 0110 + 0110 = 1100
observe that all the bits are shifted by 1 bit to the left
binary_numer * 2 is equivalent to binary_number << 1
Further results, what if I want to multiply binary number with 2^23 ?
Simply, shift 23 bits to the left, which is binary_number << 23

XOR with negated binary number

1100 ^ (~1100) = 1111
XORing with its negated value is a sequence of 1s

Clearing bits from the right

1011 & (~0 << 2)
~0 is a sequence of 1s
So, left shifting by 2 will be 2 zeroes at the right, followed by 1s
ANDing it with a number will clear the last 2 bits
= 1000

Get Bit

Shift 1 over by i bits (i = which bit you wanna get), creating a value that looks like 00100000
Then do logical AND with the number, and compare it with 0
If the ith bit was set, then the result won’t be 0
Example, Check if 5th bit from right is set or not, 10110110
We take 00000001, left shift by 5
00000001 << 5 = 00100000
logical AND with given number, 00100000 & 10110110 = 00100000
which is not equal to 0, so the 5th bit from right was set

 
    bool getBit(int num, int i) {
        return ((num & (1 << i)) != 0);
    }

Set Bit

Setting a bit is quite easy
Just shift the 1 to the desired location and do a logical OR

 
    int setBit(int num, int i) {
        return num | (1 << i);
    }

Clear Bit

Very similar to set bit, but here we negate the mask
Create a number like 11011111, then do logical AND

 
    int clearBit(int num, int i) {
        int mask = ~(1 << i);
        return num & mask;
    }

Clearing bits from MSB to i (inclusive)

 
    int clearBitMSBThroughI(int num, int i) {
        int mask = (1 << i) - 1;
        return num & mask;
    }

Clearing bits from i to 0 (inclusive)

 
    int clearBitIThrough0(int num, int i) {
        int mask = (-1 << (i + 1));
        return num & mask;
    }

Update Bit

It is a combination of clear bit and set bit

 
    int updateBit(int num, int i, bool bit) {
        int val = bit ? 1 : 0;
        int mask = ~(1 << i);
        return (num & mask) | (value << i);
    }

Brian Kernighan’s Algorithm

A famous algorithm to find the number of set bits in a number.

The main idea behind this algorithm is that when we subtract one from any number, it inverts all the bits after the rightmost set bit. For example.

Number	Binary Representation
10	01010
9	01001
8	01000
7	00111

The rightmost set bit also gets inverted along with the numbers right to it.

How can we count the number of set bits?

 
    int cnt = 0;
    while(num) {
        cnt++;
        num = num & num-1;
    }

num & num-1 will reverse the rightmost set bit. So, when all of the set bits will be reversed, the loop will run till the number becomes 0, and we get the count.