Detector de LSB
O detector de LSB informa o indice do bit menos significativo em 1 no barramento de entrada, com um sinalizador de habilitacao que fica alto apenas se ao menos um bit estiver em 1. Varrendo de baixo, isola o um mais baixo, a operacao por tras do find-first-set e da logica de alocacao.
Ultimo um em 4 bits
Para a entrada 0110 o bit mais baixo em 1 esta no indice 1, entao o detector entrega 1 e ativa a habilitacao. Com 0000 nao ha nada em 1, a habilitacao fica em baixo e o indice fica indefinido.
| Input | Enable | Index |
|---|---|---|
| 0000 | 0 | - |
| 0001 | 1 | 0 |
| 0010 | 1 | 1 |
| 0100 | 1 | 2 |
| 0110 | 1 | 1 |
| 1000 | 1 | 3 |
Isolar o um mais baixo
Em 8 bits o detector retorna o primeiro 1 visto do extremo menos significativo. Para 01101000 o ultimo um esta no indice 3. O truque classico x AND (-x) isola esse mesmo bit como mascara.
Alocador find-first-free
Pools de recursos mantem um bitmap onde 0 marca um slot livre. Invertendo-o e tomando o indice do LSB obtem-se o primeiro slot disponivel em um passo, o nucleo de alocadores de buffers, listas de prontos do escalonador e arbitros round-robin.
Citações
- Shannon, C. E. (1938). A symbolic analysis of relay and switching circuits. Referência 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.