如何检查一个整数是否是 3 的幂? [英] How to check if an integer is a power of 3?

问题描述

我看到了 来计算常数.例如对于 2^63-1(signed int64)，C++ 和 Java 都给出 4052555153018976256，但正确的值是 4052555153018976267.

I saw this question, and pop up this idea.

解决方案

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.

这篇关于如何检查一个整数是否是 3 的幂?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！