Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /// Returns the number of trailing zeros in a 32bit unsigned integer.
- ///
- /// Hacker's Delight, Reiser's algorithm.
- /// "Three ops including a "remainder, plus an indexed load."
- ///
- /// Works because each bit in the 32 bit integer hash uniquely to the
- /// prime number 37. The lowest set bit is returned via (x & -x).
- ntz32(int x) {
- assert(x < 0x100000000, "only 32bit numbers supported");
- return _ntzLut32[(x & -x) % 37];
- }
- /// Returns the number of trailing zeros in a 64bit unsigned integer.
- ///
- /// Modification of ntz32 - each bit in a 64 bit integer hash to the prime
- /// number 131. The lowest set bit is returned via (x & -x).
- ntz64(int x) => _ntzLut64[(x & -x) % 131];
- const _ntzLut32 = [
- 32, 0, 1, 26, 2, 23, 27, 0, //
- 3, 16, 24, 30, 28, 11, 0, 13,
- 4, 7, 17, 0, 25, 22, 31, 15,
- 29, 10, 12, 6, 0, 21, 14, 9,
- 5, 20, 8, 19, 18
- ];
- const _ntzLut64 = [
- 64, 0, 1, -1, 2, 46, -1, -1, 3, 14, 47, 56, -1, 18, -1, //
- -1, 4, 43, 15, 35, 48, 38, 57, 23, -1, -1, 19, -1, -1, 51,
- -1, 29, 5, 63, 44, 12, 16, 41, 36, -1, 49, -1, 39, -1, 58,
- 60, 24, -1, -1, 62, -1, -1, 20, 26, -1, -1, -1, -1, 52, -1,
- -1, -1, 30, -1, 6, -1, -1, -1, 45, -1, 13, 55, 17, -1, 42,
- 34, 37, 22, -1, -1, 50, 28, -1, 11, 40, -1, -1, -1, 59,
- -1, 61, -1, 25, -1, -1, -1, -1, -1, -1, -1, -1, 54, -1,
- 33, 21, -1, 27, 10, -1, -1, -1, -1, -1, -1, -1, -1, 53,
- 32, -1, 9, -1, -1, -1, -1, 31, 8, -1, -1, 7, -1, -1,
- ];
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement