logo

oasis

Own branch of Oasis Linux (upstream: <https://git.sr.ht/~mcf/oasis/>) git clone https://anongit.hacktivis.me/git/oasis.git

bitutil.c (1194B)


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