Объясните, что делает код ((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 является степенью двойки или равно нулю.

Разбор взят из книги Гейл Л. Макдауэлл «Cracking the Coding Interview» (есть в переводе).