algorithm - 如何判断一个整数是不是3的幂？

Question

我看到了this question , 并弹出这个想法。

Answer 1

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

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

1. 对于任何M <= N那是 3 的幂，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;
}

一般来说，魔数(Magic Number)是:

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

注意浮点舍入错误，使用像 Wolfram Alpha 这样的数学计算器来计算常数。例如 2^63-1 (signed int64) C++ 和 Java 都给出 4052555153018976256 , 但正确的值为 4052555153018976267 .