marcel novák - 6 months ago 23

C Question

`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