calculate number of bits set in byte

Question

I am interested, which is the optimal way of calculating the number of bits set in byte by this way

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

Maybe it is optimal when value of byte is known at run-time? Is it recommended use this in code?

Answer 1

For 8-bit values, just use a 256-element lookup table.

For larger sized inputs, it's slightly less trivial. Sean Eron Anderson has several different functions for this on his Bit Twiddling Hacks page, all with different performance characteristics. There is not one be-all-end-all-fastest version, since it depends on the nature of your processor (pipeline depth, branch predictor, cache size, etc.) and the data you're using.

Answer 2

C++20 introduced std::popcount from the header <bit>

std::popcount(0b1101u) will return 3

See https://en.cppreference.com/w/cpp/numeric/popcount for more details.

Answer 3

#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 4

For just a single byte value, the fastest way is to store the answer in an 256 byte array that you index with the value. For example, bits_set[] = {0, 1, 1, 2, ...

Answer 5

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

Answer 6

The usual answer for "fastest way to do bitcount" is "look up the byte in an array". That kind of works for bytes, but you pay an actual memory access for it. If you only do this once in awhile, it is likely the fastest, but then you don't need the fastest if you only do it once in awhile.

If you do it a lot, you are better off batching up bytes into words or doublewords, and doing fast bitcount operations on these. These tend to be pure arithmetic, since you can't realistically lookup a 32 bit value in an array to get its bitcount. Instead you combine values by shifting and masking in clever ways.

A great source of clever tricks for doing this is Bit Hacks.

Here is the scheme published there for counting bits in 32 bit words in 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

Why not do a left shift and mask off the rest?

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

This can easily be adapted to handle ints of any size by simply calculating how many bits there is in the value being counted, then use that value in the counter loop. This is all very trivial to do.

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 8

For one byte of data, the optimal way considering both speed and memory consumption:

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

Calling this function from a for loop should yield quite an efficient program on most systems. And it is very generic.

Answer 9

Why not just use the standard library? That way the optimal way should be determined by the implementation, and is likely better than any standards compliant code that you can actually write. For instance, if you're on an x86 this compiles to a single instruction but only if you're targeting CPUs that support it.

#include <bitset>
#include <iostream>

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

Answer 10

#include <ctime>
#include <iostream>
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;
}

Answer 11

In gcc you can use __builtin_popcount(unsigned) function.
It should efficiently use the optimal solution for the target hardware platform.
With -march=core-avx2 (highest level compatible with my cpu) the popcntl x86_64 assembly instruction was used, doing it in the hardware.
With the default x86_64 instruction set a popcntl function was called that implements the optimal C (clever hacks) algorithm.
There's also __builtin_popcountl and __builtin_popcountll for unsigned long and unsigned long long.

Answer 12

