logo标签列表

如何检查一个整数是否是3的幂？

algorithmmath
67
9
常常会有新问题产生，但我建议考虑概括性的问题。例如，“N的幂？”其中N是任意整数。 - Michael Easter
3
@Michael：我刚刚添加了一个比starblue提供的更快的答案：我的算法最坏情况下只需要五次除法。在我的回答中，我还讨论了“N的幂”的一般情况。 - Ray Burns
3
这很荒谬。接下来是什么？5的力量吗？ - Alexandre Santos
@AlexandreSantos 没错！这是在技术面试中被问到的问题；5的幂！ - Hengameh
然而，3和5（如7、9、15、17等）是2的幂次方+/-1，有趣的“数字”求和技巧适用。 - greybeard
显示剩余3条评论
25个回答
121

对于有限大小的整数（例如32位整数），存在一种常数时间（相当快）的方法。

注意，对于一个3的幂次方整数N，以下结论是成立的：

  1. 对于任何小于等于N的3的幂次方M，M都能整除N。
  2. 对于任何小于等于N但不是3的幂次方的整数M，M不能整除N。

适合32位的最大3的幂次方为3486784401（3^20），下面是相应的代码：

```python if n > 0 and 3486784401 % n == 0: return True else: return False ```
bool isPower3(std::uint32_t value) {
    return value != 0 && 3486784401u % value == 0;
}

同样地，对于有符号的32位整数，它是1162261467（3^19）：

bool isPower3(std::int32_t value) {
    return value > 0 && 1162261467 % value == 0;
}

通常的魔数为：

3^floor(log_3 MAX) == pow(3, floor(log(MAX) / log(3)))

注意浮点精度误差问题，使用像Wolfram Alpha这样的数学计算器来计算常数。例如对于2^63-1（有符号int64），C++和Java都会给出4052555153018976256，但正确的值是4052555153018976267。

1
在1和2中指定的属性对于所有质数都是正确的。不是吗？那么我们可以使用这个过程来检查一个整数是否是2、3、5、7、11等的幂次吗？ - Mohammad Mamun Hossain
1
但需要知道数字3486784401或1162261467，如何仅使用*获取它？这与原始数字连续除以3相同。 - J.J. Beam
不应该说“C++给出了这个数字”。C++过于未指定，无法给出任何特定的数字。在我的x86 Linux GCC上，我从std::pow(3.L, std::floor(std::log((1ull<<63)-1.L)/std::log(3.L)))得到了正确的值。(请注意这里的long double字面量，它们起到了关键作用。) - Ruslan
以上计算有误，正确的2^63-1的值为9223372036854775807。如果您使用Java的pow()方法计算2^63并将其强制转换为int类型，则会发生截断并得到2147483647的结果。 - bincob
88
while (n % 3 == 0) {
    n /= 3;
}
return n == 1;

请注意，1是三的零次幂。

编辑：在循环之前还需要检查零，因为对于 n = 0，循环不会终止（感谢 Bruno Rothgiesser）。

27
我会在此发表评论，因为它目前（我希望仍然是）得票最高的答案。对于所有想避免除法而使用乘法的人来说：通常情况下，这个答案会比你们的更快，因为对于大多数输入，它不需要进行很多次除法运算。随机输入的三分之二将在一次取模和比较后被排除。而基于乘法的答案必须一直乘下去，直到累加器达到或超过n，对于任何输入都是如此。 - John Y
5
这个算法已经非常简单和清晰明了。在纯数学中，我们会使用对数。而在计算机上，则可以使用starblue的示例代码。 - Noctis Skytower
3
我对这个和其他答案都很感兴趣，但是最快的解决方案在这里并没有被提到。我已经发布了另一个答案，它比这个答案更快，也比if-else语句的想法更快，因为它避免了管道停顿（你可以去看看...）。然而，我必须说，我真的很喜欢这个答案的简单性，如果我写的不是以速度为最重要标准的库，我可能会选择它而不是我的答案。 - Ray Burns
@Ray Burns 请查看我下面的新答案。我认为它应该可以与最快的解决方案竞争。 - starblue
这是最好的“通用”解决方案，因为它具备以下三个特点：1）简单易操作；2）现代编译器会将除法转化成乘法（请参见算法4），从而实现高效紧凑的循环，无需查找表和内存访问。 - Brett Hale
显示剩余7条评论
44

我稍微有点认为，如果你所说的“整数”指的是“带符号的32位整数”，那么（伪代码）

