如何检查一个数是否是2的幂

今天，我需要一个简单的algorithm来检查一个数是否是2的幂。

该algorithm需要是：

简单
纠正任何超值。

我想出了这个简单的algorithm：

 private bool IsPowerOfTwo(ulong number) { if (number == 0) return false; for (ulong power = 1; power > 0; power = power << 1) { // This for loop used shifting for powers of 2, meaning // that the value will become 0 after the last shift // (from binary 1000...0000 to 0000...0000) then, the 'for' // loop will break out. if (power == number) return true; if (power > number) return false; } return false; }

但后来我想，如何检查log ₂ x是一个完整的整数？但是当我检查2 ^ 63 + 1时， Math.Log由于四舍五入而正好返回63。所以我检查了2的幂63是否等于原来的数字 – 这是因为计算是以double s完成的，而不是确切的数字：

 private bool IsPowerOfTwo_2(ulong number) { double log = Math.Log(number, 2); double pow = Math.Pow(2, Math.Round(log)); return pow == number; }

对于给定的错误值，这返回true ： 9223372036854775809 。

有更好的algorithm吗？

这个问题有一个简单的技巧：

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

注意，这个函数会报0 ，这不是2的幂。如果你想排除这一点，这里是如何：

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

说明

首先是MSDN定义中的按位二进制＆运算符：

二进制＆运算符是为整型和布尔值预定义的。对于整数types，＆计算其操作数的逻辑按位与。对于bool操作数，＆计算其操作数的逻辑与; 也就是说，当且仅当两个操作数都为真时，结果才是真的。

现在让我们来看看这一切如何发挥：

该函数返回布尔值（true / false），并接受一个types为unsigned long（x，在这种情况下）的传入参数。让我们为了简单起见，假设有人已经通过了价值4，并称这样的function：

 bool b = IsPowerOfTwo(4)

现在我们用4replace每个x的出现：

 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 。所以我们做math：

 100 011 ---- 000

结果只是0.所以我们回头看看我们的返回语句现在转化为：

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

现在翻译成：

 return true && (0 == 0);

 return true && true;

我们都知道true && true是true ，这表明对于我们的例子，4是2的幂。

一些网站，logging和解释这个和其他一些twiddling黑客是：

而他们的祖父，亨利·沃伦（Henry Warren，Jr.）写的“黑客的喜悦”（Hacker's Delight）

http://www.hackersdelight.org/

正如肖恩·安德森（Sean Anderson）的页面所解释的，expression式((x & (x - 1)) == 0)错误地表明0是2的幂。他build议使用：

 (!(x & (x - 1)) && x)

纠正这个问题。

return (i & -i) == i

我最近在http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/上写了一篇关于这方面的文章。; 它涵盖了位计数，如何正确使用对数，经典的“x &&！（x＆（x – 1））”检查等等。

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

这是一个简单的C ++解决scheme：

 bool IsPowerOfTwo( unsigned int i ) { return std::bitset<32>(i).count() == 1; }

  bool IsPowerOfTwo(int n) { if (n > 1) { while (n%2 == 0) { n >>= 1; } } return n == 1; }

这里有一个通用的algorithm，用于确定一个数字是否是另一个数字的幂。

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

发布问题后，我想到了以下解决scheme：

我们需要检查是否只有一个二进制数字是一个。所以我们简单地把数字右移一位数字，如果它等于1就返回true 。如果在任何时候我们都有一个奇数（ (number & 1) == 1 ），我们知道结果是false 。这certificate了（使用基准）比原始方法稍微快一些（大）真值，而对于错误或较小的值则要快得多。

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

当然，Greg的解决scheme要好得多。

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

以下对接受答案的解释可能对一些人有用：

当以二进制表示时，二的幂将总是看起来像1，其后n个零 ，其中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 ，再次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进行按位与（这是2的幂）和x - 1什么？

x的一个与x - 1的零点alignment， x所有零点都与x - 1的零点alignment，导致按位AND得到0.这就是我们如何得到上面提到的单行答案对。

进一步增加以上接受的答案的美丽 –

所以，我们现在有一个财产：

当我们从任何数字中减去1时，那么在二进制表示中，最右边的1将变成0，并且在最右边的1之前的所有的零现在将变成1

一个令人敬畏的使用这个属性是在找出 – 给定数字的二进制表示中有多less个1？ 对于一个给定的整数x来说，简短而又甜蜜的代码是：

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

从上面解释的概念可以certificate的数字的另一个方面是“每个正数可以表示为2的幂的和吗？ 。

是的，每个正数可以表示为2的幂的和。对于任何数字，取其二进制表示。例如：以501号码

 The binary of 501 is 111110101 Because 111110101 = 100000000 + 10000000 + 1000000 + 100000 + 1000 + 000 + 100 + 00 + 1 we have 501 = 256 + 128 + 64 + 32 + 16 + 0 + 4 + 0 + 1

查找给定的数字是2的幂。

 #include <math.h> int main(void) { int n,logval,powval; printf("Enter a number to find whether it is s power of 2\n"); scanf("%d",&n); logval=log(n)/log(2); powval=pow(2,logval); if(powval==n) printf("The number is a power of 2"); else printf("The number is not a power of 2"); getch(); return 0; }

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

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

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

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

如果x是2的幂，则其唯一的1位在位置n 。这意味着x – 1在位置n有一个0。想知道为什么，回想一下二进制减法是如何工作的。当从x减去1时，借位一直传播到位置n ; 现在，由于x没有与x – 1共同的1个位，所以x & (x – 1)是0， !(x & (x – 1))是真的。

如果一个数字只包含1个设定位，则它是2的乘方。我们可以使用这个属性和通用函数countSetBits来查找一个数是否是2的幂。

这是一个C ++程序：

 int countSetBits(int n) { int c = 0; while(n) { c += 1; n = n & (n-1); } return c; } bool isPowerOfTwo(int n) { return (countSetBits(n)==1); } int main() { int i, val[] = {0,1,2,3,4,5,15,16,22,32,38,64,70}; for(i=0; i<sizeof(val)/sizeof(val[0]); i++) printf("Num:%d\tSet Bits:%d\t is power of two: %d\n",val[i], countSetBits(val[i]), isPowerOfTwo(val[i])); return 0; }

我们不需要明确地检查0是否是2的幂，因为它也返回False。

OUTPUT

 Num:0 Set Bits:0 is power of two: 0 Num:1 Set Bits:1 is power of two: 1 Num:2 Set Bits:1 is power of two: 1 Num:3 Set Bits:2 is power of two: 0 Num:4 Set Bits:1 is power of two: 1 Num:5 Set Bits:2 is power of two: 0 Num:15 Set Bits:4 is power of two: 0 Num:16 Set Bits:1 is power of two: 1 Num:22 Set Bits:3 is power of two: 0 Num:32 Set Bits:1 is power of two: 1 Num:38 Set Bits:3 is power of two: 0 Num:64 Set Bits:1 is power of two: 1 Num:70 Set Bits:3 is power of two: 0

这里是我devise的另一种方法，在这种情况下使用| 而不是& ：

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

改进@ user134548的答案，无需位算术：

 public static bool IsPowerOfTwo(ulong n) { if (n % 2 != 0) return false; // is odd (can't be power of 2) double exp = Math.Log(n, 2); if (exp != Math.Floor(exp)) return false; // if exp is not integer, n can't be power return Math.Pow(2, exp) == n; }

这工作正常：

 IsPowerOfTwo(9223372036854775809)

例

 0000 0001 Yes 0001 0001 No

algorithm

使用位掩码，将NUMvariables除以二进制
IF R > 0 AND L > 0: Return FALSE
否则， NUM变成非零的那个
IF NUM = 1: Return TRUE
否则，请转到步骤1

复杂

Time〜O O(log(d))其中d是二进制数字的个数

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

对于任何2的幂，下面也成立。

N'（ – N）==Ñ

注：n = 0失败，需要检查
这个工程的原因是：
-n是n的二进制补码。 -n将比n翻转n的最右边的位的左边。对于2的幂，只有一个设定位。

这个程序在java中返回“true”，如果number是2的幂，如果它不是2的幂，则返回“false”

 // To check if the given number is power of 2 import java.util.Scanner; public class PowerOfTwo { int n; void solve() { while(true) { // To eleminate the odd numbers if((n%2)!= 0){ System.out.println("false"); break; } // Tracing the number back till 2 n = n/2; // 2/2 gives one so condition should be 1 if(n == 1) { System.out.println("true"); break; } } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); PowerOfTwo obj = new PowerOfTwo(); obj.n = in.nextInt(); obj.solve(); } } OUTPUT : 34 false 16 true

 public static IsPowerOf(int num, int powerOf) { var logOfNum = Math.Round(Math.Log(num, powerOf), 10); // Check for Integral. return (logOfNum % 1) == 0; }

如何检查一个数是否是2的幂

说明

进一步增加以上接受的答案的美丽 –

N'（ – N）==Ñ

智能进度条ETA计算

创build没有重复的随机数字序列

Firefox如何优化这个循环？

计算一组数字的所有子集

Redis使用的底层数据结构是什么？

有什么办法来检测像putjbtghguhjjjanikastring？

浮点除法器硬件实现细节

JavaScript：计算一个数字的第n个根

图像分割使用Mean Shift解释

find访问特定节点的图中的最短path