Волшебство n &= (n - 1);

Как всегда уважаемый Александр радует интересными вопросами. На этот раз это формализованное доказательство того, что следующая функция вернет количество единиц в числе переведенном в двоичную систему:

int bitcount (unsigned int n)  {
   int count = 0 ;
   while (n)  {
      count++ ;
      n &= (n - 1) ;
   }
   return count ;
}

Т.е. фактически количество итераций цикла, равно количеству единичных (не нулевых) бит.

Хоть я и не математик, но попробуем внимательнее взглянуть на код...

Выполнение цикла будет прервано когда n станет равным нулю. Я считаю что формула
n &= (n - 1);
вызванная в цикле, убирает из n единицы (в двоичном представлении) до тех пор пока их совсем не останется.

Попробую доказать.

Для начала рассмотрим операцию n-1. Что будет происходить с числом в двоичном представлении? При вычитании единицы с числом в двоичном виде произойдет следующее: первый с правого края единичный бит будет обнулен, а предшествующие ему нули инвертированы. Вот так:
xx...xx100...00 - 1 = xx...xx011...11
где x -произвольные биты в левой части числа.
Это можно доказать следующим образом (если это нужно). Любое число A можно представить в виде:
А = b_x*2^x+b_x-1*2^x-1+...+b₁*2¹+b₀*2⁰
где x - порядок бита в двоичном представлении числа,
а b_x - сам бит в позиции x.
Значит и единицу можно представить следующим образом:
1=(1*2⁰)=(1*2¹-1*2⁰)=(1*2²-1*2¹-1*2⁰)...
Предположим, что b₀=1, тогда:
A - 1 = (b_x*2^x+b_x-1*2^x-1+...+b₁*2¹+1*2⁰) - (1*2⁰) = (b_x*2^x+b_x-1*2^x-1+...+b₁*2¹+0*2⁰)

Т.е. мы видим, что на место b₀ подставился ноль, т.е. первый единичный бит справа был обнулен. (желтым я подсветил части выражения, которые взаимоуничтожаются из за разности знаков)
Если же первый единичный бит справа это b₁ то можно сделать другую подстановку:
A - 1 = (b_x*2^x+b_x-1*2^x-1+...+1*2¹+0*2⁰) - (1*2¹-1*2⁰) = (b_x*2^x+b_x-1*2^x-1+...+1*2¹+0*2⁰) - 1*2¹ + 1*2⁰ = (b_x*2^x+b_x-1*2^x-1+...+0*2¹+1*2⁰+0*2⁰) = (b_x*2^x+b_x-1*2^x-1+...+0*2¹+1*2⁰)

Теперь в позиции b₁ ноль, зато в позиции b₀ - единица.
Для предположения, когда первый единичный бит это b₂:
A - 1 = (b_x*2^x+b_x-1*2^x-1+...+1*2²+0*2¹+0*2⁰) - (1*2²-1*2¹-1*2⁰) = (b_x*2^x+b_x-1*2^x-1+...+1*2²+0*2¹+0*2⁰) - 1*2²+1*2¹+1*2⁰ = (b_x*2^x+b_x-1*2^x-1+...+0*2²+1*2¹+1*2⁰)

И так далее и тому подобное.
Не знаю, считаются ли мои корявые рассуждения доказательством у настоящих математиков, но отсюда во-всяком случае понятно что происходит: в битовом представлении числа самая правая единица превращается в ноль, а все остальное за ней превращается в единицы.

Следующая операция это побитовый И.

Что произойдет с числами А и B когда с ним будет произведена побитовая операция И, если мы знаем, что:
1. B = A - 1, а значит, что
2. До бита с номером Y эти числа совпадают.
3. Бит с номером Y - самая правая единица в числе A, за которым идут нули.
4. Сам бит с номером Y в числе A равен единице, а в B равен нулю и
5. далее в числе A все последующие символы равны нулю, а в B - единице.

Очевидно, что часть числа ДО бита с номером Y останется неизменной, так как a&a=a.
Бит с номером Y будет обнулен и так же будут обнулены все последующие за ним, так как там один из операндов равен нулю.

  xx...xx100...00 
& xx...xx011...11 =

  --------------- 
  xx...xx000...00

Т.е. мы видим, что в результате этой операции самый правый единичный бит в байте превратился в ноль.

Мы сможем повторять эту операцию и результат не будет равен нулю до тех пор, пока последний единичный бит не станет нулевым. Очевидно, что количество итераций и будет равно количеству единиц в числе.

Извините, если мое описание немного сумбурное, буду благодарен за подсказки о том "как правильно".