Найдите, если число является степенью двух без функции математики или функции журнала

Я хочу найти, если введенный пользователем номер имеет силу два или нет.

Мой код не работает.

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 и т.д.

Ответ 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, тогда его двоичное представление будет содержать несколько других 1s в дополнение к ведущему 1, что означает, что оба n и n - 1 будут иметь один и тот же ведущий 1 бит (поскольку вычитание 1 не может отключить этот бит, если в двоичном представлении есть еще один). Следовательно, операция & не может произвести 0, если n не является степенью 2, так как & с двумя ведущими битами n и n - 1 будет производить 1 сам по себе. Это, конечно, предполагает, что n положительно.

Это также объясняется в "Быстрый алгоритм, чтобы проверить, является ли положительное число силой два" в Википедии.

Быстрая проверка работоспособности:

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

Ответ 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, оставьте его и продолжайте, но с этого момента, инвертируйте все биты. Я попытался объяснить это более здесь.

Ответ 3

double input = 22;

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

return input == 2;

Продолжайте делиться на 2, пока не достигнете 1 или нечетного числа. Если он достигает 1, он имеет мощность 2, иначе это не так.

Ответ 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)

Ответ 5

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

Ответ 6

Очень простое решение.

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