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

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

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

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, etc..

6 60
javascript

6 ответов:

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

это также объясняется в "быстрый алгоритм, чтобы проверить, если положительное число-это мощность двух" на Википедии.

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

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

1
2
4
8
16
32
64
197

можно использовать bitwise AND (&) operator:

return (num & -num) == num

почему это работает?

рассмотрим число 8, что это в двоичном формате (предполагая 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    ¯\_(ツ)_/¯

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

91
double input = 22;

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

return input == 2;

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

7

простое решение:

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

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

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