LSB detector
The LSB detector reports the index of the least-significant bit set to 1 in the input bus, with an enable flag that is high only when at least one bit is set. Scanning from the bottom, it isolates the lowest one, the operation behind find-first-set and allocator logic.
Trailing-one on 4 bits
For input 0110 the lowest set bit is at index 1, so the detector outputs 1 and raises enable. With 0000 there is nothing set, enable stays low and the index is undefined.
| Input | Enable | Index |
|---|---|---|
| 0000 | 0 | - |
| 0001 | 1 | 0 |
| 0010 | 1 | 1 |
| 0100 | 1 | 2 |
| 0110 | 1 | 1 |
| 1000 | 1 | 3 |
Isolating the lowest one
On 8 bits the detector returns the first 1 seen from the least-significant end. For 01101000 the trailing one sits at index 3. The classic trick x AND (-x) isolates that same bit as a mask.
Find-first-free allocator
Resource pools keep a bitmap where 0 marks a free slot. Inverting it and taking the LSB index yields the first available slot in one step, the core of buffer allocators, scheduler ready-lists and round-robin arbiters.
Citations
- Shannon, C. E. (1938). A symbolic analysis of relay and switching circuits. Reference 1
- Mano, M. M., & Ciletti, M. D. (2018). Digital design: With an introduction to the Verilog HDL, VHDL, and SystemVerilog (6th ed.). Pearson.
- Wakerly, J. F. (2018). Digital design: Principles and practices (5th ed.). Pearson.