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

我看到这个问题 ，并popup这个想法。

Answer 1

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

注意1是三的零次幂。

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

Answer 2

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

请注意，对于3的幂的整数N ，以下是正确的：

1. 对于任何M <= N是3的幂， M除N
2. 对于任何不是幂3的M <= N ， M不分N

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这样的math计算器来计算常量。 例如，对于2^63-1 （signed int64），C ++和Java都给出4052555153018976256 ，但正确的值是4052555153018976267 。

Answer 3

我发现自己有点想，如果用“整数”表示“有符号的32位整数”，那么（伪代码）

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

有一定的美丽的简单性（最后一个数字是3 ^ 19，所以没有荒唐的案件数量）。 即使是一个无符号的64位整数，仍然只有41例（谢谢@亚历山大指出我的大脑滑移）。 任意精度算术当然是不可能的…

Answer 4

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

以下algorithm平均速度更快 – 在某些情况下速度要快得多 – 比简单的一次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，这个完全需要三个循环。 一般algorithm的每一步看起来DivRem, cmp, cmove, cmp, cand, cjmp, add长，但实际上它只包含： DivRem, cmp, cmove, cmp, cand, cjmp, add 。 可用的并行性很多，因此在一个典型的双向超标量处理器中，每个步骤可能会在大约4个时钟周期内执行，从而保证大约25个时钟周期的最坏执行时间。

如果input值均匀分布在UInt32的范围内，则下面是与此algorithm相关的概率：

• 在第一条优化线之前或之后返回：66％的时间
• 在第二条优化线之前或之后返回：89％的时间
• 在第一个通用algorithm步骤之前或之后返回：99.998％的时间
• 在第二个通用algorithm步骤之前或之后返回：99.99998％的时间
• 在第三个通用algorithm步骤之前或之后返回：99.999997％的时间

该algorithm比while(n%3==0) n/=3循环简单，具有以下几率：

• 在第一次迭代中返回：66％的时间
• 返回前两个迭代：89％的时间
• 返回前三个迭代：97％的时间
• 返回前四个迭代：98.8％的时间
• 返回前五个迭代：99.6％的时间…等等…
• 返回前12次迭代：99.9998％的时间…超越…

更重要的是，这个algorithm可以更有效地处理三个（及其倍数）的中等和大的幂：在最坏的情况下，简单的algorithm将消耗超过100个CPU周期，因为它将循环20次（对于64位为41次）。 我在这里提出的algorithm永远不会超过约25个周期。

扩展到64位

把上面的algorithm扩展到64位是微不足道的 – 只需再增加一个步骤即可。 以下是64位版本的上述algorithm，针对没有高效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得到1000000的商和0的余数，这些增加到10000000。
2. 我除以10 ^ 5得到一个商数为100，余数为0.这些加到100。
3. 我除以10 ^ 3得到一个0和一个100的余数，这些加到100。
4. 我除以10 ^ 2得到商1和余数0.这些加1。

因为我从10的幂开始，每次除以10的幂，我都以零商或零余数结束。 如果我是从10开始的，我迟早会得到一个非零商或余数。

在这个例子中，我select了10,5和3的指数来匹配前面提供的代码，并且仅仅为它的join而添加了2。 其他指数也可以工作：在给定最大input值和输出允许的最大功率10的情况下，有一个简单的select理想指数的algorithm，但是这个余量没有足够的空间来容纳它。

注意：在整个解释中，你可能一直在考虑十位数，但是如果你在三位基本思想中，上面的整个解释都可以被理解和理解 ，除了指数会被不同地表示（而不是“10” “5”，“3”和“2”我不得不说“101”，“12”，“10”和“2”）。

Answer 5

如果（log n）/（log 3）是整数，那么n是3的幂。

Answer 6

recursion地除以3，检查余数为零并重新应用于商。

请注意，1是一个有效的答案，因为3的零功率为1是需要小心的边缘情况。

Answer 7

非常有趣的问题，我喜欢starblue的答案 ，这是他的algorithm的一个变种，它将更快地收敛到解决scheme：

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

Answer 8

两权之间最多只有三权。 所以下面是一个快速testing：

1. 通过查找数字中前导1位的位置来查找n的二进制对数。 这是非常快的，因为现代处理器有一个特殊的指令。 （否则，你可以做一点点twiddling，看Bit Twiddling黑客 ）。

2. 在由该位置索引的表格中查找三个潜在的力量，并与n进行比较（如果没有三次幂，则可以以不同的二进制对数存储任何数字）。

3. 如果他们是平等的回报是的，否则不。