return (n == 1) 
    or (n == 3)
    or (n == 9)
    ... 
    or (n == 1162261467)

这个问题有一定的美丽简洁性（最后一个数字是3^19，因此情况并不多）。即使对于一个64位无符号整数，仍然只有41种情况（感谢@Alexandru指出我的疏忽）。当然，对于任意精度算法来说是不可能的...

18
对于64位整数，您不应该获得超过64个情况。 - Alexandru
4
您可以展开常量，例如 n = 3 * 3 或 n = 3 ** 2。这样您就可以通过目测来检查正确性。通常情况下，编译器会为您折叠常量，因此不会损失效率（但并非所有语言/实现都是如此）。 - dan-gph
5
你可以使用二分查找来加速它。 - starblue
5
使用二分搜索，我确定这是最有效的解决方案。 - Niki
32

我对此感到惊讶。似乎所有人都错过了最快的算法。

下面这个算法平均来说比简单的while(n%3==0) n/=3;循环更快，在某些情况下速度会显著提高：

bool IsPowerOfThree(uint n)
{
  // Optimizing lines to handle the most common cases extremely quickly
  if(n%3 != 0) return n==1;
  if(n%9 != 0) return n==3;

  // General algorithm - works for any uint
  uint r;
  n = Math.DivRem(n, 59049, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r, 243, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r,  27, out r); if(n!=0 && r!=0) return false;
  n += r;
  return n==1 || n==3 || n==9;
}

代码中的数字常量为3^10，3^5和3^3。

性能计算

在现代CPU中，DivRem通常是一个单周期指令。在其他CPU上，它会扩展成除法、乘法和加法操作，需要大约三个时钟周期。该算法的每个步骤看起来很长，但实际上只包括：DivRem, cmp, cmove, cmp, cand, cjmp, add。可以利用大量的并行性，在典型的双向超标量处理器上，每个步骤的执行时间大约为4个时钟周期，因此最坏情况下的执行时间保证不超过25个时钟周期。

如果输入值均匀分布在UInt32的范围内，则该算法涉及以下概率:

  • 在第一条优化行之前或之内返回：66%的时间
  • 在第二条优化行之前或之内返回：89%的时间
  • 在第一个一般算法步骤之前或之内返回：99.998%的时间
  • 在第二个一般算法步骤之前或之内返回：99.99998%的时间
  • 在第三个一般算法步骤之前或之内返回：99.999997%的时间

该算法优于简单的while(n%3==0) n/=3循环，后者的概率如下:

  • 在第一次迭代中返回：66%的时间
  • 在前两次迭代中返回：89%的时间
  • 在前三次迭代中返回：97%的时间
  • 在前四次迭代中返回：98.8%的时间
  • 在前五次迭代中返回：99.6%的时间……以此类推……
  • 在前十二次迭代中返回：99.9998%的时间……以及之后……

更重要的是，该算法能够高效地处理中等大小和大型的三的幂（以及其倍数）：在最坏情况下，简单算法将消耗超过100个CPU周期，因为它需要循环20次（64位情况下为41次）。我提出的算法永远不会超过25个时钟周期。

扩展到64位

将上述算法扩展到64位非常简单-只需要再添加一个步骤。以下是针对没有高效64位除法的处理器进行优化的上述算法的64位版本：

bool IsPowerOfThree(ulong nL)
{
  // General algorithm only
  ulong rL;
  nL = Math.DivRem(nL, 3486784401, out rL); if(nL!=0 && rL!=0) return false;
  nL = Math.DivRem(nL+rL,   59049, out rL); if(nL!=0 && rL!=0) return false;
  uint n = (uint)nL + (uint)rL;
  n = Math.DivRem(n,   243, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r,  27, out r); if(n!=0 && r!=0) return false;
  n += r;
  return n==1 || n==3 || n==9;

}
新的常量是3^20。方法的优化行被省略掉了，因为根据我们的假设64位除法很慢，它们实际上会减慢速度。 这种技术为什么有效 假设我想知道"100000000000000000"是否是10的幂。我可以按照以下步骤进行：
  1. 我除以10^10得到商为10000000和余数为0。这两个数相加等于10000000。
  2. 我除以10^5得到商为100和余数为0。这两个数相加等于100。
  3. 我除以10^3得到商为0和余数为100。这两个数相加等于100。
  4. 我除以10^2得到商为1和余数为0。这两个数相加等于1。
