bool isPow2 = ((x & ~(x-1))==x)? !!x : 0;

返回(i & -i) == i

在C中，我测试了I && !(I & (I - 1)技巧，并将其与__builtin_popcount(I)进行比较，在Linux上使用gcc，使用-mpopcnt标志，以确保使用CPU的POPCNT指令。我的测试程序计算了0到2^31之间2的幂的整数个数。

起初，我认为I && !(I & (I - 1)快10%，即使我验证了在我使用__builtin_popcount的反汇编中使用了POPCNT。

然而，我意识到我已经包含了一个if语句，分支预测可能在位旋转版本上做得更好。我删除了if和POPCNT，结果更快，正如预期的那样。

结果:

英特尔(R)酷睿(TM) i7-4771 CPU最大3.90GHz

Timing (i & !(i & (i - 1))) trick
30

real    0m13.804s
user    0m13.799s
sys     0m0.000s

Timing POPCNT
30

real    0m11.916s
user    0m11.916s
sys     0m0.000s

AMD Ryzen Threadripper 2950X 16核处理器最大3.50GHz

Timing (i && !(i & (i - 1))) trick
30

real    0m13.675s
user    0m13.673s
sys 0m0.000s

Timing POPCNT
30

real    0m13.156s
user    0m13.153s
sys 0m0.000s

请注意，这里英特尔的CPU似乎比AMD的比特旋转稍慢，但有一个更快的POPCNT;AMD的POPCNT没有提供这么多的提升。

popcnt_test.c:

#include "stdio.h"

// Count # of integers that are powers of 2 up to 2^31;
int main() {
  int n;
  for (int z = 0; z < 20; z++){
      n = 0;
      for (unsigned long i = 0; i < 1<<30; i++) {
       #ifdef USE_POPCNT
        n += (__builtin_popcount(i)==1); // Was: if (__builtin_popcount(i) == 1) n++;
       #else
        n += (i && !(i & (i - 1)));  // Was: if (i && !(i & (i - 1))) n++;
       #endif
      }
  }

  printf("%d\n", n);
  return 0;
}

运行测试:

gcc popcnt_test.c -O3 -o test.exe
gcc popcnt_test.c -O3 -DUSE_POPCNT -mpopcnt -o test-popcnt.exe

echo "Timing (i && !(i & (i - 1))) trick"
time ./test.exe

echo
echo "Timing POPCNT"
time ./test-opt.exe

这是我设计的另一个方法，在这种情况下使用|而不是&:

bool is_power_of_2(ulong x) {
    if(x ==  (1 << (sizeof(ulong)*8 -1) ) return true;
    return (x > 0) && (x<<1 == (x|(x-1)) +1));
}

解决这个问题有一个简单的技巧:

bool IsPowerOfTwo(ulong x)
{
    return (x & (x - 1)) == 0;
}

注意，这个函数对于0报告为真，因为0不是2的幂。如果你想排除这种情况，以下是方法:

bool IsPowerOfTwo(ulong x)
{
    return (x != 0) && ((x & (x - 1)) == 0);
}

解释

首先，MSDN定义中的按位二进制&运算符:

二进制和操作符是为整型和bool类型预定义的。为 整型，&计算其操作数的逻辑位与。 对于bool操作数，&计算其操作数的逻辑与;那 Is，当且仅当它的两个操作数都为真时，结果为真。

现在让我们来看看这一切是如何发生的:

该函数返回布尔值(true / false)，并接受一个unsigned long类型的传入参数(在本例中为x)。为了简单起见，让我们假设有人传递了值4，并像这样调用函数:

bool b = IsPowerOfTwo(4)

现在我们将x的每一次出现都替换为4:

return (4 != 0) && ((4 & (4-1)) == 0);

我们已经知道4 != 0的值为真，到目前为止还不错。但是:

((4 & (4-1)) == 0)

当然，这可以转化为:

((4 & 3) == 0)

但是4和3到底是什么呢?

4的二进制表示是100,3的二进制表示是011(记住&取这些数字的二进制表示)。所以我们有:

100 = 4
011 = 3

想象一下这些值像基本加法一样堆积起来。&运算符表示，如果两个值都等于1，则结果为1，否则为0。1 & 1 = 1,1 & 0 = 0,0 & 0 = 0, 0 & 1 = 0。我们来算算:

100
011
----
000

结果就是0。所以我们回过头来看看return语句现在转换成了什么:

return (4 != 0) && ((4 & 3) == 0);

现在翻译过来就是:

return true && (0 == 0);

return true && true;

我们都知道true && true就是true，这表明在我们的例子中，4是2的幂。

bool isPowerOfTwo(int x_)
{
  register int bitpos, bitpos2;
  asm ("bsrl %1,%0": "+r" (bitpos):"rm" (x_));
  asm ("bsfl %1,%0": "+r" (bitpos2):"rm" (x_));
  return bitpos > 0 && bitpos == bitpos2;
}