运行时间主要取决于访问表项所需的时间。 如果我们使用机器整数，表格很小，而且可能在caching中（我们正在使用它数百万次，否则这个优化级别是没有意义的）。

Answer 9

简单和恒定时间的解决scheme：

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

Answer 10

你的投入有多大？ 用O（log（N））的内存可以做得更快，O（log（log（N））预先计算3的幂，然后在预先计算的值上进行二分search。

Answer 11

这里是一个很好和快速的实施雷伯恩斯的方法在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）上，速度非常快，但是不像使用二进制对数 （在该CPU的硬件中实现） 的starblue方法那么快。 但是在没有这样的指令的CPU上，或者在查找表是不合需要的情况下，这可能是另一种select。

Answer 12

对于非常大的数字n ，可以使用下面的math技巧来加速运算

  n % 3 == 0 

这真的很慢，很可能是任何依赖重复检查余数的algorithm的瓶颈。 你必须了解模块化algorithm，以跟随我正在做什么，这是基本数论的一部分。

令x =Σk a _k 2 ^k为感兴趣的数量。 我们可以让这个和的上界是∞，并且知道某个k> M的_k = 0

0≡x≡Σk a _k 2 k≡Σk a _2k 2 ^2k + a _{2k + 1} 2 ^{2k +} 1≡Σk 2 ^2k （a _2k + a _{2k + 1} 2）≡Σk a _2k + a _{2k + 1} 2（mod 3）

因为2 2 ^k≡4 k≡1 k≡1（mod 3）。

给定二进制表示的数字x与2n + 1位为

x ₀ x ₁ x ₂ … x _{2n + 1}

其中x k∈{0,1}可以分组奇偶对

（x ₀ x ₁ ）（x ₂ x ₃ ）…（x _2n x _{2n + 1} ）。

令q表示forms（1 0）的配对数，令r表示forms（0 1）的配对数。 然后从上面的公式得出3 | x当且仅当3 | （q + 2r）。 此外，可以certificate3 |（q + 2r）当且仅当q和r除以3时具有相同的余数。

所以确定一个数是否可​​以被3整除的algorithm可以做如下

  q = 0, r = 0 for i in {0,1, .., n} pair <- (x_{2i} x_{2i+1}) if pair == (1 0) switch(q) case 0: q = 1; break; case 1: q = 2; break; case 2: q = 0; break; else if pair == (0 1) switch(r) case 0: r = 1; break; case 1: r = 2; break; case 2: r = 0; return q == r 

这个algorithm比使用％更有效率。

—多年后编辑—-

我花了几分钟的时间来实现这个python的基本版本，检查所有数字为10 ^ 4的真实。 我将其包含在下面以供参考。 显然，为了利用这一点，尽可能靠近硬件来实现这一点。 这种扫描技术可以扩展到任何想要通过改变派生的数字。 我也猜想algorithm中的“扫描”部分可以用类似于FFT的recursionO(log n)types公式重新expression，但我不得不考虑这一点。

 #!/usr/bin/python def bits2num(bits): num = 0 for i,b in enumerate(bits): num += int(b) << i return num def num2bits(num): base = 0 bits = list() while True: op = 1 << base if op > num: break bits.append(op&num !=0) base += 1 return "".join(map(str,map(int,bits)))[::-1] def div3(bits): n = len(bits) if n % 2 != 0: bits = bits + '0' n = len(bits) assert n % 2 == 0 q = 0 r = 0 for i in range(n/2): pair = bits[2*i:2*i+2] if pair == '10': if q == 0: q = 1 elif q == 1: q = 2 elif q == 2: q = 0 elif pair == '01': if r == 0: r = 1 elif r == 1: r = 2 elif r == 2: r = 0 else: pass return q == r for i in range(10000): truth = (i % 3) == 0 bits = num2bits(i) check = div3(bits) assert truth == check 

Answer 13

你可以做得比重复的分割，这需要O（lg（X）* | division |）时间。 本质上，你在3的幂上进行二分search。真的，我们将在N上进行二分search，其中3 ^ N =input值）。 设N的Pth二进制数对应乘以3 ^（2 ^ P），forms3 ^（2 ^ P）的值可以通过重复平方来计算。

algorithm

• 让input值为X.
• 产生一个重复的平方值列表L，一旦你传递X就结束。
• 让你的候选值为T，初始化为1。
• 对于反向L中的每个E，如果T * E <= X，则令T * = E.
• 返回T == X.

复杂：

O（lg（lg（X））* |乘法|） – 在L上生成和迭代需要lg（lg（X））次迭代，乘法是迭代中最昂贵的操作。

Answer 14