因为我从10的幂开始，每次我除以10的幂时，我最终得到的要么是零商，要么是零余数。如果我不是从10的幂开始，我迟早会得到非零商或余数。
在此示例中，我选择了10、5和3的指数以匹配先前提供的代码，并额外添加了2。其他指数也可以：对于给定的最大输入值和输出中允许的最大10次幂，有一种简单的算法来选择理想的指数。但是这个空间不足以包含它。
注意：你可能一直在基于十进制思考，但是如果你在三进制中思考，上面的整个解释也可以被读和理解，只是指数将会被用不同的方式表示（例如，“10”、“5”、“3”和“2”将会变成“101”、“12”、“10”和“2”）。
5
请原谅我的无知，但在循环计数中，除法和乘法通常需要多个周期吗？ - Michael Myers
3
这取决于CPU。在需要多个周期才能执行除法运算的CPU上，运算结果会有所不同，但这个算法仍然是当前可用的最有效算法。 - Ray Burns
也许使用log()会更快，可以看看我的解决方案。 - Tomas
8
Elric的答案更加优雅，而且可能更快： bool isPower3(uint32_t v) { return v != 0 && 3486784401u % v == 0; }。吹嘘每个人似乎都错过了最快的算法通常是注定要失败的。 - chqrlie
除法总是很慢，因为它无法像乘法那样进行优化，即使在更高的硬件成本下也是如此。我从未听说过CPU可以在一个周期内完成除法运算；在现代amd64上，即使乘法需要3-4个周期，而除法则慢了一个数量级。 - maaartinus
30
这是以下所有好的答案的总结，性能数据可以在LeetCode文章中找到。

1. 循环迭代

时间复杂度为O(log(n))，空间复杂度为O(1)

public boolean isPowerOfThree(int n) {
    if (n < 1) {
        return false;
    }

    while (n % 3 == 0) {
        n /= 3;
    }

    return n == 1;
}

2. 进制转换

将整数转换为三进制数，并检查它是否以前导1后跟所有0的形式书写。这灵感来自于检查一个数是否是2的幂的解决方案，方法是执行n & (n - 1) == 0

时间复杂度：根据语言和编译器不同，为O(log(n))，空间复杂度：O(log(n))

public boolean isPowerOfThree(int n) {
    return Integer.toString(n, 3).matches("^10*$");
}

3. 数学

如果n = 3^i，则i = log(n) / log(3)，因此可得出解决方案。

时间复杂度：取决于语言和编译器，空间复杂度：O(1)。

public boolean isPowerOfThree(int n) {
    return (Math.log(n) / Math.log(3) + epsilon) % 1 <= 2 * epsilon;
}

4. 整数限制

因为3^19 = 1162261467是32位整数中最大的3的幂，因此我们可以进行以下操作：

时间复杂度：O(1)，空间复杂度：O(1)

public boolean isPowerOfThree(int n) {
    return n > 0 && 1162261467 % n == 0;
}

5. 使用Set解决整数限制问题

这个方法与#4类似，使用一个set来存储所有可能的3的幂次数（从3^0到3^19）。这样可以使代码更易读。

6. 递归解法（C++11）

这个解法特定于C++11，使用模板元编程，这样编译器将用计算出的结果替换调用isPowerOf3<Your Input>::cValue的语句。

时间复杂度：O(1)，空间复杂度：O(1)

template<int N>
struct isPowerOf3 {
    static const bool cValue = (N % 3 == 0) && isPowerOf3<N / 3>::cValue;
};

template<>
struct isPowerOf3<0> {
    static const bool cValue = false;
};

template<>
struct isPowerOf3<1> {
    static const bool cValue = true;
};

int main() {
    cout<<isPowerOf3<1162261467>::cValue;
    return 0;
}
“只是在不总结关键点的情况下放置链接，直接违反了如何撰写好答案？第四段 - 这样做会积累负面评价。（同样适用于代码，特别是没有注释的代码。）” - greybeard
@ greybeard 感谢您的评论，我会更新我的答案。 - HaoCS
1
@HaoCS 不错的解决方案！您怎么知道3^19是适合32位系统的最大数字？那4、5等的最大幂次呢？ - Papps
@HaoCS，您能否分享第三种实现的详细信息呢？我对添加方程两边的epsilon部分很感兴趣，您是如何想到这个技巧的呢？ - noobsaibot
28

如果 (log n) / (log 3) 是整数，则 n 是 3 的幂。

