在Python中产生二次幂的位操作

Question

在纯音准理论中，一种音乐理论，音符之间的间隔用有理数表示。以2:1的比率倍频使它增加一个倍频程，而1:1的比率是不变的；和谐。因此，如果我有一个音程大于一个八度或小于一个和弦（它会下降），那么“证明”它是有用的。即使1≤n≤2。我在Python中使用以下函数执行此操作：

def justify(n):
    return n / 2 ** floor( log(n,2) )

实际的函数涉及到fractions库，但它使用float和int来完成任务。对数找到2n的幂次，floor向下取整，得到的除数是小于n2的最接近的幂。我也试过这个：

^{pr2}$

这一个取二进制表示的长度，并在此基础上补零。当然，这只适用于int。我想知道有没有办法用位操作来执行这个操作。看起来二进制程序会很好地利用2运算的能力。至少，我希望找到一种方法来用按位替换2 ** floor( log(n,2) )。如果它能处理浮点运算，那就多了一点，但我知道那更复杂。在

Answer 1

math.frexp(x)正如马克·迪金森在问题评论中指出的那样，是一条出路：

def justify(n):
    return 2*frexp(n)[0]

它可以处理浮点和整数。在

Answer 2

对于整数，您可以通过以下方式稍微迂回地达到：

def justify(n):
    return n / 1<<(n.bit_length()-1)

我不知道在没有重要测试的情况下它是否更快，但是使用timeit的快速测试显示它的速度大约是第一个代码片段的两倍。在

但是，将n转换为分子中的浮点值（以获得浮点值的返回值）会将其减慢到与原始值相同的速度。在

^{pr2}$

bit_length给出了表示abs(x)所需的最小位数，实际上将比计算所需的多1个。在

我希望log(n,2)在基础中对2的幂次进行了大量优化，而且它是用C实现的，所以你很难战胜它。在

可能将分母改为1<<int(log(n,2))可能会比2**方法提供更好的性能。。而且似乎要快30%

def justify(n):
    return float(n) / (1<<int(log(n,2)))

完全可以用位运算符来完成：

def justify_bitwise(n):
   int_n = int(abs(n))
   p = 0
   while int_n != 1:
       p += 1
       int_n >>= 1

   return float(n) / (1<<p)

但是timeit将其时钟调整为2.16微秒。比使用bit_length慢一个数量级