Объясните, что делает код ((n & (n - 1)) == 0)
88К открытий88К показов
Вернемся к «истокам».
Что означает A & B == 0
?
Это означает, что А и B не содержат на одних и тех же позициях единичных битов. Если n & (n - 1) == 0
, то n
и n - 1
не имеют общих единиц.
На что похоже n - 1
(по сравнению с n
)?
Попытайтесь проделать вычитание вручную (в двоичной или десятично системах).
Что произойдет?
Когда вы отнимаете единицу, посмотрите на младший бит. 1 вы замените на 0. Но если там стоит 0, то вы должны заимствовать из старшего бита. Вы изменяете каждый бит с 0 на 1, пока не дойдете до 1. Затем вы инвертируете единицу в ноль, — все готово.
Таким образом, можно сказать, что n - 1
будет совпадать с n
в каких-то битах, за исключением того, что младшим нулям в n
соответствуют единицы в n - 1
, а последний единичный бит в n
становится нулем в n - 1
.
Что значит n & (n - 1) == 0
?
n
и n - 1
не содержат общих единиц. Предположим, они имеют вид:
n = abcde1000
n - 1 = abcde0111
abcde
должны быть нулевыми битами, то есть n
имеет вид 000001000
. Таким образом, значение n
– степень двойки.
Итак, наш ответ: логическое выражение ((n & (n-1)) == 0)
истинно, если n
является степенью двойки или равно нулю.
Разбор взят из книги Гейл Л. Макдауэлл «Cracking the Coding Interview» (есть в переводе).
88К открытий88К показов