Может кто-нибудь объяснить, почему это работает для подсчета набора битов в целое число без знака? - PullRequest
Новая
       62

Может кто-нибудь объяснить, почему это работает для подсчета набора битов в целое число без знака?

1 голос
/ 10 января 2020

Я видел этот код, называемый "Набор счетных битов, путь Брайана Кернигана" . Я озадачен тем, как "побитовое" и "целое" целое число с его декрементом работает для подсчета установленных бит, может кто-нибудь объяснить это? 

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

Ответы [ 3 ]

4 голосов
/ 10 января 2020

Каждый раз, когда подсчитывается один бит l oop, и один бит очищается (устанавливается в ноль).

Как это работает: когда вы вычитаете один из числа, вы меняете наименее значимое один бит до нуля, а еще менее значимые биты - один, хотя это не имеет значения. Это не имеет значения, потому что они равны нулю в значениях, которые вы уменьшаете, так что в любом случае они будут равны нулю после операции and. 

XXX1 => XXX0
XX10 => XX01
X100 => X011
etc.
3 голосов
/ 10 января 2020

Пусть A = a n-1 a n-2 ... a 1 a 0 быть числом, на которое мы хотим сосчитать биты, и k индексом самого правого бита на единицу.

Следовательно A = a n-1 a n-2 ... a k + 1 100 ... 0 = Ak + 2 k , где Ak = a n-1 a n-2 ... a k + 1 000 ... 0

As 2 k -1 = 000..0111..11, имеем A-1 = Ak + 2 k -1 = a n-1 a n-2 ... a k + 1 011 ... 11

Теперь выполните поразрядно & из A и A-1

a n-1 a n-2 ... a k + 1 100 ... 0 A
a n-1 a n-2 ... a k + 1 011 ... 1 A-1
a n-1 a n-2 ... a k + 1 000 ... 0 A & A-1 = Ak

То есть A & A-1 идентично A , за исключением того, что его самый правый бит был очищено, что подтверждает правильность метода.

3 голосов
/ 10 января 2020

Пошаговое руководство

Давайте пройдемся по l oop с примером: давайте установим v = 42, что составляет 0010 1010 в двоичном формате.

  • Первая итерация : c=0, v=42 (0010 1010). Теперь v-1 равно 41, что является 0010 1001 в двоичном виде. Давайте вычислим v & v-1: 

       0010 1010
 & 0010 1001
   .........
   0010 1000

    Теперь значение v&v-1 равно 0010 1000 в двоичном или 40 в десятичном виде. Это значение сохраняется в v.

  • Вторая итерация : c=1, v=40 (0010 1000). Теперь v-1 равно 39, что 0010 0111 в двоичном виде. Давайте вычислим v & v-1: 

       0010 1000
 & 0010 0111
   .........
   0010 0000

    Теперь значение v&v-1 равно 0010 0000, что составляет 32 в десятичном виде. Это значение сохраняется в v.

  • Третья итерация : c=2, v=32 (0010 0000). Теперь v-1 равно 31, что 0001 1111 в двоичном виде Давайте вычислим v & v-1: 

       0010 0000
 & 0001 1111
   .........
   0000 0000

    Теперь значение v&v-1 равно 0.

  • Четвертая итерация : c=3, v=0. l oop завершается . c содержит 3, которое является числом битов, установленным в 42.

Почему это работает

Вы можете видеть, что двоичное представление v-1 устанавливает младший значащий бит или младший бит (т. Е. Самый правый бит, равный 1) от 1 до 0, а все биты справа от младшего бита от 0 до 1.

Когда вы делаете поразрядно И между v и v-1, биты, оставшиеся от LSB, одинаковы в v и v-1, поэтому поразрядное И оставит их без изменений. Все биты справа от LSB (включая сам LSB) различны, поэтому результирующие биты будут равны 0.

В нашем первоначальном примере v=42 (0010 1010) LSB - это второй бит справа. Вы можете видеть, что v-1 имеет те же биты, что и 42, за исключением двух последних: 0 стал 1, а 1 стал 0.

Аналогично для v=40 (0010 1000) младший бит является четвертым битом из право. При вычислении v-1 (0010 0111) вы можете видеть, что левые четыре бита остаются неизменными, в то время как правые четыре бита стали инвертированными (нули стали единицами, а единицы стали нулями).

Следовательно, эффект v = v & v-1 заключается в установке наименьшего значения значительный бит от v до 0 и оставьте остальные без изменений. Когда все биты очищены таким образом, v равно 0, и мы посчитали все биты.

...