• State Resolved
  • Locked Locked
  • Replies 4 replies
  • Subscribers 53 subscribers
  • Views 3300 views
  • Users 0 members are here
Support feedback
Options
Options
Related

This thread has been locked.

If you have a related question, please click the "Ask a related question" button in the top right corner. The newly created question will be automatically linked to this question.

Quick way to count # of bits set in uint8_t

MikeH
Guru 15580 points

Ok C coding gurus..... I'm looking for a quick easy way to count the number of bits set in an unsigned 8-bit integer. The fewer cycles, the better. Suggestion welcomed!

Thx,

MikeH

 

  • 0
    TI__Guru* 84285 points

    Barring a specialized bit-count instruction or a 256-entry lookup table, the fastest way will be using bit-tricks.   See http://en.wikipedia.org/wiki/Hamming_weight for the basic idea, with several links to some good explanations.

  • 0 in reply to Archaeologist
    Guru 15580 points

    Arch,

    Thanks for the pointer. I took the brute force approach. Here's essentially what I did (re-written for public consumption).

    //Return the number of bits set in a uint8_t

    uint8_t bits_set(uint8_t number)

    {

    uint8_t i, count=0, temp =0;

    temp = number;

    for(i=0;i<sizeof(number); i++)

    {

    if(temp & 0x01) count++;

    temp >>= 1;

    }

    return count;

    }

  • 0 in reply to MikeH
    TI__Guru* 84285 points

    MikeH said:

    for(i=0;i<sizeof(number); i++)

    I think you mean sizeof(number)*CHAR_BIT here

  • 0 in reply to Archaeologist
    Guru 26430 points

    That Hamming weight Wiki article is interesting reading. The algorithm without lookup looks to be too much code for just 8 bits. I think a 16 entry lookup table used twice might be the best balance between memory usage, code size and constant execution times. A modification of the Wiki lookup code would be something like:

    //Return the number of bits set in a uint8_t
    uint8_t bits_set(uint8_t number)
    {
      static const uint8_t lookup[16] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
      return( lookup[number>>4] + lookup[number&0x0F] );
    }