我需要这样的功能：

// return true iff 'n' is a power of 2, e.g.
// is_power_of_2(16) => true  is_power_of_2(3) => false
bool is_power_of_2(int n);

谁能建议我该怎么写？我们能告诉我一个好的网站，在哪里可以找到这种算法？

解决方案

2的幂只能设置一位(用于无符号数字)。就像是

bool powerOfTwo = !(x == 0) && !(x & (x - 1));

会很好的工作；较低有效位中的1小于2的幂是全1，因此必须按位与之和为0。

当我假设无符号数字时，== 0测试(我本来忘记了，对不起)就足够了。如果我们使用带符号整数，则可能需要> 0的测试。

bool is_power_of_2(int i) {
    if ( i <= 0 ) {
        return 0;
    }
    return ! (i & (i-1));
}

二进制的2的幂如下所示：

1: 0001
2: 0010
4: 0100
8: 1000

注意，总是精确地设置1位。唯一的例外是带符号整数。例如一个值为-128的8位带符号整数如下所示：

10000000

因此，在检查了该数字是否大于零之后，我们可以使用一个聪明的小技巧来测试仅设置了一位。

bool is_power_of_2(int x) {
    return x > 0 && !(x & (x?1));
}

有关更多信息，请参见此处。

这不是最快或者最短的方法，但我认为它非常易读。所以我会做这样的事情：

bool is_power_of_2(int n)
  int bitCounter=0;
  while(n) {
    if ((n & 1) == 1) {
      ++bitCounter;
    }
    n >>= 1;
  }
  return (bitCounter == 1);
}

这是可行的，因为二进制基于2的幂。任何只设置了一位的数字都必须是2的幂。

(n＆(n 1))== 0是最好的。但是，请注意，对于n = 0，它将错误地返回true，因此，如果可能的话，我们将需要显式检查它。

http://www.graphics.stanford.edu/~seander/bithacks.html包含大量聪明的位旋转算法，包括该算法。

另一种可行的方法(可能不是最快的方法)是确定ln(x)/ ln(2)是否为整数。