62

ユーザーが入力した数値が 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 の累乗で
はありません。

4

6 に答える 6

203

次のようなもので、正の整数nが 2 のべき乗であるかどうかをテストできます。

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

n非正（つまり、負またはゼロ）になる可能性がある場合は、使用する必要があります

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

が本当に 2 の累乗である場合n、バイナリでは次のようになります。

10000000...

ようn - 1に見える

01111111...

そして、それらをビットごとに ANDすると、次のようになります。

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

が 2 のべき乗でn ない場合、そのバイナリ表現には先頭の 1 に加えて他の 1 が含まれます。これは、nとの両方n - 1が同じ先頭の 1 ビットを持つことを意味します (バイナリ表現のどこかに別の 1 があります)。したがって、が 2 の累乗でない場合、との先頭の 2 ビットを ing するとそれ自体で生成されるため、&演算は生成できません。もちろん、これはそれが正であることを前提としています。0n&nn - 11n

これは、Wikipediaの「正の数が 2 のべき乗であるかどうかを確認する高速アルゴリズム」でも説明されています。

クイック サニティ チェック:

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

1
2
4
8
16
32
64
于 2013-10-15T14:04:46.457 に答える
96

以下を使用できますbitwise AND (&) operator。

return (num & -num) == num

なぜこれが機能するのですか？

数字の 8 を考えてみましょう。2 進法 (32 ビットと仮定) は何ですか? 

0000 0000 0000 0000 0000 0000 0000 1000

では、-8 がどのように表されるか見てみましょう。1

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    ¯\_(ツ)_/¯

ここで、2 の累乗で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がゼロの場合に何が起こるか考えてみてください。解決策はお任せします :)

1それを計算する方法を覚えておく良い方法: 右端のビットから開始し、0 が表示されるたびに変更しないでください。1 が表示されたら、そのままにして続行しますが、それ以降はすべてのビットを反転します。ここでこれをもっと説明しようとしました。

于 2013-10-15T14:05:31.600 に答える
7 
double input = 22;

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

return input == 2;

1 か奇数になるまで 2 で割ります。1 に達した場合は 2 のべき乗であり、それ以外の場合はそうではありません。

于 2013-10-15T14:06:06.000 に答える
5

簡単な解決策：

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)
于 2013-10-15T19:20:49.790 に答える
0 
   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;
        }
于 2014-07-06T18:51:07.243 に答える
-3

非常に簡単な解決策です。

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")
于 2013-12-11T08:33:24.250 に答える