<分区>
Possible Duplicate:
How to check if a number is a power of 2
找到给定数字“n”的最快方法可以表示为 2^m
例如:16= 2^4
天真的解决方案:将给定数字除以 2，直到余数变为 0(如果成功)或小于二(如果不成功)
谁能告诉我另一种最快的计算方法是什么？
标签 algorithm
<分区>
Possible Duplicate:
How to check if a number is a power of 2
找到给定数字“n”的最快方法可以表示为 2^m
例如:16= 2^4
天真的解决方案:将给定数字除以 2，直到余数变为 0(如果成功)或小于二(如果不成功)
谁能告诉我另一种最快的计算方法是什么？
最佳答案
最快的方法:
if (n != 0 && (n & (n - 1)) == 0)
如果数字是 2 的幂，它将用二进制表示为 1 后跟 m 个零。减去1后就是m个。例如取m=4(n=16)
10000 binary = 16 decimal
01111 binary = 15 decimal
执行按位“与”，您将得到 0。因此在这种情况下它会给出正确的结果。
现在假设对于某些 m，n 不正好是 2m。然后从中减去 1 不会影响最高位...所以当你“和”在一起时 n 和 n-1 最高位位仍将被设置，因此结果不会为 0。因此也没有误报。
编辑:我最初没有 n != 0 测试...如果 n 为零，则 n & anything 将为零，因此你得到误报。
关于algorithm - 找到给定数字 'n' 的最快方法可以绝对表示为 2^m，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3488809/