Java 在没有数学函数或对数函数的情况下查找数字是否为 2 的幂
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19383248/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find if a number is a power of two without math function or log function
提问by sam
I want to find if a user entered number is a power of two or not.
我想知道用户输入的数字是否是 2 的幂。
My code doesn't work.
我的代码不起作用。
public class power_of_two
{
public static void main(String args[])
{
Scanner in=new Scanner(System.in);
System.out.println("Enter the number : ");
int num = in.nextInt();
int other = 1;
if(((~num) & 1) == 1)
{
System.out.println("The number is a power of two");
}
else
{
System.out.println("The number is a NOT A power of two");
}
}
}
Let me know how can I find the power of two number.
For example 8 is a power of 2.
22 is nota power of 2, etc..
让我知道如何找到两个数的幂。
例如，8 是 2 的幂
。22不是2 的幂等。
采纳答案by arshajii
You can test if a positive integer nis a power of 2 with something like
您可以测试一个正整数n是否是 2 的幂，例如
(n & (n - 1)) == 0
If ncan be non-positive (i.e. negative or zero) you should use
如果n可以是非正数（即负数或零），您应该使用
(n > 0) && ((n & (n - 1)) == 0)
If nis truly a power of 2, then in binary it will look like:
如果n确实是 2 的幂，那么在二进制中它看起来像：
10000000...
so n - 1looks like
所以n - 1看起来像
01111111...
and when we bitwise-ANDthem:
当我们按位与它们时：
10000000...
& 01111111...
-----------
00000000...
Now, if nisn'ta power of 2, then its binary representation will have some other 1s in addition to the leading 1, which means that both nand n - 1will have the same leading 1 bit (since subtracting 1 cannot possibly turn off this bit if there is another 1 in the binary representation somewhere). Hence the &operation cannot produce 0if nis not a power of 2, since &ing the two leading bits of nand n - 1will produce 1in and of itself. This of course assumes that nis positive.
现在，如果n不是2 的幂，那么它的二进制表示除了前导 1 之外还有一些其他的 1，这意味着两者n和n - 1将具有相同的前导 1 位（因为减 1 不可能关闭该位，如果某处的二进制表示中还有另一个 1）。因此，&操作不能产生0如果n不是2的幂，因为&荷兰国际集团的两个前导比特n和n - 1将产生1在其本身。这当然假设这n是积极的。
This is also explained in "Fast algorithm to check if a positive number is a power of two"on Wikipedia.
这也在维基百科上的“检查正数是否为 2 的幂的快速算法”中进行了解释。
Quick sanity check:
快速健全性检查：
for (int i = 1; i <= 100; i++) {
if ((i & (i - 1)) == 0)
System.out.println(i);
}
1 2 4 8 16 32 64
回答by Maroun
You can use the bitwise AND (&) operator:
您可以使用bitwise AND (&) operator：
return (num & -num) == num
Why this works?
为什么这有效？
Consider the number 8, what it is in binary (assuming 32-bits)?
考虑数字 8，它是什么二进制（假设是 32 位）？
0000 0000 0000 0000 0000 0000 0000 1000
Now let's see how -8 is represented? 1
现在让我们看看 -8 是如何表示的？1
1111 1111 1111 1111 1111 1111 1111 1000
Finally.. let's calculate 8 & -8:
最后..让我们计算一下8 & -8：
0000 0000 0000 0000 0000 0000 0000 1000 8
↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ &
1111 1111 1111 1111 1111 1111 1111 1000 -8
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 1000 8 ˉ\_(ツ)_/ˉ
Now let's take another example, let's say 7, which is notpower of two.
现在让我们再举一个例子，比方说7，这不是二的幂。
0000 0000 0000 0000 0000 0000 0000 0111 7
↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ &
1111 1111 1111 1111 1111 1111 1111 1001 -7
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0001 != 7 ˉ\_(?_?)_/ˉ
As mentioned by @arshajii, think what will happen if numis zero.. I'll leave the solution for you :)
正如@arshajii 所提到的，想想如果num为零会发生什么......我会为你留下解决方案:)
1A good way to remember how to calculate that: Begin from the rightmost bit, for each 0 you see, don't change it, when you see 1, leave it and proceed, but from now on, invert all bits. I tried to explain this more here.
1记住如何计算的好方法：从最右边的位开始，对于您看到的每个 0，不要更改它，当您看到 1 时，离开并继续，但从现在开始，反转所有位。我试图在这里解释更多。
回答by Jeroen Vannevel
double input = 22;
while(((input != 2) && input % 2 == 0) || input == 1) {
input = input /2;
}
return input == 2;
Keep dividing it by 2 until you reach 1 or an odd number. If it reaches 1 it's a power of 2, otherwise it isn't.
继续除以 2，直到达到 1 或奇数。如果达到 1，则是 2 的幂，否则不是。
回答by crazy2be
The straightforward solution:
直截了当的解决方案：
bool isPowerOfTwo(int n) {
// All values < 1 cannot be (positive, at least) powers of two.
if (n < 1) return false;
// Keep shifting bits.
while (n > 1) {
// Since n > 1, the low bit set means at least two bits must
// be set, making n no longer a power of two.
if (n & 0x1) return false;
// Throw away the bottom (zero) bit.
n >>= 1;
}
// Only one bit was set, therefore, n is a power of two.
return true;
}
Of course, this is not as optimal as some of the other bit-trickery solutions (which are indeed quite clever), but it's very easy to see how it works, and verify it works in your head.
当然，这并不像其他一些比特技巧解决方案（它们确实很聪明）那样最佳，但是很容易看到它是如何工作的，并在您的脑海中验证它是否有效。
For the input 4, we get:
对于输入4，我们得到：
n = 4 (0x100)
run loop
n = 2 (0x10)
run loop
n = 1 (0x1)
return true
For an invalid input, like 5, we get:
对于无效输入，例如5，我们得到：
n = 5 (0x101)
return false (0x101 & 0x1 => 0x1, which is truthy)
回答by Pankaj Goyal
A very simple solution.
一个非常简单的解决方案。
int n = 8; // any integer and you can take it from user also
for(;n>0;n++){
if(n%2 != 0) {
System.out.println("not a power of two")
return;
} // if ends here
n = n/2;
}// for ends here
System.out.println("power of two")
回答by Kranti123
public boolean isPowerOfTwo(int n){
boolean isPower=false;
int temp=n;
while(temp>=2){
if(temp%2==0){
isPower=true;
}else{
isPower=false;
break;
}
temp=temp/2;
}
if(isPower){
System.out.println("power of 2");
}else{
System.out.println("not power of 2");
}
return isPower;
}
