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.

Answer 2

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

Note that 1 is the zeroth power of three.

Edit: You also need to check for zero before the loop, as the loop will not terminate for n = 0 (thanks to Bruno Rothgiesser).