​​Объясните, что делает код ((n & (n — 1)) == 0) Вернемся к « | Тостер

​​Объясните, что делает код ((n & (n — 1)) == 0)

Вернемся к «истокам».
Что означает 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 является степенью двойки или равно нулю.

Тостер