оценить, является ли число целой степенью 4

Question

Следующая функция предназначена для оценки того, является ли число целой степенью 4. Я не совсем понимаю, как это работает?

bool fn(unsigned int x)
{
if ( x == 0 ) return false;
if ( x & (x - 1) ) return false;
return x & 0x55555555;
}

Answer 1

Первое условие исключает 0, что, очевидно, не является степенью 4, но некорректно пройдет следующие два теста. (РЕДАКТИРОВАТЬ: Нет, это не так, как указано. Первый тест избыточен.)

Следующий хороший прием: он возвращает истину тогда и только тогда, когда число является степенью 2. Степень два характеризуется наличием только одного установленного бита. Число с одним установленным битом минус один приводит к числу со всеми битами, предшествующими этому установленному биту (то есть 0x1000 минус один равен 0x0111). И эти два числа, и вы получите 0. В любом другом случае (т.е. не в степени 2), будет хотя бы один бит, который перекрывается.

Итак, на данный момент мы знаем, что это степень 2.

x & 0x55555555 возвращает ненулевое значение (= true), если установлен любой четный бит (бит 0, бит 2, бит 4, бит 6 и т. Д.). Это означает, что это степень 4. (т.е. 2 не проходит, но 4 проходит, 8 не проходит, 16 проходов и т. Д.).

Answer 2

Каждая степень 4 должна быть в форме 1, за которым следует четное число нулей (двоичное представление): 100 ... 00 :

100 = 4

10000 = 16

1000000 = 64

1. 1-й тест ("если") очевиден.

2. Вычитая 1 из числа вида XY100 ... 00 , вы получаете XY011 ... 11 .Итак, 2-й тест проверяет, есть ли в номере более одного бита «1» ( XY в этом примере).

3. Последний тест проверяет,одиночный «1» находится в правильной позиции, т. е. бит № 2,4,6 и т. д. Если это не так, маскировка (&) вернет ненулевой результат.

Answer 3

Ниже решение работает на 2,4,16 мощности проверки.

  public static boolean isPowerOf(int a, int b)
  {         
     while(b!=0 && (a^b)!=0)
     {              
        b = b << 1;     
     }
   return (b!=0)?true:false;   
  }

isPowerOf(4,2) > true
isPowerOf(8,2) > true
isPowerOf(8,3) > false
isPowerOf(16,4) > true