For C++ 14+: (https://onlinegdb.com/q_PR4Iocb)

#include <stdint.h>
#include <iostream>
#include <sstream>

using namespace std;

template <class T, int width = sizeof(T) << 3>
struct stBitPattern
{
    static inline constexpr T res(T x)
    {
        constexpr int hw = width >> 1;

        x = stBitPattern<T, hw>::res(x);
        x += x << hw;

        return x;
    }
};

template <class T>
struct stBitPattern<T, 8>
{
    static inline constexpr T res(T x)
    {
        return x;
    }
};

class csPop
{
    private:
        template <class T>
        static inline constexpr T _pop8(T x)
        {
            constexpr T m1 = stBitPattern<T>::res(0x55); //binary: 0101...
            constexpr T m2 = stBitPattern<T>::res(0x33); //binary: 00110011..
            constexpr T m4 = stBitPattern<T>::res(0x0f); //binary:  4 zeros,  4 ones ...

            x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
            x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
            x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits
            return x;
        }

        template <class T, int width = sizeof(T) << 3>
        struct _pop
        {
            static inline constexpr T res(T x)
            {
                const int hw = width >> 1;
    
                x = _pop<T, hw>::res(x);
                x += x >> hw;
    
                return x;
            }
        };

        template <class T>
        struct _pop<T, 8>
        {
            static inline constexpr T res(T x)
            {
                x = _pop8(x);
                return x;
            }
        };

        template<class T>
        static inline constexpr bool _chkIfTAvail(T *p, T *pend);

    public:
        template <class T>
        static inline constexpr int pop(T x)
        {
            x = _pop<T>::res(x);
            return (int)(x & 0x7f);
        }

        template <class T>
        static int pop(T *p, size_t sz);
};

template<class T>
constexpr bool csPop::_chkIfTAvail(T *p, T *pend)
{
    return ((uint8_t*)pend-(uint8_t*)p) >= sizeof(T);
}

template <class T>
int csPop::pop(T *p, size_t sz)
{
    int res = 0;
    T *pend = (T*)((uint8_t*)p + sz);
    
    if (sz >= sizeof(T))
    {
        int t = (size_t)p & (sizeof(T) - 1);
        
        sz -= t;

        if (t >= sizeof(uint8_t))
        {
            res += pop(*(uint8_t*)p);
            p = (T*)((uint8_t*)p + 1);
            t -= sizeof(uint8_t);
        }       
        if (t >= sizeof(uint16_t))
        {
            res += pop(*(uint16_t*)p);
            p = (T*)((uint16_t*)p + 1);
            t -= sizeof(uint16_t);
        }       
        if (t >= sizeof(uint32_t))
        {
            res += pop(*(uint32_t*)p);
            p = (T*)((uint32_t*)p + 1);
            t -= sizeof(uint32_t);
        }
        if (t >= sizeof(uint64_t))
        {
            res += pop(*(uint64_t*)p);
            p = (T*)((uint64_t*)p + 1);
            t -= sizeof(uint64_t);
        }

        if (_chkIfTAvail(p, pend))
        {
            sz -= sizeof(T);
            res += pop(*p++);

            for(; _chkIfTAvail(p, pend); p++, sz-= sizeof(T))
            {
                res += pop(*p);
            }       
        }
    } // if (sz >= sizeof(T))

    if (sz >= sizeof(uint64_t))
    {
        res += pop(*(uint64_t*)p);
        p = (T*)((uint64_t*)p + 1);
        sz -= sizeof(uint64_t);
    }
    if (sz >= sizeof(uint32_t))
    {
        res += pop(*(uint32_t*)p);
        p = (T*)((uint32_t*)p + 1);
        sz -= sizeof(uint32_t);
    }
    if (sz >= sizeof(uint16_t))
    {
        res += pop(*(uint16_t*)p);
        p = (T*)((uint16_t*)p + 1);
        sz -= sizeof(uint16_t);
    }
    if (sz >= sizeof(uint8_t))
    {
        res += pop(*(uint8_t*)p);
        p = (T*)((uint8_t*)p + 1);
        sz -= sizeof(uint8_t);
    }

    return res;
}

int main()
{
    uint32_t x = 16777215;
    cout << "pop(" << x << ") = " << csPop::pop(x) << endl;
    
    uint32_t a[] = {x, x, x, x, 15};
    uint32_t *p_end = a + sizeof(a)/sizeof(a[0]) - 1;
    uint32_t *p = a;
    stringstream ss;
    
    for(; p_end - p; p++)
    {
        ss << to_string(*p) << ", ";
    }
    ss << to_string(*p);
    
    cout << "pop({" << ss.str() << "}) = " << csPop::pop(a, sizeof(a)) << endl;

    return 0;
}

Result:

pop(16777215) = 24
pop({16777215, 16777215, 16777215, 16777215, 15}) = 100

Answer 13

Using C++17 you can precalculate the lookup table using a constexpr lambda. Easier to reason about the correctness of it rather than a ready copy-pasted table.

#include <array>
#include <cstdint>

static constexpr auto bitsPerByteTable = [] {
  std::array<uint8_t, 256> table{};
  for (decltype(table)::size_type i = 0; i < table.size(); i++) {
    table.at(i) = table.at(i / 2) + (i & 1);
  }
  return table;
}();