Я смотрю на какой-то код, который должен быть тривиальным, но моя математика меня здесь не устраивает.
Здесь условие, которое проверяет, имеет ли число, если имеет значение 2, используя следующее:
if((num != 1) && (num & (num - 1))) { /* make num pow of 2 */ }
Мой вопрос в том, как использование побитового И между num и num-1 определяет, является ли число значением 2?
Любая степень 2 минус 1 - это все: (2 N - 1 = 111.... b)
2 = 2^1. 2-1 = 1 (1b)
4 = 2^2. 4-1 = 3 (11b)
8 = 2^3. 8-1 = 7 (111b)
Возьмите 8, например. 1000 и 0111 = 0000
Итак, это выражение проверяет, не является ли число числом не равным 2.
Ну, первый случай будет проверять на 2 0 == 1.
Для других случаев вступает в действие num & (num - 1):
Это высказывание, если вы берете какое-то число и маскируете биты с одного нижнего, вы получите один из двух случаев:
если число равно двум, то одно меньше приведет к двоичному числу, которое будет иметь только бит младшего разряда. Использование & ничего не будет делать.
0100 & (0100 - 1) → (0100 & 0011) → 0000если число уже не равно двум, то одно меньше не будет касаться самого высокого бита, поэтому результат будет, по крайней мере, наивысшей мощностью двух меньших, чем num.
Пример с 3: 0011 & (0011 - 1) → (0011 & 0010) → 0010
Пример с 13: 1101 & (1101 - 1) → (1101 & 1100) → 1100
Таким образом, фактическое выражение находит все, что не является силой двух, в том числе 2 0.
Ну,
если у вас есть X = 1000, тогда x-1 = 0111. И 1000 && 0111 - 0000.
Каждое число X, являющееся степенью 2, имеет x-1, у которого на позиции x есть нули. А побитовое и 0 и 1 всегда равно 0.
Если число x не является степенью двух, например 0110. x-1 равно 0101, а и дает 0100.
Для всех комбинаций в пределах 0000-1111 это приводит к
X X-1 X && X-1
0000 1111 0000
0001 0000 0000
0010 0001 0000
0011 0010 0010
0100 0011 0000
0101 0100 0100
0110 0101 0100
0111 0110 0110
1000 0111 0000
1001 1000 1000
1010 1001 1000
1011 1010 1010
1100 1011 1000
1101 1100 1100
1110 1101 1100
1111 1110 1110
И нет необходимости в отдельной проверке для 1.
Объяснено здесь красиво
Также указанное выражение считает, что 0 является степенью 2. Чтобы исправить это использование
!(x & (x - 1)) && x;.
Определяет, является ли целое число силой 2 или нет. Если (x & (x-1)) равно нулю, то это число равно 2.
Например, пусть x будет 8 (1000 в двоичном виде); то x-1= 7 (0111).
if 1000
& 0111
---------------
0000
C для демонстрации:
#include <stdio.h>
void main()
{
int a = 8;
if ((a&(a-1))==0)
{
printf("the bit is power of 2 \n");
}
else
{
printf("the bit is not power of 2\n");
}
}
Это выводит the bit is power of 2.
#include <stdio.h>
void main()
{
int a = 7;
if ((a&(a-1))==0)
{
printf("the bit is power of 2 \n");
}
else
{
printf("the bit is not power of 2\n");
}
}
Это выводит the bit is not power of 2.
Я предпочитаю такой подход, который опирается на два дополнения:
bool checkPowTwo(int x){
return (x & -x) == x;
}
После выполнения программы в C будет выяснено, является ли это число равным 2, а также найдите, какая степень 2, номер.
#include<stdio.h>
void main(void)
{
unsigned int a;
unsigned int count=0
unsigned int check=1;
unsigned int position=0;
unsigned int temp;
//get value of a
for(i=0;i<sizeof(int)*8;i++)//no of bits depend on size of integer on that machine
{
temp = a&(check << i);
if(temp)
{
position = i;
count++;
}
}
if(count == 1)
{
printf("%d is 2 to the power of %d",a,position);
}
else
{
printf("Not a power of 2");
}
}
Существуют и другие способы: если число равно 2, в двоичном формате будет установлен только 1 бит
например, 8 эквивалентен 0x1000, вычитая 1 из этого, получаем 0x0111.
Конечная операция с исходным номером (0x1000) дает 0.
если это так, это число равно 2
void IsPowerof2(int i)
{
if(!((i-1)&1))
{
printf("%d" is a power of 2, i);
}
}
другой способ может быть следующим: -
Если взять дополнение числа, которое является степенью 2,
например, дополнение 8 i.e 0x1000, получим 0x0111 и добавим 1 к нему, получим
то же число, если это так, это число равно 2
void IsPowerof2(int i)
{
if(((~1+1)&i) == 1)
{
printf("%d" is a power of 2,i):
}
}