标尺函数的迭代实现(1,2,1,3,1,2,1,4,1,2,1,3,...)

Question

什么是标尺函数的迭代实现？

该网站声称"标尺函数可以非递归地生成",但从未显示示例.

Python中的递归实现(来自同一网页)如下所示:

def ruler(k):
  for i in range(1, k+1):
    yield i
    for x in ruler(i-1): yield x

Answer 1

对于每个数字n,ruler(n)等于1 +(二进制n中的尾随0的数量).

我认为(这是未经测试的)它可以有效地实现

def ruler(n):
    return (x ^ (x - 1)).bit_length()

因为在二进制中,拖尾数字看起来像

...mno1000    # x
...mno0111    # x - 1
...0001111    # x XOR (x - 1)

那么你想要1s的数量,这.bit_length()给你.