Nested for loops to iterate to the power of 2

Question

I need to use two loops in such a way that the outer loop drives the inner loop to do computations for 2,4,8,16,and 32 iterations.

for example if i=2(for outer loop) then inner loop will iterate for 4 times

and if i=3 then inner loop will iterate for 8 times and so on.

this is the logic I m using

for ( i = 0 ; i < n ; i++ ) 
     {
         for ( c = 0 ; c <= pow(2,i) ; c=c++ )   

I would really appreciate any suggestions

Answer 1

You'll want to use something like everyone else has suggested:

for (int i=0 ; i<n ; i++){
    for(int c=0 ; c < (1<<i) ; c++){
        //do computations
    }
}

The reason you want to use < instead of <= is becase <= will actually give you (2^i)+1 iterations, due to counting zero.

The reason you want to want to use the bitshift operation 1<<i, is because integers are already in base two, and adding zeros on the end is the equivelant of multiplying by two repeatedly. (1 is automatically created as an integer, while 1.0 is automatically created as a float. You could not safely do this with floats: 1.0<<1 bitshifts to 1.70141e+38, if you can get the compiler to do it.)

Finally, you want to use c++ because c++ increments c, but returns the original value, so your inner for-loop always keeps the original value and never increments.

Answer 2

1. Compute the number of iterations of the inner loop once and reuse it instead of computing it everytime.

2. Don't use pow(2, i). Use the more reliable 1 << i.

3. Don't use c = c++. Just use c++. I am not sure c = c++ is guaranteed to be c = c+1.

for ( i = 0 ; i < n ; i++ ) 
{
   int nextCount = (1 << i);
   for ( c = 0 ; c <= nextCount ; c++ ) 

Answer 3

You can use the fact that to compute a small power of two in C++ you can use a bit shift left:

for ( i = 0 ; i < n ; i++ ) {
    for ( c = 0 ; c < (1 << i) ; c++ ) {
        ...
    }
}

The reason behind this "magic" is the same as the reason why adding a zero to the right of a decimal number multiplies the number by ten.

Note that since you start the iteration of the inner loop at zero, you need to use <, not <=. Otherwise you would iterate 2ⁿ+1 times.