找到小于X的最大二的次幂？

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的最大二次幂的惯用方法是什么？

编辑： 例如：power_two(100)仅返回该幂。

- user422100

---

当你说“小于”时，是指“小于或等于”还是“严格小于”？换句话说，如果n是2的精确幂，例如32，它应该返回什么？ - Mark Byers

使用对数与Python的“pythonic”有什么关系？这些与Python的前辈大约相差377年。 - JUST MY correct OPINION

@我的正确看法：您有什么其他建议呢？ - Mark Byers

我刚才说的是对数。你的答案很完美，只是...你知道...不太符合Python的风格，更偏向于“普遍数学”。 - JUST MY correct OPINION

Answer 1

找到对数并截断：

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

- Mark Byers

---

@mark：我指的是只返回6，"2**6"是为了解释6来自哪里，但你给了我一个Pythonic的方法，谢谢。 - user422100

在Python3.2中：int(math.log(4,2)) == 1，但是int(math.log(8,2)) == 3。这对于power_two()函数来说是一种不一致的行为。 - jfs

@Sebastian 可能是Python 3.2中的一个错误。这将破坏与之前版本的兼容性。具体来说，Python 3.1.2按预期工作，math.log(4,2) = 2.0。 - Dimitris Leventeas

@DimitrisLeventeas：它已经被修复了，但是否是一个 bug 还有争议 - jfs

power_two(2**2955) 的输出结果错误，应该是 2954。 - Colonel Panic

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()

- jfs

---

这是一个不错的解决方案，尽管Tony Veijalainen实际上已经发布了它 - 只是他的答案不够清晰。我给了他+1的赞同，因为他首先提出了这个建议，并且还提到了它需要Python 2.7或更新版本，这是一个非常真实的问题 - 许多用户仍在使用Python 2.6。 - Mark Byers

@Mark Byers：我也赞同Tony Veijalainen（他之前被投反对了）。Python 2.7是CPython的当前版本，因此我没有明确提及它（我在工作中使用2.4，所以我理解你的想法）。当我看到你的答案时，我认为一定有一些位操作的解决方案（最高有效位）。 long.bits_in_digit()不是公开的，因此bit_length()是下一个最好的选择。 - jfs

Answer 3

有两种方法，第一种仅适用于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)

- Tony Veijalainen

---

如果二进制是负数，那么“-3”部分会出现问题。 - Tony Veijalainen

Answer 4

利用.format()的强大功能！

def maxPowOf2(n):
     return len("{0:b}".format(n))-1

这个答案和@jfs的类似，但可能会慢一些...将数字转换为二进制字符串并找到长度。但对负数不起作用...

- Bjamse

Answer 5

嗯，我相信其他建议可能有效，但我觉得它们的执行速度会非常慢。虽然我实际上还没有验证过任何速度，但这应该非常快！

这也是用Java编写的。所以你需要进行转换。

public static int getPowerOfTwo(int size)
{
    int n = -1;
    while (size >> ++n > 0);
    return (1 << n - 1 == size) ? size : 1 << n;
}

public static int getNextPowerOfTwo(int size)
{
    int n = -1;
    while (size >> ++n > 0);
    return 1 << n;
}

public static int getPreviousPowerOfTwo(int size)
{
    int n = -1;
    while (size >> ++n > 0);
    return 1 << n - 1;
}

- Jeremy Trifilo