如何检查整数是否为3的幂? [英] How to check if an integer is a power of 3?
问题描述
我看到了这个问题,然后弹出这个主意.
I saw this question, and pop up this idea.
推荐答案
对于有限大小的整数(例如32位整数),存在一种恒定时间(相当快)的方法.
There exists a constant time (pretty fast) method for integers of limited size (e.g. 32-bit integers).
请注意,对于N
的整数(为3的幂),为true:
Note that for an integer N
that is a power of 3 the following is true:
- 对于任何
M <= N
的3的幂,M
除以N
. - 对于任何不是3的
M <= N
,M
不会除以N
.
- For any
M <= N
that is a power of 3,M
dividesN
. - For any
M <= N
that is not a power 3,M
does not divideN
.
适合32位的3的最大幂是3486784401
(3^20
).这给出了以下代码:
The biggest power of 3 that fits into 32 bits is 3486784401
(3^20
). This gives the following code:
bool isPower3(std::uint32_t value) {
return value != 0 && 3486784401u % value == 0;
}
对于带符号的32位,它是1162261467
(3^19
):
Similarly for signed 32 bits it is 1162261467
(3^19
):
bool isPower3(std::int32_t value) {
return value > 0 && 1162261467 % value == 0;
}
一般而言,魔术数字是:
In general the magic number is:
== pow(3, floor(log(MAX) / log(3)))
Careful with floating point rounding errors, use a math calculator like Wolfram Alpha to calculate the constant. For example for 2^63-1
(signed int64) both C++ and Java give 4052555153018976256
, but the correct value is 4052555153018976267
.
这篇关于如何检查整数是否为3的幂?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!