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

Question

我看到了这个问题,并提出了这个想法.

Answer 1

对于有限大小的整数(例如32位整数)存在恒定时间(非常快)的方法.

请注意,对于N幂为3的整数,以下情况为真:

1. 对于任何M <= N3的幂,M除以N.
2. 对于任何M <= N不是权力3,M不分裂N.

适合32位的3的最大功率是3486784401(3^20).这给出了以下代码:

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;
}

通常,幻数是:

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

小心浮点舍入误差,使用像Wolfram Alpha这样的数学计算器来计算常数.例如,对于2^63-1(signed int64),C++和Java都给出了4052555153018976256,但正确的值是4052555153018976267.

Answer 2

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

请注意,1是三次的第0次幂.

编辑:您还需要在循环之前检查零,因为循环不会因n = 0而终止(感谢Bruno Rothgiesser).

Answer 3

我发现自己有点想,如果用'整数'表示'签名的32位整数',那么(伪代码)

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

它具有一定的美观(最后一个数字是3 ^ 19,因此没有荒谬的数量).即使对于无符号的64位整数,仍然只有41个案例(感谢@Alexandru指出我的大脑滑动).对于任意精度算术来说当然是不可能的......

Answer 4

我对此感到惊讶. 每个人似乎都错过了最快的算法.

以下算法平均速度更快 - 在某些情况下更快 - 比简单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通常是单个指令,需要一个周期.在其他情况下,它扩展为div,然后是mul和add,这将更像是三个周期.通用算法的每一步看起来很长,但它实际上只包括: 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次(41次,64位).我在这里提出的算法永远不会超过大约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".

Answer 5

如果(log n)/(log 3)是积分则n是3的幂.

Answer 6

递归除以3,检查余数是否为零并重新应用于商.

注意1是有效答案,因为零功率为1的3是要注意的边缘情况.

Answer 7

非常有趣的问题,我喜欢starblue的答案,这是他的算法的变体,它会更快地收敛到解决方案:

private bool IsPow3(int n)
{
    if (n == 0) return false;
    while (n % 9 == 0)
    {
        n /= 9;
    }
    return (n == 1 || n == 3);
}

Answer 8

这是对这些问题下所有优秀答案的总结,性能数据可以从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.基本转换

将整数转换为基数为3的数字,并检查它是否被写为前导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集的整数限制

这个想法类似于#4,但使用一组来存储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;
}

Answer 9

在两个幂之间,最多有三个幂.所以以下是一个快速测试:

1. n通过查找1数字中前导位的位置来查找二进制对数.这是非常快的,因为现代处理器有一个特殊的指令.(否则你可以通过一点点思考来做,看看Bit Twiddling Hacks).

2. 在由该位置索引的表中查找三个的潜在幂并与之比较n(如果没有三个幂,则可以存储具有不同二进制对数的任何数字).

3. 如果他们是平等的,则返回是,否则返回.

运行时主要取决于访问表条目所需的时间.如果我们使用机器整数,表很小,可能在缓存中(我们使用它数百万次,否则这种级别的优化没有意义).

Answer 10

这是Ray Burns 方法在 C 中的一个很好且快速的实现：

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（英特尔 Sandy Bridge）上，它非常快，但不如使用二进制对数的 starblue 方法（在该 CPU 的硬件中实现）快。但是在没有这种指令的 CPU 上，或者当查找表不受欢迎时，它可能是一种替代方法。

Answer 11

你的输入有多大？使用 O(log(N)) 内存，您可以做得更快，O(log(log(N))。预先计算 3 的幂，然后对预先计算的值进行二分搜索。

Answer 12

简单而恒定的解决方案:

return n == power(3, round(log(n) / log(3)))