Как посчитать количество установленных бит в 32-битном целом числе?

Question

8 битов, представляющих число 7, выглядят так:

00000111

Три бита установлены.

Что такое алгоритмы для определения количества установленных бит в 32-разрядном целом числе?

Answer 1

Как насчет преобразования целого числа в двоичную строку и подсчета их?

PHP решение:

substr_count( decbin($integer), '1' );

Answer 2

Я использую следующую функцию. Не проверял тесты, но это работает.

int msb(int num)
{
    int m = 0;
    for (int i = 16; i > 0; i = i>>1)
    {
        // debug(i, num, m);
        if(num>>i)
        {
            m += i;
            num>>=i;
        }
    }
    return m;
}

Answer 3

Я даю два алгоритма, чтобы ответить на вопрос,

  package countSetBitsInAnInteger;

    import java.util.Scanner;

    public class UsingLoop {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        try{
        System.out.println("Enter a integer number to check for set bits in it");
        int n = in.nextInt();
        System.out.println("Using while loop, we get the number of set bits as: "+usingLoop(n));
        System.out.println("Using Brain Kernighan's Algorithm, we get the number of set bits as: "+usingBrainKernighan(n));
        System.out.println("Using ");
        }
        finally{
        in.close();
        }
    }
    private static int usingBrainKernighan(int n) {
        int count = 0;
        while(n>0){
            n&=(n-1);
            count++;
        }
        return count;
    }/*
    Analysis:
        Time complexity = O(lgn)
        Space complexity = O(1)
    */
    private static int usingLoop(int n) {
        int count = 0;
        for(int i=0;i<32;i++){
            if((n&(1<<i))!=0)
                count++;
        }
        return count;
    }
    /*
    Analysis:
        Time Complexity = O(32) // Maybe the complexity is O(lgn)
        Space Complexity = O(1)
    */
    }

Answer 4

Это также будет нормально работать:

int ans = 0;
while(num){
 ans += (num &1);
 num = num >>1;
}    
return ans;

Answer 5

Вы можете сделать что-то вроде:

int countSetBits(int n)
{
    n=((n&0xAAAAAAAA)>>1) + (n&0x55555555);
    n=((n&0xCCCCCCCC)>>2) + (n&0x33333333);
    n=((n&0xF0F0F0F0)>>4) + (n&0x0F0F0F0F);
    n=((n&0xFF00FF00)>>8) + (n&0x00FF00FF);
    return n;
}

int main()
{
    int n=10;
    printf("Number of set bits: %d",countSetBits(n));
     return 0;
}

См. Здесь: http://ideone.com/JhwcX

Работу можно объяснить следующим образом:

Сначала все четные биты сдвигаются вправо и добавляются с нечетными битами для подсчета количества битов в группе из двух. Затем мы работаем в группе из двух, затем четыре и так далее ..

Answer 6

Я нигде не видел такого подхода:

int nbits(unsigned char v) {
    return ((((v - ((v >> 1) & 0x55)) * 0x1010101) & 0x30c00c03) * 0x10040041) >> 0x1c;
}

Он работает на байт, поэтому его нужно будет вызывать 4 раза для 32-разрядного целого числа. Он получен из бокового сложения, но использует два 32-битных умножения, чтобы уменьшить количество команд до 7.

Большинство современных компиляторов C оптимизируют эту функцию, используя инструкции SIMD (SSE2), когда становится ясно, что число запросов кратно 4, и оно становится вполне конкурентоспособным. Он переносим, ​​может быть определен как макрос или встроенная функция и не нуждается в таблицах данных.

Этот подход может быть расширен для работы с 16 битами одновременно с использованием 64-битных умножений. Однако происходит сбой, когда установлены все 16 битов, возвращая ноль, поэтому его можно использовать только при отсутствии входного значения 0xffff. Он также медленнее из-за 64-битных операций и плохо оптимизируется.

Answer 7

public class BinaryCounter {

private int N;

public BinaryCounter(int N) {
    this.N = N;
}

public static void main(String[] args) {

    BinaryCounter counter=new BinaryCounter(7);     
    System.out.println("Number of ones is "+ counter.count());

}

public int count(){
    if(N<=0) return 0;
    int counter=0;
    int K = 0;
    do{
        K = biggestPowerOfTwoSmallerThan(N);
        N = N-K;
        counter++;
    }while (N != 0);
    return counter;

}

private int biggestPowerOfTwoSmallerThan(int N) {
    if(N==1) return 1;
    for(int i=0;i<N;i++){
        if(Math.pow(2, i) > N){
            int power = i-1;
            return (int) Math.pow(2, power);
        }
    }
    return 0;
}
}

Answer 8

Вот что работает в PHP (все интергеры PHP имеют 32-битную подпись, то есть 31-битную):

function bits_population($nInteger)
{

    $nPop=0;
    while($nInteger)
    {
        $nInteger^=(1<<(floor(1+log($nInteger)/log(2))-1));
        $nPop++;
    }
    return $nPop;
}

Answer 9

Простой способ, который должен хорошо работать для небольшого количества битов, что-то вроде этого (для 4 битов в этом примере):

(i & 1) + (i & 2) / 2 + (i & 4) / 4 + (i & 8) / 8

Другие рекомендуют это для небольшого числа бит в качестве простого решения?

Answer 10

Простой алгоритм подсчета количества установленных бит:

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

Возьмите пример 11 (1011) и попробуйте вручную выполнить алгоритм. Должно вам очень помочь!