C# Efficient Algorithm Integer Based Power Function

Question

I am looking at The most efficient way to implement an integer based power function pow(int, int).

This is the answer they got.

I am trying to make it work for C# but I am getting comparing int to bool and all this other stuff. . . and I can't figure out why they are comparing & 1 wouldn't that mean and true? What is the point of that. It doesn't seem efficient.

 int ipow(int base, int exp)
 {
     int result = 1;
     while (exp)
     {
         if (exp & 1)
             result *= base;
         exp >>= 1;
         base *= base;
     }
 
     return result;
 }

I am doing exp == on the compare but that 1 is still there and I don't know if I need it.

Does someone know what the 1 in if (exp & 1) is for? Or if I need it? I can't see the use.

Answer 1

Basically in C and C++, the condition for if/while is "if the expression is non-zero".

So in this case you'd want:

while (exp != 0)

and

if ((exp & 1) != 0) // If exp is odd

You'd also want to avoid using the keyword base :)

I haven't checked whether the algorithm will work in C#, but that should at least help you get one step further.

Answer 2

Here's a C# version of the method:

int ipow(int base, int exp) {
   int result = 1; 
   while (exp > 0) {
      if ((exp & 1) != 0) { 
         result *= base;
      } 
      exp >>= 1; 
      base *= base; 
   } 
   return result; 
}

(As Jon pointed out you should avoid using base as variable name, however I kept it in the code to make it similar to the C original.)

When you are using the & operator on two integers (exp and 1) it's a binary operator. The purpose is to mask out the least signifiact bit in the exp value.

What the method does is that it goes through the bits in the exp value, and multiplies the base values multiplied to correspond to the value of the bits in the exp value.

If the exp value for example is 21, that is 10101 in binary, with the bit values 16+4+1. Instead of multiplying the base value 21 times, it multiplies 16 * base, 4 * base, and 1 * base.

Answer 3

'&' is binary opererator. '&&' is a logical operator. lets say you have

int a = 5, b = 1;
int c = a & b;

Your 'a' is actually 00000101 in binary and b is 00000001. When you do a&b it means to do a AND operation on every bit of those numbers. Meaning the first bits will "anded" and the second and so on. The result in C will be 00000001. Because the only place where a AND b are 1 is on the last bit.

You can do the same with the or( '|' ) operator.

int d = a | b; //d = 00000101

beacause OR operator asks for atleast one bit to be true;

Answer 4

The problem you have here, is that C use numbers to get boolean values. So compare a int with 1 will do a AND operation over the two values, and then will take the result and evaluate it as a boolean.

C# will not do the same, you need to re think the algorithm here

Answer 5

for .NET 5 and newer here is the fastest...

int answer = (int)Math.Pow(x, pow);
    

Note: this is only fast in .net 5 and later. The speed increased 350X from .net 4 to .net 5.