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

Question

什么是ruler function的迭代实现？

This website 断言 "The ruler function can be generated non-recursively" 但从未显示示例。

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)

然后你想要 1 的数量，.bit_length() 给你。

Answer 2

我可能在这里遗漏了一些东西，但是根据标尺函数的描述...

def ruler(k):
    pow = 1
    while ((2*k) % (2**pow)) == 0:
        pow += 1
    return pow-1

for x in range(1, 10):
     print ruler(x)

1
2
1
3
1
2
1
4
1

不知道，可能我没看懂问题。

Answer 3

根据 Hugh Bothwell 所说，您可以执行以下操作（对于 n > 0）：

def ruler(n):
  return len(bin(n).split('1')[-1]) + 1

Answer 4

查找 table 和 bit-twiddling 可以让您有效地解决这个问题。

ruler = dict((1<<i, i+1) for i in xrange(63))

for i in xrange(1, 20):
    print ruler[i & ~(i-1)],

Answer 5

我正在尝试这个问题并使用一些旧方法。请检查一次。我还没有完全设置它。但显然它正在工作。几乎没有未完成的破损代码。

提前致歉。

#!/usr/bin/env python
import os
def ruler():
    print("Initiating ruler function...")
    num = int(input("Enter the value to Eval::  "))

    expNumrange = 1234567890

    if num%2 == 0:
        for i in range(num):
            print(expNumrange,end='----')

    else:
        rem = num%2
        remLen = len(str(abs(rem)))
        expNumrangelen = len(str(abs(expNumrange)))
        finval = len(str(abs(expNumrange - remLen)))
        setVal = expNumrange - finval
        #rem2 = (str(expNumrange) - str(remLen))
        for i in range(num):
            print(expNumrange, end=(str(setVal) + '--'))



if __name__ == '__main__':
    ruler()

现在，请检查输出。

为“8”

1234567890----1234567890----1234567890----1234567890----1234567890----1234567890----1234567890----1234567890----

为“5”

12345678901234567880--12345678901234567880--12345678901234567880--12345678901234567880--12345678901234567880--

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

iterative implementation of the ruler function (1,2,1,3,1,2,1,4,1,2,1,3,...)

python

algorithm

number-theory