Number of Trailing Zeros - Dart Edition

ntz.dart

/// 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,
];