Popcount: Count Set Bits in an 8-bit Word
Population count (popcount) counts the number of 1-bits in a binary word. It appears in error-correcting codes (Hamming weight), cryptographic operations, SIMD instruction sets (Intel POPCNT), and storage system checksums. Every major CPU architecture has a dedicated hardware popcount instruction because the operation is so common. This problem asks you to build an 8-bit popcount circuit from adder primitives.
Given 8 individual input bits D7 through D0, produce a 4-bit binary count Y3 (MSB) through Y0 (LSB) representing how many of the 8 input bits are 1. The count ranges from 0 (all inputs 0) to 8 (all inputs 1, output 1000 binary).
The optimal 7-component solution uses a Wallace-tree adder structure: three first-level compressors (2 FA and 1 HA) reduce the 8 bits to partial sums, then three second-level adders reduce those to the final 4-bit count. Specifically: FA(D0,D1,D2) gives {c1,s1}, FA(D3,D4,D5) gives {c2,s2}, HA(D6,D7) gives {ch,sh}. Then FA(s1,s2,sh) gives bit 0 of the result and a carry, FA(c1,c2,ch) gives a partial bit-1 and carry, and two HA components combine the carries to produce bits 2 and 3.
| Signal | Direction | Width | Description | |--------|-----------|-------|-------------| | D7 | input | 1 | Bit 7 of the input word | | D6 | input | 1 | Bit 6 | | D5 | input | 1 | Bit 5 | | D4 | input | 1 | Bit 4 | | D3 | input | 1 | Bit 3 | | D2 | input | 1 | Bit 2 | | D1 | input | 1 | Bit 1 | | D0 | input | 1 | Bit 0 of the input word | | Y3 | output | 1 | MSB of count (bit 3) | | Y2 | output | 1 | Bit 2 of count | | Y1 | output | 1 | Bit 1 of count | | Y0 | output | 1 | LSB of count (bit 0) |
Constraints
- The circuit is purely combinational. No clock or state.
- The count Y must be a standard 4-bit binary number: Y3=1, Y2=0, Y1=0, Y0=0 means count of 8.
- The optimal solution uses 4 FA and 3 HA components (7 total), structured as a two-level adder tree.
- All 256 combinations of the 8 input bits are valid; the circuit must be correct for all.
Topics
Solve this problem
Place the gates, wire them up and watch the signals settle. Every submission runs on the same simulation engine that grades it.
This problem is part of Codiode Pro. The statement above is free to read.
The circuit builder and code editor need a desktop screen. On a phone, read the problem here and open it on a laptop to solve.