查找数字是否为2的幂,没有数学函数或日志函数

Question

我想查找用户输入的数字是否为2的幂.

我的代码不起作用.

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

让我知道如何才能找到两个数字的力量.
例如,8是2的幂
.22 不是 2的幂,等等.

Answer 1

您可以n使用类似的方法测试正整数是否为2的幂

(n & (n - 1)) == 0

如果n可以是非正数(即负数或零),则应使用

(n > 0) && ((n & (n - 1)) == 0)

如果n真的是2的幂,那么在二进制中它看起来像:

10000000...

所以n - 1看起来像

01111111...

当我们按位和它们时:

  10000000...
& 01111111...
  -----------
  00000000...

现在,如果n 不是 2的幂,那么它的二进制表示除了前导1之外还会有一些其他的1,这意味着两个n并且n - 1将具有相同的前导1位(因为减去1不可能关闭此位,如果某处的二进制表示中有另外1个).因此,如果不是2的幂,则&操作不能产生,因为两个前导位并且将产生其本身.这当然假设是积极的.0n&nn - 11n

维基百科上的"快速算法检查正数是2的幂"也解释了这一点.

快速健全检查:

for (int i = 1; i <= 100; i++) {
    if ((i & (i - 1)) == 0)
        System.out.println(i);
}

1
2
4
8
16
32
64

Answer 2

你可以使用bitwise AND (&) operator:

return (num & -num) == num

为什么会这样？

考虑数字8,它是二进制的(假设是32位)？

0000 0000 0000 0000 0000 0000 0000 1000

现在让我们看看-8是如何表示的？¹

1111 1111 1111 1111 1111 1111 1111 1000

最后..让我们计算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    ¯\_(?)_/¯

现在让我们再举一个例子,让我们说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  ¯\_(?_?)_/¯

正如@arshajii所提到的,想想如果num为零将会发生什么......我将为你留下解决方案:)

¹记住如何计算的好方法:从最右边的位开始,对于你看到的每个0,不要改变它,当你看到1时,离开并继续,但从现在开始,反转所有位.我试着在这里解释一下.

Answer 3

double input = 22;

while(((input != 2) && input % 2 == 0) || input == 1) {
 input = input /2;
}

return input == 2;

继续除以2,直到达到1或奇数.如果它达到1则为2的幂,否则不是.

Answer 4

直截了当的解决方案:

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

当然,这并不像其他一些比特巧妙的解决方案(它确实非常聪明)那样最优,但是很容易看出它是如何工作的,并且验证它在你脑海中起作用.

对于输入4,我们得到:

n = 4 (0x100)
run loop
n = 2 (0x10)
run loop
n = 1 (0x1)
return true

对于无效输入5,我们得到:

n = 5 (0x101)
return false (0x101 & 0x1 => 0x1, which is truthy)