bitutil.c (1194B)
- #include <stdint.h>
- /*
- * Find highest one bit set.
- * Returns bit number + 1 of highest bit that is set, otherwise returns 0.
- */
- int
- highbit64(uint64_t i)
- {
- if (i == 0)
- return (0);
- static const char debruijn[64] = {
- 1, 36, 2, 57, 37, 22, 3, 61,
- 58, 50, 38, 32, 23, 17, 4, 62,
- 55, 59, 30, 53, 51, 45, 39, 33,
- 47, 27, 24, 18, 41, 12, 5, 63,
- 35, 56, 21, 60, 49, 31, 16, 54,
- 29, 52, 44, 46, 26, 40, 11, 34,
- 20, 48, 15, 28, 43, 25, 10, 19,
- 14, 42, 9, 13, 8, 7, 6, 64
- };
- i |= i >> 1;
- i |= i >> 2;
- i |= i >> 4;
- i |= i >> 8;
- i |= i >> 16;
- i |= i >> 32;
- return (debruijn[(i * 0x03F79C6D30BACA89) >> 58 & 0x3F]);
- }
- /*
- * Find lowest one bit set.
- * Returns bit number + 1 of lowest bit that is set, otherwise returns 0.
- */
- int
- lowbit64(uint64_t i)
- {
- if (i == 0)
- return (0);
- static const char debruijn[64] = {
- 1, 2, 37, 3, 58, 38, 23, 4,
- 62, 59, 51, 39, 33, 24, 18, 5,
- 63, 56, 60, 31, 54, 52, 46, 40,
- 34, 48, 28, 25, 19, 42, 13, 6,
- 64, 36, 57, 22, 61, 50, 32, 17,
- 55, 30, 53, 45, 47, 27, 41, 12,
- 35, 21, 49, 16, 29, 44, 26, 11,
- 20, 15, 43, 10, 14, 9, 8, 7,
- };
- i &= -i;
- return (debruijn[(i * 0x03F79C6D30BACA89) >> 58 & 0x3F]);
- }