Найдите, если число является степенью двух без функции математики или функции журнала
Я хочу найти, если введенный пользователем номер имеет силу два или нет.
Мой код не работает.
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);
}
1
2
4
8
16
32
64
Ответ 2
Вы можете использовать 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, оставьте его и продолжайте, но с этого момента, инвертируйте все биты. Я попытался объяснить это более здесь.
Ответ 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")
