рассчитать количество битов, установленных в байтах

Question

Меня интересует, какой способ вычисления числа бит в байтах, установленный таким способом, является оптимальным

template< unsigned char byte > class BITS_SET
{
public:
    enum {
     B0 = (byte & 0x01) ? 1:0,
     B1 = (byte & 0x02) ? 1:0,
     B2 = (byte & 0x04) ? 1:0,
     B3 = (byte & 0x08) ? 1:0,
     B4 = (byte & 0x10) ? 1:0,
     B5 = (byte & 0x20) ? 1:0,
     B6 = (byte & 0x40) ? 1:0,
     B7 = (byte & 0x80) ? 1:0
    };
public:
 enum{RESULT = B0+B1+B2+B3+B4+B5+B6+B7};
};

Может быть, это оптимально, когда значение байта известно во время выполнения? Рекомендуется ли использовать это в коде?

Answer 1

Для одного байта данных оптимальный способ, учитывающий как скорость, так и потребление памяти:

uint8_t count_ones (uint8_t byte)
{
  static const uint8_t NIBBLE_LOOKUP [16] =
  {
    0, 1, 1, 2, 1, 2, 2, 3, 
    1, 2, 2, 3, 2, 3, 3, 4
  };


  return NIBBLE_LOOKUP[byte & 0x0F] + NIBBLE_LOOKUP[byte >> 4];
}

Вызов этой функции из цикла for должен дать довольно эффективную программу на большинстве систем. И это очень универсально.

Answer 2

Для 8-битных значений просто используйте таблицу поиска из 256 элементов.

Для входов большего размера это немного менее тривиально.Шон Эрон Андерсон имеет несколько различных функций для этого на своей странице Bit Twiddling Hacks , все с различными характеристиками производительности.Не существует единой версии «все-на-конец-все-быстрее», поскольку она зависит от природы вашего процессора (глубина конвейера, предсказатель ветвления, размер кэша и т. Д.) И используемых вами данных.

Answer 3

Почему бы просто не использовать стандартную библиотеку?Таким образом, оптимальный способ должен определяться реализацией и, вероятно, лучше, чем любой совместимый со стандартами код, который вы действительно можете написать.Например, если вы используете x86, это компилируется в одну инструкцию, но только если вы ориентируетесь на процессоры, которые его поддерживают .

#include <bitset>
#include <iostream>

int main() {
  unsigned char bitfield = 17;
  std::cout << std::bitset<8>(bitfield).count() <<
    std::endl;
}

Answer 4

Для всего одного байтового значения самый быстрый способ - сохранить ответ в 256-байтовом массиве, который вы проиндексировали со значением. Например, bits_set[] = {0, 1, 1, 2, ...

Answer 5

Почему бы не сделать сдвиг влево и не замаскировать остальные?

int countBits(unsigned char byte){
    int count = 0;
    for(int i = 0; i < 8; i++)
        count += (byte >> i) & 0x01; // Shift bit[i] to the first position, and mask off the remaining bits.
    return count;
}

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

int countBits(unsigned long long int a){
    int count = 0;
    for(int i = 0; i < sizeof(a)*8; i++)
        count += (a >> i) & 0x01;
    return count;
}

Answer 6

Обычный ответ для «самого быстрого способа сделать битовый подсчет» - это «поиск байта в массиве».Это работает для байтов, но вы платите за это доступ к памяти.Если вы делаете это только один раз в какое-то время, это, вероятно, самый быстрый, но тогда вам не нужен самый быстрый, если вы делаете это только один раз в какое-то время.

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

Отличным источником хитрых приемов для этого является Бит-хаки .

Вот схема, опубликованная тамсчитая биты в 32-битных словах в C:

 unsigned int v; // count bits set in this (32-bit value)
 unsigned int c; // store the total here

 v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
 c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

Answer 7

#include <iostream>
#include <climits> // for CHAR_BIT (most likely to be 8)
#include <cstring> // for memset
#include <new> 

static const int DUMMY = -1;

// first approch : activate the O(8) function in first get try... after that its O(1);
class bitsInByteflyLUT
{
    typedef unsigned char byte;

    public:
        bitsInByteflyLUT();     //CTOR - throws std::bad_alloc
        ~bitsInByteflyLUT();    //DTOR


        int Get_bitsInByte(byte _byte);     


    private:
        // CLASS DATA
        int*    flyLUT;

        // PRIVATE FUNCTIONS
        int bitsInByte(byte _byte);
        // O(8) for finding how many bits are ON in a byte.
        // answer can be between 0 to CHAR_BIT.

        bitsInByteflyLUT(const bitsInByteflyLUT & _class); // COPY CTOR - forbidden
        const bitsInByteflyLUT & operator= (const bitsInByteflyLUT& _class);
        // ASSIGN OPERATOR - forbidden

};

bitsInByteflyLUT::bitsInByteflyLUT()
{
    size_t nIndexes = 1 << CHAR_BIT;
    try
    {
        flyLUT =  new int[nIndexes];
    }
    catch (std::bad_alloc& ba)
    {
        throw;
    }
    memset(flyLUT, DUMMY, sizeof(int)*nIndexes);
}


bitsInByteflyLUT::~bitsInByteflyLUT()
{
    delete[] flyLUT;
}


int bitsInByteflyLUT::Get_bitsInByte(byte _byte)
{
    if (flyLUT[_byte] == DUMMY) // if its first time we try to get answer for this char.
    {
        flyLUT[_byte] = bitsInByte(_byte); // O(8)
    }
    return flyLUT[_byte]; // O(1) 
}

int bitsInByteflyLUT::bitsInByte(byte _byte)
{   
    byte nBits = CHAR_BIT;
    byte counter = 0;
    byte mask = 1;
    while(nBits--)
    {
        if(mask & _byte)
        {
            ++counter;
        }
        mask <<= 1;
    }
    return counter;
}





int main ()
{
    using std::cout;
    using std::endl;

    bitsInByteflyLUT flut;

    for (unsigned int i = 0; i < (1 << CHAR_BIT); i += 1)
    {   
        cout << i << " " << flut.Get_bitsInByte(i) << endl;
    }

    return 0;
}

Answer 8

int count(int a){ return a == 0 ? 0 : 1 + count(a&(a-1)); }

Answer 9

        #include <iostream>
        #include <ctime>
        using namespace std;

        int count1s(unsigned char byte)
        {
                if (byte == 0)
                {
                        return 0;
                }

                if (byte & 0x01)
                {
                        return  1+count1s(byte>>1);
                }
                return count1s(byte>>1);
        }

        int count1s2(unsigned char byte)
        {
                static const int ones[256] =  
   {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};

                return ones[(int)byte];
        }

        int main()
        {
                time_t start = clock();
                int c = count1s(205);
                time_t end = clock();
                cout<<"count1: "<<c<<" time: "<<double(end-start)<<endl;
                start = clock();
                c = count1s2(205);
                end = clock();
                cout<<"count2: "<<c<<" time: "<<double(end-start)<<endl;
                return 0;
        }