algorithm - How to check if an integer is a power of 3?

Question

I saw this question, and pop up this idea.

Answer 1

There exists a constant time (pretty fast) method for integers of limited size (e.g. 32-bit integers).

Note that for an integer N that is a power of 3 the following is true:

1. For any M <= N that is a power of 3, M divides N.
2. For any M <= N that is not a power 3, M does not divide N.

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

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.