找到小于X的最大2的幂?

Question

我正在做这个

def power_two(n, base = -1):
    result = 2 ** base
    if result < n:
        base += 1
        power_two(n, base)
    else:
        if result == n:
            print base
        else:
            print base - 1

在Python中，怎么才能找到小于某个数字X的最大2的幂呢？

补充说明：举个例子，调用power_two(100)时，只返回这个幂的值。

Answer 1

有两种方法，第一种只在Python 2.7中有效，可能在3+版本中也能用：

import random
for number in (random.randint(0,1<<32) for _ in range(16)):
    print "%20i,%4i, %4i" % (number, number.bit_length()-1, len(bin(number))-3)

Answer 2

你可以使用 bit_length() 这个方法：

def power_two(n):
    return n.bit_length() - 1

根据定义，当 n != 0 时，有：2**(n.bit_length()-1) <= abs(n) < 2**n.bit_length()

Answer 3

找到对数并截断它：

def power_two(n):
    return int(math.log(n, 2))