[PERF] Implement Fast Bit-Search Indexer in Yul (Find First Set Bit)

[mijinummi]

Labels: medium-difficulty, yul, math, gasguard
Difficulty: Medium
Module: contracts/math/

---

🧠 Concept

Build an assembly algorithm (Find First Set / De Bruijn multiplication approach) in Yul to locate the position of the most significant bit (MSB) or least significant bit (LSB) in a uint256 word.

⚠️ Problem

Finding bit indices using high-level while loops iterates byte-by-byte or bit-by-bit, consuming high execution gas on large numbers.

📁 Implementation Scope

• contracts/math/YulBitSearch.sol
• test/math/YulBitSearch.test.ts

🛠️ Requirements

1. Implement De Bruijn lookup or binary-search bitwise shifts in Yul assembly.
2. Return bit index ($0\text{--}255$) in $O(1)$ constant time.

🎯 Acceptance Criteria

• Finds MSB/LSB bit indices with minimal gas consumption.
• Passes comprehensive unit tests across edge values ($0, 1, 2^{255}$).