C#高效算法整数幂函数

Question

我正在研究实现基于整数的幂函数pow(int,int)的最有效方法.

这是他们得到的答案.

我试图让它适用于C#,但我正在将int与bool和所有其他东西进行比较...而且我无法弄清楚他们为什么要比较而且1这不是那个意思和真实吗？有什么意义呢.它看起来效率不高.

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

return result; 

}

我在比较中做exp ==但是1仍然在那里,我不知道我是否需要它.

有人知道"if(exp&1)"中的1是什么吗？或者如果我需要它？我看不出用途.

Answer 1

基本上在C和C++中,if/while的条件是"如果表达式非零".

所以在这种情况下你想要:

while (exp != 0)

和

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

你也想避免使用关键字base:)

我没有检查算法是否可以在C#中工作,但这至少可以帮助你更进一步.

Answer 2

这是方法的C#版本:

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

(正如Jon指出的那样,你应该避免使用base变量名,但是我将它保存在代码中以使其与C原始类似.)

当您&在两个整数(exp和1)上使用运算符时,它是一个二元运算符.目的是掩盖exp值中最不重要的位.

该方法的作用是它遍历exp值中的位,并将乘以的基值乘以对应于exp值中的位值.

例如,如果exp值为21,则为二进制10101,位值为16 + 4 + 1.它不是将基值乘以21倍,而是乘以16*base,4*base和1*base.