MSB / Leading-One Detector (4-bit, One-Hot Output)
Finding the position of the most significant set bit is a critical operation in floating-point normalization, priority arbiters, and divide-by-power-of-two optimizations. In floating-point hardware, the normalizer must find the leading one of the mantissa to determine how many positions to shift — this is the exact circuit you are building. NVIDIA and Intel both interview candidates on leading-one detection as a gateway to floating-point datapath questions.
Your task is to build a leading-one detector for a 4-bit input. Given inputs A3 (MSB), A2, A1, A0 (LSB), produce four one-hot outputs Y3, Y2, Y1, Y0 where exactly one of the four outputs is 1, corresponding to the highest bit position that is set in the input. If all inputs are 0 (no bits set), all outputs are 0.
The priority encoding is: A3 has the highest priority. If A3=1, then Y3=1 regardless of A2, A1, A0. If A3=0 and A2=1, then Y2=1. If A3=0, A2=0, and A1=1, then Y1=1. If A3=A2=A1=0 and A0=1, then Y0=1.
Worked examples: input 1010 (A3=1) → Y3=1, Y2=0, Y1=0, Y0=0. Input 0110 (A3=0, A2=1) → Y3=0, Y2=1, Y1=0, Y0=0. Input 0001 (only A0 set) → Y3=0, Y2=0, Y1=0, Y0=1. Input 0000 → all outputs 0.
| Signal | Direction | Width | Description | |--------|-----------|-------|-------------| | A3 | input | 1 | Bit 3 (MSB) of the input | | A2 | input | 1 | Bit 2 of the input | | A1 | input | 1 | Bit 1 of the input | | A0 | input | 1 | Bit 0 (LSB) of the input | | Y3 | output | 1 | 1 when A3 is the highest set bit | | Y2 | output | 1 | 1 when A2 is the highest set bit (and A3=0) | | Y1 | output | 1 | 1 when A1 is the highest set bit (and A3=A2=0) | | Y0 | output | 1 | 1 when A0 is the highest set bit (and A3=A2=A1=0) |
Constraints
- The circuit is purely combinational. No clock or state.
- Y3 = A3 (wire directly from input, no gate needed).
- Y2 = NOT(A3) AND A2. Y1 = NOT(A3) AND NOT(A2) AND A1. Y0 = NOT(A3) AND NOT(A2) AND NOT(A1) AND A0.
- The optimal solution uses 7 gate components: 3 NOT, 1 AND, 1 AND3, 1 AND3, 1 AND (sharing NOT(A3) and NOT(A2) across multiple outputs).
- At most one output may be 1 for any given input; for all-zero input, all outputs are 0.
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.