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

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

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};
};

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

 dato datuashvili30 мар. 2012 г., 22:47
да, конечно, это не мой родной язык, я из Грузии, но я не понимаю, почему вы упомянули это?
 Mark Ransom30 мар. 2012 г., 22:41
@PaulR, вопрос немного сбивает с толку - он показывает код, который будет работать только во время компиляции, но спрашивает, будет ли он оптимальным во время выполнения. Я предполагаю, что английский не является родным языком автора.
 Mark Ransom30 мар. 2012 г., 22:32
@PaulR, предлагаемое шаблонное решение будет рассчитывать во время компиляции, что займет менее одной инструкции во время выполнения!
 Paul R30 мар. 2012 г., 22:34
Ах - извините - упустил суть вопроса!
 Paul R30 мар. 2012 г., 22:28
Это называется подсчетом населения, и это можно сделать гораздо эффективнее, чем тестирование по одному биту за раз. На x86 это можно сделать с помощью одной инструкции. На других архитектурах это можно сделать с помощью нескольких инструкций.

Ответы на вопрос(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;
        }
 Rodrigo01 дек. 2018 г., 02:37
Спасибо за предоставленную нам таблицу поиска из 256 элементов. Я просто надеюсь, что это правильно.
 m_callens07 июл. 2016 г., 21:51
Пожалуйста, правильно отформатируйте свой ответ, а также дайте объяснение. Простой ответ в ответ не считается хорошим ответом.

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

#include <bitset>
#include <iostream>

int main() {
  unsigned char bitfield = 17;
  std::cout << std::bitset<8>(bitfield).count() <<
    std::endl;
}
 SonarJetLens04 авг. 2017 г., 21:46
К сведению: с VS2017, на i5 с поддержкой SSE4, в выпуске это все еще не компилируется в POPCNT, а вместо этого использует Good 'Ol LUT ... к сожалению
#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;
}

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

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 должен давать довольно эффективную программу на большинстве систем. И это очень универсально.

 Lundin22 июн. 2015 г., 12:56
@IraBaxter Действительно. И это занимает в 16 раз меньше памяти. Так что это, например, распространенное решение во встроенных системах.
 Ira Baxter22 июн. 2015 г., 10:25
Это занимает вдвое больше времени, чем обычный поиск байта в таблице 256 записей.

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

 Mark Ransom30 мар. 2012 г., 22:31
Учитывая скорость современных процессоров и сравнительную медлительность памяти, мне пришлось бы увидеть перебор между таблицей поиска и небольшим битовым кодом, прежде чем я объявил бы поиск самым быстрым.
 TJD30 мар. 2012 г., 22:39
@MarkRansom, это возможно. На самом деле некоторые процессоры имеют инструкцию по сборке, которая считает биты, установленные за один цикл. Но я также трачу много времени на встраиваемые системы, которые имеют однократный доступ ко всей своей (небольшой объем) памяти.
 Nathan Osman24 мар. 2013 г., 23:03
@MarkRansom: Но небольшая справочная таблица, скорее всего, поместится в кэш L1 ЦП.
 Matthew30 мар. 2012 г., 22:39
Если вы не хотите создавать массив из 256 элементов, вы можете вместо этого создать массив из 16 элементов и сдвинуть бит во второй половине.
 Ira Baxter30 мар. 2012 г., 22:42
Не будьте уверены, что машинная инструкция «bitcount» работает в одном такте. Будет ли это зависеть от конкретной микроархитектуры и, более вероятно, от того, будет ли этот чип использоваться АНБ или нет: -}
int count(int a){ return a == 0 ? 0 : 1 + count(a&(a-1)); }
 dato datuashvili30 мар. 2012 г., 22:32
не будет ли рекурсивный вызов функции увеличивает скорость функции экспоненциальной? может быть, лучше использовать цикл while?
 Jarosław Gomułka31 мар. 2012 г., 08:39
Это займет 2 * number_of_set_bits + 1. Так что для 10000010 потребуется 5 инструкций. Но в целом решение от BitHacks определенно лучше.
 Jarosław Gomułka30 мар. 2012 г., 22:34
Современные компиляторы оптимизируют такие простые функции до «нерекурсивных» версий.
 Ira Baxter31 мар. 2012 г., 03:18
Это все еще делает N шагов, если в слове есть N битов. Если N = 32, это может сделать 32 шага с условным переходом в каждом. Плохие новости. Лучше использовать логарифмическое суммирование; для N ~~ 32 вы получаете постоянное время. Код BitHacks, который я цитировал, использует 14 машинных инструкций, многие из которых представляют собой отдельные часы на современных процессорах.
Решение Вопроса

ов.

Для входов большего размера это немного менее тривиально. Шон Эрон Андерсон имеет несколько различных функций для этого на егоБит Тиддлинг Хаки страницавсе с разными характеристиками. Существует не одна из самых быстрых версий, поскольку она зависит от природы вашего процессора (глубина конвейера, предсказатель ветвления, размер кэша и т. Д.) И используемых вами данных.

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

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;
}

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

Если вы делаете это много, вам лучше собирать байты в слова или двойные слова и выполнять над ними быстрые битовые операции. Они, как правило, являются чисто арифметическими, поскольку вы не можете реально найти 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
 Ira Baxter30 мар. 2012 г., 23:21
Ваш целевой компьютер имеет собственный размер слова, легко известный вашему приложению во время компиляции. Если вы определяете свой код как число обработанных битов, у вас будет не более 4 подпрограмм в обозримом будущем: одна для 8, 16, 32, 64 бит (вы решаете, если вы думаете, что скоро произойдет 128 бит). Я думаю, что это довольно переносимо, и будет быстро на любой целевой архитектуре, для которой вы скомпилировали. Мне не понятно, что вы хотите использовать для этого шаблонное метапрограммирование.
 dato datuashvili30 мар. 2012 г., 22:49
так что это означает, что мой код не является переносимым да? как правило, мой вопрос, какой из них лучше, если компилятор поддерживает программирование шаблонов?

Ваш ответ на вопрос