Currently Being Moderated
Fareez Ahamed

Bitwise can avoid loops

Posted by Fareez Ahamed in ABAP Development on Apr 9, 2012 3:45:25 PM

The power of bitwise operators are immense. Sometimes thinking in terms of arithmetical operators cost you lots of CPU time when compared to bitwise operators. So given a problem its obvious for us to think in terms of arithmetical solutions, but try to search for a bitwise solution and compare it with previous one. You can end up in a very powerful algorithm too. Now I wish to share one such case where the use of bitwise operator avoids the use of a loop too.

 

Problem Statement: Given a number, check whether its a positive power of two or not.

 

First I would like to give a simple arithmetical solution. Here I have given the solution in the syntax of C as the problem we are talking is algorithmic and not language oriented. Moreover, everyone would be able to understand the program flow in C easily.

 

int main()
{
    int a=256,rem,flag=0;
    
    while(a>1)
    {
        c=a%2;
        if(c==1)
        {
            flag=1;
            break;
        }
        a=a/2;
    }
    if(flag==1)
        printf("Not Power of 2");
    else
        printf("Power of 2");
    return 0;
}

 

This is quite a good algorithm of order O(log2n), that is, given a number n, it will take log2n operations to find the result. So, if n is 256, then 8 operations are required to produce the result. The algorithm that we have come up with works at an amazing rate. O(log2n) is a very good algorithm. Still, if it can be reduced further to O(1) it will be great isn't it. Bitwise operators come to the rescue.

 

Now see the program below which is the bitwise algorithm for solving the same problem.

 

int main()
{
    int a=256;
    
    if((a&(a-1)==0)
        printf("Power of 2");
    else
        printf("Not Power of 2");
    return 0;
} 

 

 

This bitwise algorithm has only one operation which checks a&(a-1) is 0 or not. If its 0, then its a power of 2 otherwise its not. How? It seems amazing isn't it? Let's see.

 

First note the binary representations of the powers of 2.

 

2^0 =   1 => 00000001
2^1 =   2 => 00000010
2^2 =   4 => 00000100
2^3 =   8 => 00001000
2^4 =  16 => 00010000
2^5 =  32 => 00100000
2^6 =  64 => 01000000
2^7 = 128 => 10000000

 

Now check out the other part, binary representations of (2^n)-1.

 

(2^0)-1 =   0 => 00000000
(2^1)-1 =   1 => 00000001
(2^2)-1 =   3 => 00000011
(2^3)-1 =   7 => 00000111
(2^4)-1 =  15 => 00001111
(2^5)-1 =  31 => 00011111
(2^6)-1 =  63 => 00111111
(2^7)-1 = 127 => 01111111

 

A sample and operation of a power of 2 and its previous number.

 

8&7 => 00001000 & 00000111 => 00000000

 

And when its not a power of 2

 

6&5 => 00000110 & 00000101 => 00000100

 

Bitwise representation of a number which is power of 2 varies at every bit from the previous numbers bitwise representation. But when its not a power of two, they have at least one '1' in common position. Now its clear that whenever you make an AND operation on the numbers which is power of 2 and one less than that, ultimately you end up at zero. Similarly, if the number is not a power of 2, you will end up in a non zero number.

 

This is an example to show the power of bitwise operators. Hope you enjoyed.

 

- Fareez Ahamed K.N.

Comments

Actions

Filter Blog

By author:
By date:
By tag:

Incoming Links