[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}$).

[Francis6-git]

Approach:
I’ll implement the Yul bit-search function using an O(1) De Bruijn or binary-search approach, covering both MSB/LSB indexing as required.

I’ll add comprehensive tests for zero, boundary values, powers of two, and representative 256-bit values, then verify correctness and compare gas usage against the existing approach.

[grantfox-oss]

🦊 GrantFox — @Francis6-git has been assigned to this issue as part of the Third Campaign campaign!

Next steps:

1. Open a Pull Request referencing this issue (e.g., Closes #751)
2. Your PR will be reviewed by the MDTechLabs maintainers

Good luck! Track your progress on GrantFox.

[grantfox-oss]

🎉 This issue has been marked as completed on GrantFox as part of the Third Campaign campaign!

@Francis6-git's PR #759 was approved and merged by @mijinummi.

🏆 @Francis6-git: You earned 40 FoxPoints for this contribution! Your current tier: Builder (1,617 total points). Track your full progress on GrantFox.

👏 Great work, @Francis6-git! Keep contributing to MDTechLabs.