德布鲁因序列（De Bruijn sequence）

NumberOfTrailingZeros使用了德布鲁因序列来快速求二进制数末尾0的个数。

const NumberOfTrailingZeros = number => {
    const num = parseInt(number).toString(2)
    const multiply_De_Bruijn_position = [
        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23,
        21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    ]
    return multiply_De_Bruijn_position[(((num & -num) * 0x077cb531) >> 27) & 31]
}

德布鲁因序列， B(k, n)，是k元素构成的循环序列。所有长度为n的k元素构成序列都在它的子序列（以环状形式）中，出现并且仅出现一次。

0x077cb531（00000111011111001011010100110001）是一个B（2，6）的德布鲁因序列

000001110111110010110101001100010000
00000
 00001
  00011
   00111
    01110
     11101
      11011
       10111
        01111
         11111
          11110
           11100
            11001
             10010
              00101
               01011
                10110
                 01101
                  11010
                   10101
                    01010
                     10100
                      01001
                       10011
                        00110
                         01100
                          11000
                           10001
                            0001|0
                             001|00
                              01|000
                               1|0000

可以保证（x* 0x077cb531) >> 27有唯一值，这里的x代表32位数中只有1位是1。

再根据唯一值从multiply_De_Bruijn_position得到目标值。& 31 ：应该是防止超过数组长度上限。

这里演示下8和16求末尾0 的个数

let i = 8 * 0x077cb531,
    j = 16 * 0x077cb531

console.log(i.toString(2), j.toString(2))

const multiply_De_Bruijn_position = [
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21,
    19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
]

//8: 00111011111001011010100110001000 =>
// 00111=>multiply_De_Bruijn_position[7]:3

//16: 01110111110010110101001100010000 =>
// 01110=>multiply_De_Bruijn_position[14]:4

参考

神奇的德布鲁因序列

https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup

YBFACC / blog

德布鲁因序列 #46

德布鲁因序列（De Bruijn sequence）

参考