Уже несколько раз видел подобное:


В чём суть, я не понимаю.

Это сообщение отредактировал(а) leniviy - 30.6.2012, 16:42

x&(x-1) обнуляет крайний справа единичный бит. Если результат равен 0 - значит, x имеет вид 1000...000, т.е. представляет собой степень 2.

для нуля не будет работать

А Вы представьте себе, что будет, если исследуемое число есть степень двойки и не есть степень двойки.

Возьмём беззнаковое ненулевое число в побитовой записи: 1xxx...xxx, где xxx - какие-то биты.

Если это число - не степень двойки, то хотя бы один бит из xxx...xxx будет отличен от нуля, и при вычитании единицы из исследуемого числа получим число вида 1yyy...yyy, то есть самая старшая единичка остаётся на своём месте. Следовательно, в этом случае a & (a-1) всегда даст ненулевой результат, какими бы не были xxx...xxx.

Если наше число - степень двойки, то оно в побитовой записи имеет вид 1000...000, при вычитании 1 получаем 0111...111. При этом старший бит обнуляется, а там где возникли единичные биты, у оригинального числа - нули. В результате, a & (a-1) даст 0.

Предлагаю самостоятельно разобраться, что будет, если взять нулевое число или знаковое число с отрицательным значением  

Это сообщение отредактировал(а) feodorv - 30.6.2012, 18:39

Спасибо, познавательно 

Можете посмотреть книгу - Генри Уоррен, Алгоритмические трюки для программистов, там много такого рода интересностей, которые иногда могут дать существенный прирост производительности.