count_set_bits

Explanation of count_set_bits

The count_set_bits function counts the number of set bits (bits with value 1) in an 8-bit unsigned integer.

Function Code

uint8_t count_set_bits(uint8_t x)
{
    uint8_t count = 0;
    while (x) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

How It Works

1. Initialization:

   • count is initialized to 0. This variable will store the number of set bits.

2. Loop Until x is 0:

   • The loop runs while x is not 0.
   • In each iteration, it checks if the least significant bit (LSB) of x is set by performing a bitwise AND operation with 1 (x & 1). If the LSB is 1, count is incremented.
   • The value of x is then right-shifted by 1 (x >>= 1), effectively discarding the LSB and shifting the next bit to the rightmost position.

3. Return the Count:

   • After the loop finishes, count contains the number of set bits in x, which is returned.

Example

Let's consider an example where x = 13.

1. Binary Representation of 13:

   • 13 in binary is 00001101.

2. Step-by-Step Execution:

• Initial Values:
  • x = 13 (binary 00001101)
  • count = 0

while (x) {
    count += x & 1;
    x >>= 1;
}

• Detailed Iterations:

1. Iteration 1:

   • x = 13 (binary 00001101)
   • x & 1 = 1 (LSB is 1)
   • count = 0 + 1 = 1
   • x >>= 1 -> x = 6 (binary 00000110)

2. Iteration 2:

   • x = 6 (binary 00000110)
   • x & 1 = 0 (LSB is 0)
   • count = 1
   • x >>= 1 -> x = 3 (binary 00000011)

3. Iteration 3:

   • x = 3 (binary 00000011)
   • x & 1 = 1 (LSB is 1)
   • count = 1 + 1 = 2
   • x >>= 1 -> x = 1 (binary 00000001)

4. Iteration 4:

   • x = 1 (binary 00000001)
   • x & 1 = 1 (LSB is 1)
   • count = 2 + 1 = 3
   • x >>= 1 -> x = 0 (binary 00000000)

• End of Loop:
  • x = 0
  • count = 3

Final Result

The number of set bits in 13 (binary 00001101) is 3.

Markdown Diagram

x = 13 (binary 00001101)

Initial state:
x       : 00001101
count   : 0

Iteration 1:
x       : 00001101
x & 1   : 00000001 -> count = 1
x >> 1  : 00000110

Iteration 2:
x       : 00000110
x & 1   : 00000000 -> count = 1
x >> 1  : 00000011

Iteration 3:
x       : 00000011
x & 1   : 00000001 -> count = 2
x >> 1  : 00000001

Iteration 4:
x       : 00000001
x & 1   : 00000001 -> count = 3
x >> 1  : 00000000

Final result:
Number of set bits in 13: 3

Use Cases

• Counting Features: In embedded systems, counting set bits can help determine the number of active features or settings enabled within a configuration register.
• Population Count in Cryptography: Used in cryptographic algorithms where the Hamming weight (number of set bits) is relevant.
• Error Detection: Helps in error detection schemes like parity bits where the count of set bits matters.
• Optimization: Some algorithms and data structures use bitwise operations for optimization, and counting set bits is often required.

The function is particularly useful in low-level programming and embedded systems where operations need to be efficient and direct manipulation of bits is common.