Що перевіряє умова ((n & (n–1) == 0)

Задача

Що перевіряє умова ((n & (n – 1) == 0) для цілих чисел?

Рішення

Для будь-яких чисел A та B операція A & B даватиме 0 якщо в них не співпадає жоден біт.

За яких умов у n та (n – 1) не співпадатиме жоден біт? Таке можливо тільки коли у n встановлено лише один біт. Наприклад:

n n – 1 n & (n – 1)
1 (00000001) 0 (00000000) 0
2 (00000010) 1 (00000001) 0
3 (00000011) 2 (00000010) 2
4 (00000100) 3 (00000011) 0
5 (00000101) 4 (00000100) 4
8 (00001000) 7 (00000111) 0
9 (00001001) 8 (00001000) 8

 

Як бачимо результат операції є нульовим лише коли встановлено один біт числа, або іншими словами коли число є ступенем двійки.

4 коментаря для “Що перевіряє умова ((n & (n–1) == 0)”

Залишити відповідь