marcel novák marcel novák - 3 months ago 9
C Question

Why this type of power function work?

res = 1;
for ( i = 1; i <= n; i <<= 1 ) // n = exponent
{
if ( n & i )
res *= a; // a = base
a *= a;
}


This should be more effective code for power and I don't know why this works.

First line of for() is fine I know why is there i <<= i. But I don't understand the line where is: if ( n & i ). I know how that works but I don't know why...

Answer

Let us say you have a binary representation of an unsigned number. How do you find the decimal representation?

Let us take a simple four bit example:

N = |   0     |    1    |    0    |    1    |
    -----------------------------------------
    | 2^3 = 8 | 2^2 = 4 | 2^1 = 2 | 2^0 = 1 |
    -----------------------------------------
    |    0    |     4   |    0    |     1   |  N = 4 + 1 = 5

Now what would happen if the base wasn't fixed at 2 for each bit but instead was the square of the previous bit and you multiply the contribution from each bit instead of adding:

N = |   0   |  1  |  0  |  1   |
    ----------------------------
    |   a^8 | a^4 | a^2 |  a^1 |
    ----------------------------
    |   0   | a^4 |  0  |  a^1 |  N = a^4 * a^1 = a^(4+1) = a^5

As you can see, the code calculate a^N

Comments