最快的解决scheme是要么testing如果n > 0 && 3**19 % n == 0在另一个答案或完美的散列（下面）给出。 首先我给出两个基于乘法的解决scheme。

乘法

我想知道为什么每个人都错过了乘法比分区快得多：

 for (int i=0, pow=1; i<=19, pow*=3; ++i) { if (pow >= n) { return pow == n; } } return false; 

只要尝试一切权力，当它变得太大时停下来。 避免溢出，因为3**19 = 0x4546B3DB是签名32位int中最大的电源配件。

乘以二进制search

二进制search可能看起来像

 int pow = 1; int next = pow * 6561; // 3**8 if (n >= next) pow = next; next = pow * 81; // 3**4 if (n >= next) pow = next; next = pow * 81; // 3**4; REPEATED if (n >= next) pow = next; next = pow * 9; // 3**2 if (n >= next) pow = next; next = pow * 3; // 3**1 if (n >= next) pow = next; return pow == next; 

重复一个步骤，从而可以准确地达到最大指数19 = 8+4+4+2+1 。

完美的哈希

有三十个幂的三十个32位整数，所以我们拿一个32个元素的表。 通过一些实验，我发现了完美的散列函数

 def hash(x): return (x ^ (x>>1) ^ (x>>2)) & 31; 

将每个权力映射到0到31之间的独特索引。其余的东西是微不足道的：

 // Create a table and fill it with some power of three. table = [1 for i in range(32)] // Fill the buckets. for n in range(20): table[hash(3**n)] = 3**n; 

现在我们有了

 table = [ 1162261467, 1, 3, 729, 14348907, 1, 1, 1, 1, 1, 19683, 1, 2187, 81, 1594323, 9, 27, 43046721, 129140163, 1, 1, 531441, 243, 59049, 177147, 6561, 1, 4782969, 1, 1, 1, 387420489] 

并可以通过非常快速的testing

 def isPowerOfThree(x): return table[hash(x)] == x 

Answer 15

这是这个问题下所有好的答案的摘要，可以从LeetCode文章中findperformance数字。

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。它的灵感来自于通过执行n & (n - 1) == 0来检查数是2的幂的解决schemen & (n - 1) == 0

时间复杂度：O（log（n））取决于语言和编译器，空间复杂度：O（log（n））

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

3math

如果n = 3^i ，则i = log(n) / log(3) ，从而得出解决scheme

时间复杂度：取决于语言和编译器，空间复杂度：O（1）

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

4个整数限制

因为3^19 = 1162261467是3位数的最大幂在32位整数，所以我们可以这样做

时间复杂度：O（1），空间复杂度：O（1）

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

5整数限制与设置

这个想法与＃4类似，但是使用一组来存储所有可能的3个数字（从3 ^ 0到3 ^ 19）。 它使代码更具可读性。

6recursion（C ++ 11）

此解决scheme特定于C ++ 11，使用模板元编程，以便编译器将计算结果replace为调用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 16

你的问题很容易通过定义一个简单的函数来运行检查你的答案。 下面显示的示例实现是用Python编写的，但如果需要的话，用其他语言重写应该不难。 与此答案的最后一个版本不同，下面显示的代码更加可靠。

 Python 3.6.0 (v3.6.0:41df79263a11, Dec 23 2016, 08:06:12) [MSC v.1900 64 bit (AMD64)] on win32 Type "copyright", "credits" or "license()" for more information. >>> import math >>> def power_of(number, base): return number == base ** round(math.log(number, base)) >>> base = 3 >>> for power in range(21): number = base ** power print(f'{number} is ' f'{"" if power_of(number, base) else "not "}' f'a power of {base}.') number += 1 print(f'{number} is ' f'{"" if power_of(number, base) else "not "}' f'a power of {base}.') print() 1 is a power of 3. 2 is not a power of 3. 3 is a power of 3. 4 is not a power of 3. 9 is a power of 3. 10 is not a power of 3. 27 is a power of 3. 28 is not a power of 3. 81 is a power of 3. 82 is not a power of 3. 243 is a power of 3. 244 is not a power of 3. 729 is a power of 3. 730 is not a power of 3. 2187 is a power of 3. 2188 is not a power of 3. 6561 is a power of 3. 6562 is not a power of 3. 19683 is a power of 3. 19684 is not a power of 3. 59049 is a power of 3. 59050 is not a power of 3. 177147 is a power of 3. 177148 is not a power of 3. 531441 is a power of 3. 531442 is not a power of 3. 1594323 is a power of 3. 1594324 is not a power of 3. 4782969 is a power of 3. 4782970 is not a power of 3. 14348907 is a power of 3. 14348908 is not a power of 3. 43046721 is a power of 3. 43046722 is not a power of 3. 129140163 is a power of 3. 129140164 is not a power of 3. 387420489 is a power of 3. 387420490 is not a power of 3. 1162261467 is a power of 3. 1162261468 is not a power of 3. 3486784401 is a power of 3. 3486784402 is not a power of 3. >>> 

