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;
 }

我在比较中使用了 ==，但是那个1还在那里，我不知道是否需要它。

有人知道 if (exp & 1) 中的1是用来干什么的吗？或者我是否需要它？我看不出有什么用处。

- Hazior

Answer 1

基本上在C和C++中，if/while的条件是“如果表达式非零”。

所以在这种情况下，您应该使用：

while (exp != 0)

并且

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

您也需要避免使用关键字base :)

我还没有检查过此算法是否适用于C#，但这至少可以帮助您向前迈进一步。

- Jon Skeet

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相乘。

- Guffa

Answer 3

'&' 是一个二进制运算符。'&&' 是一个逻辑运算符。 假设你有一个变量：

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

你的'a'实际上是二进制的00000101，而b是00000001。 当你执行a&b时，它意味着对这些数字的每个位执行AND操作。这意味着第一个位将“and”以及第二个位等等。 在C中的结果将是00000001。因为a AND b唯一为1的地方是在最后一位。

你也可以使用或('|')运算符执行相同的操作。

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

因为 OR 运算符要求至少有一个位为真;

- synepis

---

不对。&和&&都是逻辑运算符，而&也是二元运算符。它取决于操作数的类型。 - Guffa

抱歉Guffa。二进制的“与”和逻辑上的“与”是非常不同的。在C#中，你甚至不能将' && '运算符应用于整数。 - Jay

Answer 4

你在这里遇到的问题是，C使用数字来获取布尔值。因此，将int与1进行比较将对两个值执行AND操作，然后取结果并将其评估为布尔值。

C#不会执行相同的操作，你需要重新思考算法。

- gbianchi

Answer 5

对于 .NET 5 及更高版本，这是最快的...

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

注意：这只能在 .NET 5 及以上版本中实现快速操作。从 .NET 4 到 .NET 5，速度提高了 350 倍。

- SunsetQuest