Optimizing programs using bitwise operations

[Nineshadow]

Introduction

Every once in a while in the life of a programmer, we find that our implementation of an algorithm isn't fast enough. The first thing that crosses our mind is to make another algorithm with a lower Big-O complexity. However, the Big-O notation is an aproximation of the speed of a program, and not an absolute unit of measure. For small input, the difference between an O(n) algorithm and an O(n*log n) or even O(n^{2 or 3}) sometimes can't even be observed. I've even seen an algorithm in O(n*log n) actually perform faster than a liniar one.

 

In this kind of situations, we can use bitwise operations to make algorithms faster.

Here are a few examples :

Note that all of them use 32-bit integers.

 

1.Determine the number of bits in the binary representation of the number n

 

The first and naive solution to this problem would be going through each bit of the number and counting the number of bits with the value 1 we encounter.

int count(long n) {    int num = 0;    for (int i = 0; i < 32; i++)        if (n & (1 << i)) num++;    return num;}

Let's look at what n & (n-1) does :

11011101010000 = n

11011101001111 = n - 1

11011101000000 = n & (n - 1)

 

It's clear that it has the effect of canceling the least semnificative bit with the value 1.

 

So, here's our new algorithm :

int count(long n) {    int num = 0;    if (n)        do num++; while (n &= n - 1);    return num;}

The speed difference ? After testing all numbers from 1 to 2²⁴, it took 2,654 seconds with the first method, and 0.821 with the second one.

 

 

2.Determine the parity of the number of bits with the value 1 from the binary represantation of a number n

From what you've seen so far, there's 2 obvious solutions :

int parity(long n) {    int num = 0;    for (int i = 0; i < 32; i++)        if (n & (1 << i)) num ^= 1;    return num;}

int parity(long n) {    int num = 0;    if (n)        do num ^= 1; while (n &= n - 1);    return num;} 

Considering n =  11011011, our result is given by 1 ^ 1 ^ 0 ^ 1 ^ 1 ^ 0 ^ 1 ^ 1. 

We divide n in a superior and inferior part :

 1 1 0 1 ^ 1 0 1 1 = 0 1 1 0

We apply the same algorithm untill we reach an end :

01 ^ 1 0 = 1

1^1 = 0

 

Again, considering a 32-bit integer , our algorithm is :

int parity(long n) {    n = ((0xFFFF0000 & n) >> 16) ^ (n & 0xFFFF);    n = ((0xFF00 & n) >> 8) ^ (n & 0xFF);    n = ((0xF0 & n) >> 4) ^ (n & 0xF);    n = ((12 & n) >> 2) ^ (n & 3);    n = ((2 & n) >> 1) ^ (n & 1);    return n;} 

3.Determine the least semnificative bit with the value 1 from the binary representation of the number n

The naive solution usually works well, since you'll reach the least semnificative bit with the value 1 pretty easily , but it can be done even better.

As we've shown before, n & (n-1) removes the least semnificative bit from n.

Thus :

11011000 = n

11010111 = n - 1
11010000 = n & (n - 1)
11011000 = n
00001000 = n ^ (n & (n - 1))

Our algorithm is :

int low1(long n) {    return n ^ (n & (n - 1));}

This is very useful for binary-indexed trees.

 

5.Determine the index of the most significant bit with the value 1 from the binary representation of the number n

Again, we can use methods from before, but I'll present you another one :

Let's use this example :

n = 10000000

n = n | (n >> 1)

n = 11000000

n = n | (n >> 2)

n = 11110000

n = n | (n >> 4)

n = 11111111

By doing this, we can make a number with a number of bits with the value 1 equal to 1 plus the index of the most significative bit with the value 1 from the original number.

Our algorithm is :

int indexHigh1(long n) {    n = n | (n >> 1);    n = n | (n >> 2);    n = n | (n >> 4);    n = n | (n >> 8);    n = n | (n >> 16);    return count(n) - 1;}

This also needs an efficient count method, which has been presented before.

 

6. Determine if n is a power of 2 (from a Microsoft job interview)

There's quite a few naive methods, but using n & (n-1) is the most efficient, since a power of 2 will only have 1 bit with the value 1, and n & (n-1) has the effect of removing the least semnificative bit, in our case the only bit. Thus, when we apply n & (n-1) to an n = 2^p , the result would be 0.

int isTwoPower(long n) {    return ( n & (n - 1) ) == 0 ;}

Conclusion

Optmizations based on bitwise operations can make your program run faster, but at the same time it makes it harder for other people to read and understand your code, so use them in critical places, after documenting them very carefuly.

Also, another great thing for optimization can be pre-processing.

_________________________________________________________________________________________________________________________

 

Updating this post later with more stuff.

Add your input if you want so.

I'm just spreading awareness about bitwise operations.

[Nineshadow]

RESERVED.

 

Dunno if I'll actually get to put anything else in this post though.

 

Potato.

[Ciccioo]

this is the kind of performance improvement that is useless at best in 99% of real world day to day coding scenarios, but man does it feel awesome to do things hacky with bits 'n stuff. i love it

[Nineshadow]

this is the kind of performance improvement that is useless at best in 99% of real world day to day coding scenarios, but man does it feel awesome to do things hacky with bits 'n stuff. i love it

Shhh...it's more like 99.5%, but hey D: .

It's good knowledge anyway.

[jubjub]

this is the kind of performance improvement that is useless at best in 99% of real world day to day coding scenarios, but man does it feel awesome to do things hacky with bits 'n stuff. i love it

Sure but so is most stuff in programming, it's actually a really powerful way to do things. In fact it comes in very helpful when you do multithreading.

 

Also, this is a really cool post. 10/10

 

Do you have many examples where you have used this in the real world day to day op?

[Nineshadow]

Sure but so is most stuff in programming, it's actually a really powerful way to do things. In fact it comes in very helpful when you do multithreading.

 

Also, this is a really cool post. 10/10

 

Do you have many examples where you have used this in the real world day to day op?

Actually , quite a lot of them , since most of the stuff I do is figuring out really efficient algorithms, or just faster execution. I recently managed to solve a previous O(nlogn) in O(1) using bitwise operations, a single one actually.

[as96]

Outside of school the only time I remember using them was for making flags but that's cool guide

[Bene]

I test the first one, count 1's. the "naive solution" in Visual Studio 2015, takes about 0.98s

 

which compiler do you use?