返回(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

以下对已接受答案的补充可能对某些人有用:

2的幂，当用二进制表示时，总是像1后面跟着n个0，其中n大于等于0。例:

Decimal  Binary
1        1     (1 followed by 0 zero)
2        10    (1 followed by 1 zero)
4        100   (1 followed by 2 zeroes)
8        1000  (1 followed by 3 zeroes)
.        .
.        .
.        .

等等。

当我们把这些数减1，它们就变成0后面跟着n个1，同样，n和上面一样。例:

Decimal    Binary
1 - 1 = 0  0    (0 followed by 0 one)
2 - 1 = 1  01   (0 followed by 1 one)
4 - 1 = 3  011  (0 followed by 2 ones)
8 - 1 = 7  0111 (0 followed by 3 ones)
.          .
.          .
.          .

等等。

说到关键

当我们对一个数字x做位与运算时会发生什么，x是a 2的幂，x - 1呢?

x的1与x - 1的0对齐，x的所有0与x - 1的1对齐，导致按位and的结果为0。这就是为什么上面提到的单行答案是正确的。

进一步增加了上述公认答案的美感

所以，我们现在有一个属性可供我们使用:

当我们用任何数减去1时，那么在二进制表示法中，最右边的1将变成0，而最右边1左边的所有0也将变成1。

这个性质的一个很棒的用途是求出一个给定数字的二进制表示中有多少个1 ?对于给定的整数x，简短而甜蜜的代码是:

byte count = 0;
for ( ; x != 0; x &= (x - 1)) count++;
Console.Write("Total ones in the binary representation of x = {0}", count);

从上面解释的概念可以证明数字的另一个方面是“每个正数都可以表示为2的幂的和吗?”

是的，每一个正数都可以表示成2的幂的和。对于任何数字，取其二进制表示。乘117路车。

The binary representation of 117 is 1110101

Because  1110101 = 1000000 + 100000 + 10000 + 0000 + 100 + 00 + 1
we have  117     = 64      + 32     + 16    + 0    + 4   + 0  + 1

这是另一种方法

package javacore;

import java.util.Scanner;

public class Main_exercise5 {
    public static void main(String[] args) {
        // Local Declaration
        boolean ispoweroftwo = false;
        int n;
        Scanner input = new Scanner (System.in);
        System.out.println("Enter a number");
        n = input.nextInt();
        ispoweroftwo = checkNumber(n);
        System.out.println(ispoweroftwo);
    }
    
    public static boolean checkNumber(int n) {
        // Function declaration
        boolean ispoweroftwo= false;
        // if not divisible by 2, means isnotpoweroftwo
        if(n%2!=0){
            ispoweroftwo=false;
            return ispoweroftwo;
        }
        else {
            for(int power=1; power>0; power=power<<1) {
                if (power==n) {
                    return true;
                }
                else if (power>n) {
                    return false;
                }
            }
        }
        return ispoweroftwo;
    }
}

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

在发布了这个问题之后，我想到了以下解决方案:

我们需要检查是否有一个二进制数字是1。因此，我们只需将数字每次右移一位，如果它等于1则返回true。如果在任何时候我们得到一个奇数((number & 1) == 1)，我们知道结果是假的。这被证明(使用基准测试)对于(大)真值比原始方法略快，对于假值或小值则快得多。

private static bool IsPowerOfTwo(ulong number)
{
    while (number != 0)
    {
        if (number == 1)
            return true;

        if ((number & 1) == 1)
            // number is an odd number and not 1 - so it's not a power of two.
            return false;

        number = number >> 1;
    }
    return false;
}

当然，格雷格的解决方案要好得多。