среда, 21 апреля 2010 г.

Волшебство 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 можно представить в виде:
А = bx*2x+bx-1*2x-1+...+b1*21+b0*20
где x - порядок бита в двоичном представлении числа,
а bx - сам бит в позиции x.
Значит и единицу можно представить следующим образом:
1=(1*20)=(1*21-1*20)=(1*22-1*21-1*20)...
Предположим, что b0=1, тогда:
A - 1 = (bx*2x+bx-1*2x-1+...+b1*21+1*20) - (1*20) = (bx*2x+bx-1*2x-1+...+b1*21+0*20)

Т.е. мы видим, что на место b0 подставился ноль, т.е. первый единичный бит справа был обнулен. (желтым я подсветил части выражения, которые взаимоуничтожаются из за разности знаков)
Если же первый единичный бит справа это b1 то можно сделать другую подстановку:
A - 1 = (bx*2x+bx-1*2x-1+...+1*21+0*20) - (1*21-1*20) = (bx*2x+bx-1*2x-1+...+1*21+0*20) - 1*21 + 1*20 = (bx*2x+bx-1*2x-1+...+0*21+1*20+0*20) = (bx*2x+bx-1*2x-1+...+0*21+1*20)

Теперь в позиции b1 ноль, зато в позиции b0 - единица.
Для предположения, когда первый единичный бит это b2:
A - 1 = (bx*2x+bx-1*2x-1+...+1*22+0*21+0*20) - (1*22-1*21-1*20) = (bx*2x+bx-1*2x-1+...+1*22+0*21+0*20) - 1*22+1*21+1*20 = (bx*2x+bx-1*2x-1+...+0*22+1*21+1*20)

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

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

Что произойдет с числами А и 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

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

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

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

Комментариев нет:

Отправить комментарий