Skip to content

Bits manipulations

This page include some elegant ways you can use to implement binary strings.

1. Check if a number is a power of 2.

Solution

Typical solution

1
2
3
4
5
6
7
bool isPow2(int a) {
    if (a == 0) {return false;}
    else {
        while (a % 2 == 0) a /= 2;
        return (a == 1);
    }
}

Using bits

Let's try to visualize a power of 2 in binary. It would consist of exactly one "1" digit, so when you subtract 1 from it it would be equivelent to negating it. A negated binary when bitwised-and with the original binary it would give 0.

- 8 13 26 16
a 1000 1101 11010 10000
a-1 0111 1100 11001 01111
a & (a-1) 0000 1100 11000 00000

1
2
3
bool isPow2(int a) {
    return (a && !(a & (a-1)));
}
a checks if a != 0, !(a & (a-1)) checks if a-1 is a negation of a.

2. Count # 1's in a binary

Solution

In the previous example we noticed a relation between a, and a-1. That is:

a-1⇔ flipping all digits of a until the first "1".

{a}2 104 116 5
a 1101000 1110100 101
a-1 1100111 1110011 100
a & (a-1) 1100000 1110000 100

Exploiting this observation, each time we bitwise-and a, a-1 we make all digits until the first "1" zeroes.

1
2
3
4
5
6
7
8
int countOnes(int a) {
    int count = 0;
    while (a) {
        a &= a-1;
        ++count;
    }
    return count;
}