30
在数学意义上是正确的，但由于舍入误差在实际中可能不可行。我在我的机器上检查了(log 3^40)/log(3^40-1)=1.0。 - Rafał Dowgird
4
个人认为，这样做虽然在数学上是正确的，但效率和精确度都太低了。 - Dario
1
你的意思是：“如果 (log n) / (log 3) 是整数，那么 n 就是 3 的幂次方”，对吗？ - Hengameh
使用 log2 而不是 log 可以消除舍入误差。 - phoad
1
@phoad：不，它并不是这样的。首先，每个不是2的幂的整数的log2在二进制浮点数中都无法准确表示，因此任何计算其log2的函数都必须返回带有舍入误差的结果。其次，除法引入了另一个舍入误差。因此，评估log2(n) / log2(3)通常会有三个舍入误差。第三，像log2这样的数学库函数通常没有正确的舍入实现，因此它们还会有额外的舍入误差。 - Eric Postpischil
1
对于那些声称存在舍入误差的人，可以使用自带浮点运算的log10方法。例如，在JavaScript中，Number.isInteger(Math.log10(n) / Math.log10(3))。 - Farzad Yousefzadeh
11

非常有趣的问题，我喜欢来自starblue的答案，这是他算法的一个变体，能够更快地收敛到解决方案:

private bool IsPow3(int n)
{
    if (n == 0) return false;
    while (n % 9 == 0)
    {
        n /= 9;
    }
    return (n == 1 || n == 3);
}
1
不错的“混合”方法（基本上是将除法与预计算值相结合）。 - John Y
11

递归地将数除以3，检查余数是否为零，并将结果再次应用于商。

请注意，当幂为零时，3的零次方等于1是一个需要注意的特殊情况，因此1也是一个有效答案。

3
赞同正确的方法，但递归（在其真正意义上）是完全不必要的。这可以通过迭代完成。 - Carl Smotricz
7
算法本质上是递归的，迭代只是一种没有实际优势的解决方法（请参见尾递归消除）。 - Dario
10
或者，反过来迭代：
  • 数字是1吗（即3的0次方）？如果是，成功；否则继续
  • 数字是1乘以3吗......
  • 数字是1乘以3乘以3吗......
这种方法避免了除法运算，保持了整数的状态。或者，如果您使用的是具有64位整数的系统，请构建一个三的幂的表，并检查每个数组项，这只需要40个元素。 - High Performance Mark
9
在2的幂次方之间，最多只有一个3的幂次方。因此，以下是一种快速测试方法：
  1. 通过查找数字中前导1位的位置来找到n的二进制对数。这非常快，因为现代处理器有一个专门的指令。(否则，您可以通过位操作来完成，参见Bit Twiddling Hacks）。
  2. 通过查找以该位置为索引的表中的潜在3次幂，与n进行比较（如果没有3的幂，则可以存储具有不同二进制对数的任何数字）。
  3. 如果它们相等，则返回yes，否则返回no。
运行时间主要取决于访问表项所需的时间。如果我们使用机器整数，那么表格很小，而且可能在缓存中（我们要使用它数百万次，否则这种优化水平就没有意义）。
1
将零存储在那里是一个坏主意，因为你必须确保零不会被映射到这个慢速。存储三的任意幂次方可以工作。我刚刚发布了一个不同的基于完美哈希的答案，我看到我可以使用numberOfLeadingZeros作为哈希。 - maaartinus
@maaartinus 已修复，但采用更普适的方式。 - starblue
没错，但是我在答案中使用的像 table = [1 for i in range(32)] 这样的简单初始化不需要思考。没有思考意味着没有犯错的机会。 ;) - maaartinus
6

这是一个用C语言实现Ray Burns' method的快速且优秀的方法：

bool is_power_of_3(unsigned x) {
    if (x > 0x0000ffff)
        x *= 0xb0cd1d99;    // multiplicative inverse of 59049
    if (x > 0x000000ff)
        x *= 0xd2b3183b;    // multiplicative inverse of 243
    return x <= 243 && ((x * 0x71c5) & 0x5145) == 0x5145;
}

它使用乘法逆元技巧，首先除以3^10，然后再除以3^5。最后，需要检查结果是否为1、3、9、27、81或243，这是通过一些我通过试错找到的简单哈希来完成的。

在我的CPU（Intel Sandy Bridge）上，它非常快，但不如starblue方法使用二进制对数（该方法在该CPU上已实现硬件）。但在没有此类指令或不希望使用查找表时，它可能是一种替代方案。

你测试过了吗？我对这种黑客攻击非常熟悉，但这真的很令人惊讶。 - maaartinus
1
我尝试了所有32位值，结果都正确。 - Falk Hüffner
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接