java - 确定数字是否为 2 的幂的最有效的编程方法是什么？

Question

只是一个非常有效的简单布尔真/假就会很好。我应该使用递归，还是有更好的方法来确定它？

Answer 1

从这里：

确定整数是否为 2 的幂

unsigned int v; // we want to see if v is a power of 2
bool f;         // the result goes here 

f = (v & (v - 1)) == 0;

请注意，此处将 0 错误地视为 2 的幂。要解决此问题，请使用：

f = v && !(v & (v - 1));

为什么这行得通？2 的整数幂只有一个位集。减 1 的效果是将该位更改为 0，并将其下方的所有位更改为 1。AND'ing 与原始数字将始终导致全零。

Answer 2

2 的整数幂将是 1 后跟一个或多个零

IE

     Value          value -1 (binary)
   10      2              1
   100     4             11 
   1000    8            111 
   10000  16           1111 

正如米奇所说

  (value & (value-1)) == 0

当value是 2 的幂时（但对于除 1 / 0 和 1 之外的任何其他数字均不适用，并且 1 通常被视为 2 的 0 次幂）。

对于米奇的解决方案，其中数字 > 0 不是 2 的幂，即

    value              value - 1       V & (v-1)
   1000001             1000000         1000000
   1000010             1000001         1000000
   1000100             1000011         1000000
   1001000             1000111         1000000

   1000011             1000010         1000010
   1000101             1000100         1000100
   1000111             1000110         1000110

并且永远不会为零。

从一个数字中减去 1 会将位反转到并包括第一个 1；对于二的幂，只有一个“1”，因此 Value & (Value-1) == 0，对于其他数字，第二个和后续的 1 不受影响。

零将需要被排除

---

另一种可能的解决方案（可能稍慢）是

   A & (-A) == A


Powers of 2:
     A      -A 
   00001 & 11111 = 00001
   00010 & 11110 = 00010
   00100 & 11100 = 00100

其他一些数字：

     A      -A 
   00011 & 11101 = 00001
   00101 & 11011 = 00001

同样，您还需要排除 0

---

为了解决这个问题，我做了

1. 把数字写成二进制；你会看到 2 的幂只有一个
2. 在布尔级别摆弄各种运算符/布尔值，看看有什么用

这样做，我发现以下方法也有效：

  A & (-A) == A        
 (not A) | (not A + 1) == -1    /* boolean not of a & (a-1) == 0 */

Answer 3

不确定您的意思是在计算速度方面还是在代码行方面有效。但你可以试试value == Integer.highestOneBit(value)。如果需要，不要忘记排除零。