2

对于作业，我需要找到一种算法，可以在 O(log log n) 时间内测试数字 n 是否是 4 的幂。我不知道如何解决这个问题，也不知道什么数据结构或算法是合适的。有没有人对如何解决这个问题有任何建议？

4

6 回答 6

6

如果你知道字长，你可以比 O(log log N) 做得更好——事实上，你可以在 O(1) 中做到这一点，它应该编译成 4 条机器指令。例如，如果您假设 32 位整数，您可以这样做：

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

对于不同的字长，只需更改常数即可。

x & (-x)诀窍是一个众所周知的 hack，它返回一个仅是 x 中最低有效 1 位的数字。然后& 0x5554屏蔽了 2 的奇次幂，然后如果 x 中有任何其他设置位，则与原始比较失败。

于 2013-10-26T20:26:23.070 回答
5

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 已经给出了一个有效的答案。

于 2013-10-26T20:08:02.120 回答
2

我将假设数字表示为固定宽度的整数，这允许在 O(1) 时间内完成比较、加法、乘法等基本操作。

请注意，如果您有一个数字 n，则该数字 n 中有 O(log n) 位。如果我们让 b 是数字中的位数，那么所需的运行时间将是 O(log b)。换句话说，我们想找到某个函数，其运行时间与数字中的位数成对数。

由于我们试图检查该数字是否是 4 的幂，因此我们试图查看该数字是否具有某个数字 k 的 4 k形式。这是我们可以用来执行此操作的一种可能方法：

  1. 计算 4 1 , 4 2 , 4 4 , 4 8 , 4 16 , ..., 4 2 x直到我们找到一个大于数字 n 的数字。这意味着如果 n 是 4 的幂，那么它必须是夹在 4 0和 4 2 x之间的 4 的幂。由于以下原因，此步骤最终将花费 O(log log n) 时间：数字 n 可以写为 4 log 4 n。上述过程在 4 2 x ≥ 4 log 4 n时终止，在 2 x ≥ log 4时发生n，当 x ≥ log 2 log 4 n 时发生。因此，总共只有 O(log log n) 次迭代，每次迭代花费时间 O(1)。

  2. 在 [0, 2 x ]范围内进行二分搜索以确定 k 的值（如果有）满足 n = 4 k。这一步的运行时间将是 O(x)，因为在大小为 2 x的范围内，二分搜索将花费时间 O(log 2 x ) = O(x)。此外，我们知道 x = O(log n)。在步骤 (1) 中，我们不断将指数翻倍，直到它超过 log 4 n 的值。这意味着在最坏的情况下，x 可以是 2 log 4 x，因此 x = O(log n)。因此，这一步也需要 O(log log n) 时间。

由于步骤 (1) 和 (2) 各花费时间 O(log log n)，因此总体时间复杂度为 O(log log n)。

注意：您可以将此问题视为对数n的“猜数字游戏”的变体。一个经典的面试问题是“我在想一个自然数 n，你应该试着猜一下”。您可以使用上述方法在 O(log n) 时间内解决它。在这种情况下，您试图猜测有效的 4 的指数，因此您可以将该过程应用于数字的对数以获得 O(log log n) 的运行时间。

希望这可以帮助！

于 2013-10-26T18:54:39.010 回答
0

对于无符号整数，您可以使用：

bool is_pow4(DWORD x)
    {
/*
    4^0 =    1 = 00000000001b
    4^1 =    4 = 00000000100b
    4^2 =   16 = 00000010000b
    4^3 =   64 = 00001000000b
    4^4 =  256 = 00100000000b
    4^5 = 1024 = 10000000000b
    -------------------------
    or together  10101010101b
    negate       01010101010b = A....AAAh

*/
    if (!x) return false;
    if (DWORD(x&(x-1))) return false;   // not power of 2 (more than 1 bit is set)
    return !(x&0xAAAAAAAA);             // not setted any bit from negated mask
    }
  • 它与李丹尼尔克罗克的回答基本相似
  • 但它只使用无符号整数
  • 并且还检测到 1 作为 4 的幂，这是真的（Lee Daniel Crocker 代码是错误的）
  • 还添加了一些 rems 以更好地理解它是如何工作的
  • 主要思想是pow2检测
  • pow2 数字只是 1 个设置位和零（二进制）
  • 所以 pow2 -1 只是一个（二进制）
  • 如果你和它一起应该得到 0 结果
  • 假设它也是 4 的幂，只需使用否定掩码
  • 如果位设置在错误的位置（pow2 不是 pow4），则比简单并检测它
  • 可以使用任何位数...掩码总是 AAAAAAA....AAAAAAh 为 4 的幂

这里也解决了非常相似的问题：https ://stackoverflow.com/a/19888301/2521214

PS。复杂度与 x--,& 相同

  • 所以对于普通数字 O(1)
  • 对于 bignums，通常取决于实现 O(log n)
  • 以 bignum 为底进行记录，例如 log(2^32,n)
于 2013-11-11T11:16:27.537 回答
0

关于面罩的使用稍微更便携。

#include <stdio.h> 
#include <string.h>

int main ()
{
   int x;
   int mask;

   memset(&mask, 0x55, sizeof(int));
   scanf("%d",&x);

   if ((x) && ((x & (x-1)) == 0) && (x & mask))
       printf("Power of four\n");
   else
       printf("Not power of four\n");
   return (0);
}
于 2014-08-09T17:30:57.483 回答
0

在此提供机器便携解决方案。该解决方案不需要任何预先计算的数字，并且不对机器的位宽做出任何假设。

bool isPowerOfFour(int num) {
    int s = ceil(sqrt(num));
    // s > 0 makes sure 0 is not power of four
    // 4^x -> 2^(2x) so sqrt of it should be 2^x all we need to do is to tell whether the sqrt is a power or two
    // but firstly we need to make sure sqrt(num) is an integer so we use s*s == num
    // then use (s&(s-1)) == 0 to tell whether it is a power of 2
    return s > 0 && s*s == num && (s&(s-1)) == 0; 
}
于 2016-07-11T07:57:37.880 回答