оценить, является ли число целым числом 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, но неправильно проходит следующие два теста. (EDIT: Нет, это было бы не так, как указано. Первый тест является избыточным.)

Следующий приятный трюк: он возвращает true тогда и только тогда, когда это число равно 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 и т. Д. Если это не так, маскировка (&) вернет ненулевой результат.