Количество бит в массиве

Question

Я знаю, что для подсчета количества установленных бит в числе, следующий код может сделать это:

int  t; // in which we want count how many bits are set
        // for instance, in 3 (011), there are 2 bits set
int count=0;
while (t > 0) {
    t &= (t - 1);
    count++;
}

Теперь пример массива:

int x[] = {3, 5, 6, 8, 9, 7};

У меня есть следующий код:

int sum = 0;
int count;
for (int i = 0; i < x.length; i++) {
    count = 0;
    while (x[i] > 0){
        x[i] &= (x[i] - 1);
        count++;
    }
    sum += count;
}

Однако это не работает. Что не так?

Answer 1

Ваш код работает нормально для меня, за исключением того, что длина была неопределена - возможно, потому что вы использовали Java, а не C, как я сначала догадался. Во всяком случае, я получил это работает в C:

#include <stdio.h>

int main()
{
    int x[]={3,5,6,8,9,7};
    int sum=0;
    int count;
    for (int i=0;i<6;i++){
        count=0;
        while (x[i]>0){
            x[i]&=(x[i]-1);
            count++;
        }
        sum+=count;
    }

   printf("%d\n", sum);
}

Выход:

12

Более простой способ - сдвиг битов в цикле и подсчет количества битов по мере их прохождения.

count = 0;
while (t)
{
    count += t & 1;
    t >>= 1;
}

На этой странице показаны некоторые более продвинутые алгоритмы, включая использование таблицы поиска или умного параллельного алгоритма. Метод, который вы используете, на этой странице называется «путь Брайана Кернигана».

Вы также можете увидеть, что предоставляет ваш компилятор, например ::

int __builtin_popcount (unsigned int x);

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