Floor(Log2(N)) for 4-bit Input
The floor of log base 2 of an integer N equals the index of N's most significant set bit. This operation appears constantly in hardware design: determining how many bits are needed to represent a value, computing shift amounts for power-of-two alignment, and implementing fast integer division by powers of two. DSP hardware at companies like Qualcomm and Texas Instruments uses this operation in fixed-point scaling logic.
Your task is to compute floor(log2(N)) for a 4-bit unsigned input N, producing a 2-bit binary output. The input is given as individual bits D3 (MSB), D2, D1, D0 (LSB). The output is {Y1, Y0} where Y1 is the MSB and Y0 is the LSB of the 2-bit result.
N=0: result is 0 (undefined, output 00). N=1 (D=0001): floor(log2(1)) = 0, output 00. N=2 or 3 (D=001x): floor(log2) = 1, output 01. N=4 to 7 (D=01xx): floor(log2) = 2, output 10. N=8 to 15 (D=1xxx): floor(log2) = 3, output 11.
In other words, Y[1:0] encodes the position of the highest set bit: D3 set → output 11, only D2 set → output 10, only D1 set → output 01, only D0 set (or all zero) → output 00.
Y1 = 1 whenever the MSB position is 2 or 3, which simplifies to Y1 = D3 OR D2. Y0 = 1 whenever the MSB position is 1 or 3: Y0 = D3 OR (NOT(D3) AND NOT(D2) AND D1).
| Signal | Direction | Width | Description | |--------|-----------|-------|-------------| | D3 | input | 1 | MSB of the 4-bit input N | | D2 | input | 1 | Bit 2 of N | | D1 | input | 1 | Bit 1 of N | | D0 | input | 1 | LSB of N (does not affect the output for N > 1) | | Y1 | output | 1 | MSB of floor(log2(N)) | | Y0 | output | 1 | LSB of floor(log2(N)) |
Constraints
- The circuit is purely combinational. No clock or state.
- D0 does not affect the output for any valid input where D3, D2, or D1 is set. D0 only matters when N=1 (D=0001), but output is 00 for both N=0 and N=1.
- The optimal solution uses 5 components: 1 OR (for Y1), 1 NOT, 1 NOT, 1 AND3, 1 OR (for Y0).
- Shared signals: NOT(D3) and NOT(D2) computed once are reused in the Y0 expression.
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.