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

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

811 голосов
/ 20 сентября 2008

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

00000111

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

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

Ответы [ 51 ]

3 голосов
/ 23 августа 2017

что вы можете сделать, это

while(n){ n=n&(n-1); count++; }

логика, стоящая за этим, состоит в том, что биты n-1 инвертированы из крайнего правого установленного бита n. если n = 6, т.е. 110 тогда 5 равно 101, биты инвертированы из самого правого установленного бита n. поэтому, если мы и эти два мы сделаем самый правый бит 0 в каждой итерации и всегда перейдем к следующему крайнему правому установленному биту. Считаем установленный бит. Худшая временная сложность будет O (logn), когда каждый бит установлен.

2 голосов
/ 26 апреля 2012

Лично я использую это: 

  public static int myBitCount(long L){
      int count = 0;
      while (L != 0) {
         count++;
         L ^= L & -L; 
      }
      return count;
  }
1 голос
/ 05 октября 2016

В Java 8 или 9 просто вызовите Integer.bitCount.

1 голос
/ 12 февраля 2015 
int countBits(int x)
{
    int n = 0;
    if (x) do n++;
           while(x=x&(x-1));
    return n;
}

Или также: 

int countBits(int x) { return (x)? 1+countBits(x&(x-1)): 0; }
1 голос
/ 07 июня 2014 
int bitcount(unsigned int n)
{ 
      int count=0;
      while(n)
      {
           count += n & 0x1u;
           n >>= 1;
      }
      return  count;
 }

Повторный подсчет выполняется во времени, пропорциональном общему количеству битов. Он просто перебирает все биты, заканчиваясь немного раньше из-за условия while. Полезно, если 1 или S установлены биты разреженные и среди младшие биты .

1 голос
/ 27 ноября 2013

Вот решение, которое до сих пор не упоминалось, с использованием битовых полей. Следующая программа подсчитывает установленные биты в массиве из 100000000 16-битных целых чисел, используя 4 различных метода. Результаты синхронизации приведены в скобках (в MacOSX, с gcc -O3): 

#include <stdio.h>
#include <stdlib.h>

#define LENGTH 100000000

typedef struct {
    unsigned char bit0 : 1;
    unsigned char bit1 : 1;
    unsigned char bit2 : 1;
    unsigned char bit3 : 1;
    unsigned char bit4 : 1;
    unsigned char bit5 : 1;
    unsigned char bit6 : 1;
    unsigned char bit7 : 1;
} bits;

unsigned char sum_bits(const unsigned char x) {
    const bits *b = (const bits*) &x;
    return b->bit0 + b->bit1 + b->bit2 + b->bit3 \
         + b->bit4 + b->bit5 + b->bit6 + b->bit7;
}

int NumberOfSetBits(int i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

#define out(s) \
    printf("bits set: %lu\nbits counted: %lu\n", 8*LENGTH*sizeof(short)*3/4, s);

int main(int argc, char **argv) {
    unsigned long i, s;
    unsigned short *x = malloc(LENGTH*sizeof(short));
    unsigned char lut[65536], *p;
    unsigned short *ps;
    int *pi;

    /* set 3/4 of the bits */
    for (i=0; i<LENGTH; ++i)
        x[i] = 0xFFF0;

    /* sum_bits (1.772s) */
    for (i=LENGTH*sizeof(short), p=(unsigned char*) x, s=0; i--; s+=sum_bits(*p++));
    out(s);

    /* NumberOfSetBits (0.404s) */
    for (i=LENGTH*sizeof(short)/sizeof(int), pi=(int*)x, s=0; i--; s+=NumberOfSetBits(*pi++));
    out(s);

    /* populate lookup table */
    for (i=0, p=(unsigned char*) &i; i<sizeof(lut); ++i)
        lut[i] = sum_bits(p[0]) + sum_bits(p[1]);

    /* 256-bytes lookup table (0.317s) */
    for (i=LENGTH*sizeof(short), p=(unsigned char*) x, s=0; i--; s+=lut[*p++]);
    out(s);

    /* 65536-bytes lookup table (0.250s) */
    for (i=LENGTH, ps=x, s=0; i--; s+=lut[*ps++]);
    out(s);

    free(x);
    return 0;
}

Хотя версия битового поля очень удобочитаема, результаты синхронизации показывают, что она в 4 раза медленнее, чем NumberOfSetBits(). Реализации на основе таблиц поиска по-прежнему немного быстрее, в частности, с таблицей 65 КБ.

1 голос
/ 15 июня 2017

Вы можете использовать встроенную функцию с именем __builtin_popcount (). В C ++ нет __builtin_popcount, но это встроенная функция компилятора GCC. Эта функция возвращает номер установленного бита в целом числе. 

int __builtin_popcount (unsigned int x);

Ссылка: Битовые трюки

1 голос
/ 19 ноября 2015

Другой алгоритм определения веса Хэмминга, если вы используете процессор с BMI2 

the_weight=__tzcnt_u64(~_pext_u64(data[i],data[i]));

Веселись!

0 голосов
/ 07 апреля 2012 
// How about the following:
public int CountBits(int value)
{
    int count = 0;
    while (value > 0)
    {
        if (value & 1)
            count++;
        value <<= 1;
    }
    return count;
}
0 голосов
/ 24 февраля 2012

Вот пример кода, который может быть полезен. 

private static final int[] bitCountArr = new int[]{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
private static final int firstByteFF = 255;
public static final int getCountOfSetBits(int value){
    int count = 0;
    for(int i=0;i<4;i++){
        if(value == 0) break;
        count += bitCountArr[value & firstByteFF];
        value >>>= 8;
    }
    return count;
}
Страница:
...