有很多答案和发布的链接解释了为什么n & (n-1) == 0适用于2的幂，但我找不到任何解释为什么它不适用于非2的幂，所以我只是为了完整起见添加了这个。

对于n = 1(2^0 = 1) 1 & 0 = 0，没问题。

对于奇数n > 1, 1至少有2位(最左位和最右位)。现在n和n-1只差最右位，所以它们的&和至少在最左位有一个1，所以n & (n-1) != 0:

n:          1xxxx1  for odd n > 1
n-1:        1xxxx0
            ------
n & (n-1):  1xxxx0 != 0

现在即使n不是2的幂，我们也至少有2位1(最左和非最右)。在这里，n和n-1最多相差1位，所以它们的&和也至少在最左边有一个1:

        right-most 1 bit of n
                 v
n:          1xxxx100..00 for even n
n-1:        1xxxx011..11
            ------------
n & (n-1):  1xxxx000..00 != 0

在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 IsPowerOfTwo(int n)
    {
        if (n > 1)
        {
            while (n%2 == 0)
            {
                n >>= 1;
            }
        }
        return n == 1;
    }

这是一个通用的算法用来判断一个数是否是另一个数的幂。

    bool IsPowerOf(int n,int b)
    {
        if (n > 1)
        {
            while (n % b == 0)
            {
                n /= b;
            }
        }
        return n == 1;
    }

private static bool IsPowerOfTwo(ulong x)
{
    var l = Math.Log(x, 2);
    return (l == Math.Floor(l));
}

返回(i & -i) == i

int isPowerOfTwo(unsigned int x)
{
    return ((x != 0) && ((x & (~x + 1)) == x));
}

这真的很快。检查所有2^32个整数大约需要6分43秒。