How to count the bits with the value 1
The population count of a value is the number of bits that have the value 1.
The value 0xB6 has five such bits, so its population count is 5.
Every current processor has one instruction for this count.
Try the count of set bits in the bit editor
The value 0xB6, which has five bits with the value 1. Edit the expression or select a bit to flip it.
7
6
5
4
3
2
1
0
5 of 8
bits set · 8 bits
- hex
- 0xB6
- value
- 182
The count of set bits step by step
Count the bits with the value 1 in the value above: The steps follow the value above.
- Write the value as bits: 10110110
- The bits with the value 1 are at the positions 1, 2, 4, 5, 7.
- The count of bits with the value 1 is 5.
The population count of a few values
| Value | Binary | Count |
|---|---|---|
| 0x00 | 00000000 | 0 |
| 0x01 | 00000001 | 1 |
| 0x0F | 00001111 | 4 |
| 0xB6 | 10110110 | 5 |
| 0x7F | 01111111 | 7 |
| 0xFF | 11111111 | 8 |
Where the count of set bits is used
A parity check needs the count of bits with the value 1.
An error correction code compares two values by the count of bits that differ.
A bitmap allocator counts the free slots of a word with one instruction.
The count of set bits: points to note
- The trick x & (x - 1) clears the lowest bit with the value 1. A loop over it runs once per such bit.
- A value with one bit is a power of two. The test x & (x - 1) equal to 0 finds one.
- The count of bits that differ between two values is the population count of their XOR.
- The C functions are __builtin_popcount in GCC and Clang, and std::popcount in C++20.
The full bit editor
The full editor holds many values, evaluates expressions across them, and reads live values from a serial port.
Open this value in the full editorQuestions about the count of set bits
- What is a population count?
- It is the number of bits of a value that have the value 1. The name popcount is the short form.
- How do I test for a power of two?
- A value above 0 with exactly one bit of value 1 is a power of two. Test it with x & (x - 1) equal to 0.
- What is a Hamming distance?
- It is the count of positions where two values differ. Apply XOR to the two values, then count the bits with the value 1.