Isolate the lowest set bit

If we want to isolate the lowest bit that is 1 in an unsigned integer x, we can do this by calculating x & ~(x - 1).

It can be easily to derive. First, suppose x is not 0, it must have a bit that is 1. The lowest set bit is the first bit that is one from least significant bit to most significant bit. Subtracting one from x changes the lowest bit to 0 and sets all the lower bits to 1. All the higher bits remains unchanged. Therefore x & ~(x - 1) has a single bit set to 1, namely the lowest set bit. Now, suppose x is 0, subtracting one from x underflows, resulting a word in which all bits are set to one. Again, x & ~(x - 1) is 0.

A similar derivation shows that x & (x - 1) replaces the lowest bit that is one with zero. For example, if x = (00101100), then x - 1 = (00101011), so x & (x - 1) = (0010100). This fact is very useful.

Parity calculation

The parity of a binary word is 1 if the number of 1s in the word is odd, otherwise, it is 0.

Solution #1

We iteratively test the value of each bit while tracking the number of 1s so far seen. Since we only care if the number of 1s is odd or even, we can store the number modulo 2.

int parity(unsigned int x) {
    int res = 0;

    while (x) {
        result ^= (x & 1);
        x >>= 1;
    }
    return res;
}

Above method is a brute-force algorithm, the time complexity is O(n), where n is the word size.

Solution #2

Use aforementioned x & (x - 1) clears the lowest bit that is one, we can improve solution #1, let the time complexity O(k), where k is the number of 1s in word.

int parity(unsigned int x) {
    int res = 0;

    while (x) {
        result ^= 1;
        x &= (x - 1);
    }
    return res;
}
Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s