1

Test Environment: Hardware: Microcontroller

Language: C

Compiler: IAR, HEW, MPLAB, Keil...

We have a test variable

uint8_t unTestVar;  // uint8_t is type def to unsigned char (8-bit)

If in the program flow some value is moved in this unTestVar, how can we efficiently count the numbers of 1s in it.

Suppose

unTestVar = 0xA0;  // unTestVar is 10100000 in binary

so there are two 1s in this. Similarly for,

unTestVar = 89;    // unTestVar is 10000110 in binary

here we have three 1s.

Yes there are many approaches to count the number of 1s but which approach is efficient (less processing and memory usage). Note that I am in a very limited resource environment.

Osaid
  • 557
  • 1
  • 8
  • 23
  • use [__builtin_popcount()](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) if using gcc or if available. – Mohit Jain Sep 12 '14 at 09:23
  • Keep doing `(unTestVar & (unTestVar - 1))` unless `unTestVar` reduces to `0`. If you do not know why this works, find out yourself... – 0xF1 Sep 12 '14 at 09:25
  • 2
    You should look at the dozens of existing questions and web-pages that already cover this topic, and then decide which of the several option makes the most sense given the constraints that only *you* know about. – Oliver Charlesworth Sep 12 '14 at 09:27
  • I've marked it as a duplicate of a C++ question, but all the answers are non-C++-specific. Use the search facility to find other duplicates. – Oliver Charlesworth Sep 12 '14 at 09:28
  • 1
    As @OliCharlesworth stated, it has been widely answered. I'll just add this link though : http://gurmeet.net/puzzles/fast-bit-counting-routines/ – NoWiS Sep 12 '14 at 09:31

1 Answers1

1
const uint8_t m1 = 0x55;
const uint8_t m2 = 0x33;
const uint8_t m3 = 0x0F;
a = (a & m1) + ((a >> 1) & m1);
a = (a & m2) + ((a >> 2) & m2);
a = (a & m3) + ((a >> 4) & m3);

After this a contains the answer. If you don't want to loose a, use some temp variable of type uint_8.

Explanation Adding two bits would always fit in 2 bits. (00, 01 or 10). Using m1, all bits at even places (considering 0 as even and starting count from 0) are added with bits at odd places. (Shifting down by 1 place and using mask)

a = (a & m1) + ((a >> 1) & m1);

       +--+--+--+--+--+--+--+--+
a      |b7|b6|b5|b4|b3|b2|b1|b0|
       +--+--+--+--+--+--+--+--+

       +--+--+--+--+--+--+--+--+
m1     | 0| 1|| 0| 1| 0| 1| 0| 1
       +--+--+--+--+--+--+--+--+

       +--+--+--+--+--+--+--+--+
a & m1 | 0|b6| 0|b4| 0|b2| 0|b0|
       +--+--+--+--+--+--+--+--+

       +--+--+--+--+--+--+--+--+
a>>1   | 0|b7|b6|b5|b4|b3|b2|b1|
       +--+--+--+--+--+--+--+--+

       +--+--+--+--+--+--+--+--+
a>>1&m1| 0|b7| 0|b5| 0|b3| 0|b1|
       +--+--+--+--+--+--+--+--+

Adding (a&m1) and (a >> 1) & m1 and assigning to a
       +--+--+--+--+--+--+--+--+
a      |b7+b6|b5+b4|b3+b2|b1+b0|
       +--+--+--+--+--+--+--+--+

Similarly going ahead for next step a = (a & m2) + ((a >> 2) & m2);

           +--+--+--+--+--+--+--+--+
    m2     | 0| 0| 1| 1| 0| 0| 1| 1|
           +--+--+--+--+--+--+--+--+

           +--+--+--+--+--+--+--+--+
  a >> 2   |  0  |b7+b6|b5+b4|b3+b2|
           +--+--+--+--+--+--+--+--+

           +--+--+--+--+--+--+--+--+
    a&m2   |  0  |b5+b4|  0  |b1+b0|
           +--+--+--+--+--+--+--+--+

           +--+--+--+--+--+--+--+--+
 a>>2&m2   |  0  |b7+b6|  0  |b3+b2|
           +--+--+--+--+--+--+--+--+

Adding (a&m2) and (a >> 2) & m2 and assigining to a
           +--+--+--+--+--+--+--+--+
     a     |b7+b6+b5+b4|b3+b2+b1+b0|
           +--+--+--+--+--+--+--+--+

Third step a = (a & m3) + ((a >> 4) & m3);

           +--+--+--+--+--+--+--+--+
    m3     | 0| 0| 0| 0| 1| 1| 1| 1|
           +--+--+--+--+--+--+--+--+

           +--+--+--+--+--+--+--+--+
  a >> 4   |  0  |  0  |b7+b6|b5+b4|
           +--+--+--+--+--+--+--+--+

           +--+--+--+--+--+--+--+--+
    a&m3   |  0  |  0  |b3+b2|b1+b0|
           +--+--+--+--+--+--+--+--+

           +--+--+--+--+--+--+--+--+
 a>>4&m3   |  0  |  0  |b7+b6|b5+b4|
           +--+--+--+--+--+--+--+--+

Adding (a&m2) and (a >> 2) & m2 and assigining to a
           +--+--+--+--+--+--+--+--+
     a     |b7+b6+b5+b4+b3+b2+b1+b0|
           +--+--+--+--+--+--+--+--+

So finally a contains the sum of all bits. 0 bits don't contribute in the sum so it actually contains the count of set bits.

Mohit Jain
  • 30,259
  • 8
  • 73
  • 100