Page MenuHomeFreeBSD

Replace binary search with de Bruijn lookup for bit-finding
AbandonedPublic

Authored by dougm on Aug 4 2017, 3:57 AM.
Tags
None
Referenced Files
Unknown Object (File)
Mar 10 2024, 11:28 PM
Unknown Object (File)
Jan 14 2024, 7:18 PM
Unknown Object (File)
Dec 28 2023, 11:21 AM
Unknown Object (File)
Dec 25 2023, 9:38 AM
Unknown Object (File)
Dec 24 2023, 5:38 PM
Unknown Object (File)
Dec 13 2023, 3:55 AM
Unknown Object (File)
Nov 5 2023, 6:10 PM
Unknown Object (File)
Nov 5 2023, 2:56 AM
Subscribers
None

Details

Reviewers
alc
Summary

The use of a de Bruijn sequence lets the single set bit in a word be found with a multiply, a shift, and a table-lookup. In this case, the current implementation uses binary search, and de Bruijn ought to be faster.

Diff Detail

Lint
Lint Skipped
Unit
Tests Skipped