оцените, является ли число целочисленным питанием 4
Следующая функция, как утверждают, оценивает, является ли число целочисленным питанием 4. Я действительно не совсем понимаю, как это работает?
bool fn(unsigned int x)
{
if ( x == 0 ) return false;
if ( x & (x - 1) ) return false;
return x & 0x55555555;
}
2 ответа
Первое условие исключает 0, который, очевидно, не является степенью 4, но неправильно прошел бы следующие два теста. (РЕДАКТИРОВАТЬ: Нет, как указано. Первый тест избыточен.)
Следующий - хороший трюк: он возвращает истину тогда и только тогда, когда число является степенью двойки. Степень двойки характеризуется наличием только одного установленного бита. Число с одним установленным битом минус один приводит к числу со всеми битами, предшествующими установленному биту (т. Е. 0x1000 минус один - это 0x0111). И эти два числа, и вы получите 0. В любом другом случае (т.е. не в степени двойки) будет хотя бы один перекрывающийся бит.
Итак, на данный момент мы знаем, что это степень 2.
x & 0x55555555 возвращает ненулевое значение (= истина), если установлен какой-либо четный бит (бит 0, бит 2, бит 4, бит 6 и т. Д.). Это означает, что его мощность равна 4. (т.е. 2 не проходит, но 4 проходит, 8 не проходит, 16 проходов и т. Д.).
Каждая сила 4 должна быть в виде 1, за которой следует четное количество нулей (двоичное представление): 100...00:
100 = 4
10000 = 16
1000000 = 64
Первый тест ("если") очевиден.
При вычитании 1 из числа вида XY100...00 получается XY011...11. Итак, второй тест проверяет, есть ли в числе более одного бита "1" (XY в данном примере).
Последний тест проверяет, находится ли эта единственная "1" в правильной позиции, т.е. бит #2,4,6 и т.д. Если нет, то маскирование (&) вернет ненулевой результат.