注意：最后一次修订已经导致这个答案几乎与TMS的答案一样 。

Answer 17

基于解决scheme…

 DECLARE @LastExponent smallint, @SearchCase decimal(38,0) SELECT @LastExponent = 79, -- 38 for bigint @SearchCase = 729 ;WITH CTE AS ( SELECT POWER(CAST(3 AS decimal(38,0)), ROW_NUMBER() OVER (ORDER BY c1.object_id)) AS Result, ROW_NUMBER() OVER (ORDER BY c1.object_id) AS Exponent FROM sys.columns c1, sys.columns c2 ) SELECT Result, Exponent FROM CTE WHERE Exponent <= @LastExponent AND Result = @SearchCase 

在SET STATISTICS TIME ON ，logging最低的1毫秒。

Answer 18

另一种方法是在编译时生成一个表。 好的是，你可以把它扩展到4,5,6,7的能力

 template<std::size_t... Is> struct seq { }; template<std::size_t N, std::size_t... Is> struct gen_seq : gen_seq<N-1, N-1, Is...> { }; template<std::size_t... Is> struct gen_seq<0, Is...> : seq<Is...> { }; template<std::size_t N> struct PowersOfThreeTable { std::size_t indexes[N]; std::size_t values[N]; static constexpr std::size_t size = N; }; template<typename LambdaType, std::size_t... Is> constexpr PowersOfThreeTable<sizeof...(Is)> generatePowersOfThreeTable(seq<Is...>, LambdaType evalFunc) { return { {Is...}, {evalFunc(Is)...} }; } template<std::size_t N, typename LambdaType> constexpr PowersOfThreeTable<N> generatePowersOfThreeTable(LambdaType evalFunc) { return generatePowersOfThreeTable(gen_seq<N>(), evalFunc); } template<std::size_t Base, std::size_t Exp> struct Pow { static constexpr std::size_t val = Base * Pow<Base, Exp-1ULL>::val; }; template<std::size_t Base> struct Pow<Base, 0ULL> { static constexpr std::size_t val = 1ULL; }; template<std::size_t Base> struct Pow<Base, 1ULL> { static constexpr std::size_t val = Base; }; constexpr std::size_t tableFiller(std::size_t val) { return Pow<3ULL, val>::val; } bool isPowerOfThree(std::size_t N) { static constexpr unsigned tableSize = 41; //choosen by fair dice roll static constexpr PowersOfThreeTable<tableSize> table = generatePowersOfThreeTable<tableSize>(tableFiller); for(auto a : table.values) if(a == N) return true; return false; } 

Answer 19

Python solution

 from math import floor from math import log def IsPowerOf3(number): p = int(floor(log(number) / log(3))) power_floor = pow(3, p) power_ceil = power_floor * 3 if power_floor == number or power_ceil == number: return True return False 

This is much faster than the simple divide by 3 solution.

Proof: 3 ^ p = number

p log(3) = log(number) (taking log both side)

p = log(number) / log(3)

Answer 20

Here's a general algorithm for finding out if a number is a power of another number:

 bool IsPowerOf(int n,int b) { if (n > 1) { while (n % b == 0) { n /= b; } } return n == 1; } 

Answer 21

 #include<iostream> #include<string> #include<cmath> using namespace std; int main() { int n, power=0; cout<<"enter a number"<<endl; cin>>n; if (n>0){ for(int i=0; i<=n; i++) { int r=n%3; n=n/3; if (r==0){ power++; } else{ cout<<"not exactly power of 3"; return 0; } } } cout<<"the power is "<<power<<endl; } 

Answer 22

This is a constant time method! 是。 O(1). For numbers of fixed length, say 32-bits.

Given that we need to check if an integer n is a power of 3, let us start thinking about this problem in terms of what information is already at hand.

1162261467 is the largest power of 3 that can fit into an Java int.
1162261467 = 3^19 + 0

The given n can be expressed as [(a power of 3) + (some x )]. I think it is fairly elementary to be able to prove that if x is 0(which happens iff n is a power of 3), 1162261467 % n = 0.

The general idea is that if X is some power of 3, X can be expressed as Y/3a , where a is some integer and X < Y. It follows the exact same principle for Y < X. The Y = X case is elementary.

So, to check if a given integer n is a power of three, check if n > 0 && 1162261467 % n == 0 .