确定一个数字是否为四次幂O（log log n）

Question

对于作业，我需要找到一种算法，可以测试数字n是否为时间O（log log n）的四次幂。我不知道该如何处理，也不知道哪种数据结构或算法是合适的。有人对如何解决此问题有任何建议吗？

Answer 1

如果您知道单词的大小，那么您可以比O（log log N）做得更好-实际上，您可以在O（1）中使用应编译为4条机器指令的代码进行操作。例如，如果假设使用32位整数，则可以执行以下操作：

int is_power_of_4(int x) {
    return ( (x & (-x)) & 0x55555554 ) == x;
}

对于不同的单词大小，只需更改常数。

的x & (-x)招是一个众所周知的入侵，返回一个数字，是在X只至少显著1个比特。在& 0x5554随后面具掉2的奇权力，然后比较原来的失败，如果有在X任何其他设置位。

Answer 2

该O(log log n)要求是有点古怪。如果您正在处理无界整数，并且这些整数以通常的二进制形式表示，那么您就无法真正避免检查n. 在这种情况下，您将无法做得比O(log n). 另一方面，如果你只是计算基本操作，它可以及时完成O(1)。

这是一些Python代码：

>>> def is_power_of_four(n):
...     return n & (n-1) == 0 and n % 3 == 1
... 
>>> [n for n in range(-10**6, 10**6) if is_power_of_four(n)]
[1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144]

在位操作方面，这个算法是O(log n)。在操作计数方面，它是O(1). 说明：n & (n-1)是应用于and的按位和操作。当且仅当其中一个是 2 的幂或时，它才为零。并且在二的幂中，四的幂都有余数模，而其他二的幂有余数。余数测试也方便地排除了这种情况。nn-1nn == 0132n == 0

如果您还想知道四的幂是哪个n，而不仅仅是确定是否n是四的幂，那么这是一个不同的问题，templatetypedef 已经给出了有效的答案。