logo标签列表

如何检查一个整数是否是3的幂？

algorithmmath
67
9
常常会有新问题产生，但我建议考虑概括性的问题。例如，“N的幂？”其中N是任意整数。 - Michael Easter
3
@Michael：我刚刚添加了一个比starblue提供的更快的答案：我的算法最坏情况下只需要五次除法。在我的回答中，我还讨论了“N的幂”的一般情况。 - Ray Burns
3
这很荒谬。接下来是什么？5的力量吗？ - Alexandre Santos
@AlexandreSantos 没错！这是在技术面试中被问到的问题；5的幂！ - Hengameh
然而，3和5（如7、9、15、17等）是2的幂次方+/-1，有趣的“数字”求和技巧适用。 - greybeard
显示剩余3条评论
25个回答
5

简单且时间复杂度恒定的解决方案：

return n == power(3, round(log(n) / log(3)))
2
恒定的长时间。可能有几个泰勒级数隐藏在其中。 - EvilTeach
@EvilTeach，你可以预先计算一个log_3并像这样使用它：https://dev59.com/ZHI-5IYBdhLWcg3wiY7a#24274850 - TWiStErRob
是的，那会有所帮助。尽管如此，日志记录是昂贵的。 - EvilTeach
5

你的输入数据有多大？如果使用O(log(N))的内存，可以使用更快的O(log(log(N)))算法。预计算3的幂次方，然后在预计算的值上执行二分查找。

如果要找到许多3的幂，我会同意这种做法，但只有40个小于2^64，我认为线性搜索可能比二分搜索表现更好。不过，我并不想测试这个！ - High Performance Mark
预计算的想法很好，如果操作需要多次执行，这个想法非常有用。 - Paul Turner
甚至可能创建一个高效的哈希。 - MSalters
4

对于非常大的数字n，您可以使用以下数学技巧来加速操作：

  n % 3 == 0

这段代码非常缓慢，很可能是任何依赖于重复检查余数的算法的瓶颈。您必须理解模算术才能跟上我正在做的事情，这是初等数论的一部分。

假设x = Σ k a k 2 k 是我们感兴趣的数字。我们可以让总和的上限为∞，理解a k = 0对于k > M。 然后：

0 ≡ x ≡ Σ k a k 2 k ≡ Σ k a 2k 2 2k + a 2k+1 2 2k+1 ≡ Σ k 2 2k ( a 2k + a 2k+1 2) ≡ Σ k a 2k + a 2k+1 2 (mod 3)

因为22k ≡ 4 k ≡ 1k ≡ 1 (mod 3)。

给定一个具有2n + 1位的数字x的二进制表示为：

x0 x1 x2 ... x2n+1

其中xk ∈ {0、1}，您可以将奇偶对分组

(x0 x1) (x2 x3) ... (x2n x2n+1)。

设q表示形式为(1 0)的配对数，r表示形式为(0 1)的配对数。那么从上面的等式可以得出：如果且仅当3 | (q + 2r)时，3 | x。此外，您可以证明：当被3除时，q和r具有相同的余数，当且仅当3 | (q + 2r)。

因此，判断一个数字是否可以被3整除的算法如下：

 q = 0, r = 0
 for i in {0,1, .., n}
     pair <- (x_{2i} x_{2i+1})
     if pair == (1 0)
         switch(q)
             case 0:
                 q = 1;
                 break;
             case 1:
                 q = 2;
                 break;
             case 2:
                 q = 0;
                 break;
     else if pair == (0 1)
         switch(r)
             case 0:
                 r = 1;
                 break;
             case 1:
                 r = 2;
                 break;
             case 2:
                 r = 0;
 return q == r

这种算法比使用%更高效。

--- 许多年后的编辑 ---

我花了几分钟时间在Python中实现了一个简单版本，检查所有数字是否都符合10^4。下面是参考代码。显然，为了尽可能地接近硬件，需要将其实现。通过改变派生可以将此扫描技术扩展到任何想要的数字。我还猜测算法的“扫描”部分可以重新制定为类似于FFT的递归O(log n)类型公式，但我需要思考一下。

#!/usr/bin/python

def bits2num(bits):
    num = 0
    for i,b in enumerate(bits):
        num += int(b) << i
    return num

def num2bits(num):
    base = 0
    bits = list()
    while True:
        op = 1 << base
        if op > num:
            break
        bits.append(op&num !=0)
        base += 1
    return "".join(map(str,map(int,bits)))[::-1]

def div3(bits):

    n = len(bits)

    if n % 2 != 0:
        bits = bits + '0'

    n = len(bits)

    assert n % 2 == 0

    q = 0
    r = 0
    for i in range(n/2):
        pair = bits[2*i:2*i+2]
        if pair == '10':
            if q == 0:
                q = 1
            elif q == 1:
                q = 2
            elif q == 2:
                q = 0
        elif pair == '01':
            if r == 0:
                r = 1
            elif r == 1:
                r = 2
            elif r == 2:
                r = 0
        else:
            pass

    return q == r

for i in range(10000):
    truth = (i % 3)  == 0
    bits = num2bits(i)
    check  = div3(bits)
    assert truth == check
这是什么语言？执行 x % 3 一百万（或十亿）次的时间和执行相同次数的该算法的时间是多少？ - Chip Uni
1
我应该重新表述一下，我们不知道一种乘法算法，可以在O(n)时间内计算出n位数的乘积。 - ldog
1
你忽略了一个重要的事实：硬件比软件快得多。只要硬件中有乘法，% 就会更快。不过你的算法对于大数库仍然可能有用。 - LaC
嗯，我同意硬件通常更快。我认为最初的问题是针对输入数字非常大的情况提出的，否则为什么要费事呢？只需创建一个查找表，以表示您想表示的最大3的幂，查找表的大小将是对数级别的，并且相当紧凑。 - ldog
这只是一个通过查看二进制数字来测试3的可除性的测试（类似于十进制数可被11整除的测试）。在实践中，您将使用位操作使其更快。 - starblue
显示剩余3条评论
3
您可以使用更好的方法，而不是重复地进行除法计算，其时间复杂度为O(lg(X) * |division|)。实际上，您可以对3的幂进行二进制搜索。我们将对N进行二进制搜索，其中3^N=输入值。设置N的第P个二进制数字相当于乘以3^(2^P)，而形式为3^(2^P)的值可以通过重复平方计算得出。
算法：
- 将输入值X存储在列表L中，并生成重复平方值列表，直到超过X。 - 让您的候选值T初始化为1。 - 对于倒置列表L中的每个E，如果T*E<=X，则让T*=E。 - 返回T==X。
该算法复杂度为O(lg(lg(X)) * |multiplication|)，生成和迭代L需要lg(lg(X))次迭代，而乘法是迭代中最昂贵的操作。
我不确定这种方法在实践中是否比重复除法更好，因为基于除法的解决方案在典型情况下会非常快速地短路。一旦得到余数，你就可以停止除法运算，而这通常是在对三分之二的随机输入进行第一次操作后。8/9的随机输入只需要不超过2次操作；等等。除非除法比乘法慢得多（这在现今通常不是这样），否则除法方法通常会在你完成生成L之前就得出答案。 - John Y
3

最快的解决方案是按照另一个答案中给出的方法测试是否n > 0 && 3**19 % n == 0，或者使用完美哈希（下文介绍）。首先，我将提供两种基于乘法的解决方案。

乘法

我想知道为什么每个人都错过了乘法比除法快得多这一点：

for (int i=0, pow=1; i<=19, pow*=3; ++i) {
    if (pow >= n) {
        return pow == n;
    }
}
return false;

尝试所有的幂，当它变得太大时停止。避免溢出，因为3 ** 19 = 0x4546B3DB是适合于有符号32位整数的最大幂。

二分查找乘法

二分查找的形式可能如下：

int pow = 1;
int next = pow * 6561; // 3**8
if (n >= next) pow = next;
next = pow * 81; // 3**4
if (n >= next) pow = next;
next = pow * 81; // 3**4; REPEATED
if (n >= next) pow = next;
next = pow * 9; // 3**2
if (n >= next) pow = next;
next = pow * 3; // 3**1
if (n >= next) pow = next;
return pow == next;

这里有一个步骤需要重复执行，以便能够达到最大指数19 = 8+4+4+2+1的要求。

完美哈希

在32位有符号整数中，可以容纳20个3的幂次，因此我们取一个32个元素的表格。通过一些实验，我找到了完美哈希函数。

def hash(x):
    return (x ^ (x>>1) ^ (x>>2)) & 31;

将每个权力映射到一个介于0和31之间的唯一索引。其余的都是琐事：

// Create a table and fill it with some power of three.
table = [1 for i in range(32)]
// Fill the buckets.
for n in range(20): table[hash(3**n)] = 3**n;

现在我们有：
table = [
     1162261467, 1, 3, 729, 14348907, 1, 1, 1,
     1, 1, 19683, 1, 2187, 81, 1594323, 9,
     27, 43046721, 129140163, 1, 1, 531441, 243, 59049,
     177147, 6561, 1, 4782969, 1, 1, 1, 387420489]

并且可以通过快速测试进行验证。
def isPowerOfThree(x):
    return table[hash(x)] == x
你可以结合除法和乘法：先进行一次除法，检查是否为零，然后重复进行乘法和比较，以避免溢出。 - greybeard
1
我想知道为什么大家都忽略了乘法比除法快得多这一点 - 是每个人都？ - greybeard
@老程序员 将除法和乘法结合起来听起来很慢，因为即使一个除法也太昂贵了。+++我看到我错过了你的评论。 - maaartinus
1
即使是一次除法[看起来]也很昂贵。我_期望_编译器将常数除法转换为乘法，如果那样会更快。 - greybeard
1

通过定义一个简单的函数来运行检查，回答您的问题相当容易。下面展示的示例实现是用Python编写的，但如果需要，重写成其他语言也不难。与上一个答案的版本不同，下面展示的代码更加可靠。

Python 3.6.0 (v3.6.0:41df79263a11, Dec 23 2016, 08:06:12) [MSC v.1900 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> import math
>>> def power_of(number, base):
    return number == base ** round(math.log(number, base))

>>> base = 3
>>> for power in range(21):
    number = base ** power
    print(f'{number} is '
          f'{"" if power_of(number, base) else "not "}'
          f'a power of {base}.')
    number += 1
    print(f'{number} is '
          f'{"" if power_of(number, base) else "not "}'
          f'a power of {base}.')
    print()


1 is a power of 3.
2 is not a power of 3.

3 is a power of 3.
4 is not a power of 3.

9 is a power of 3.
10 is not a power of 3.

27 is a power of 3.
28 is not a power of 3.

81 is a power of 3.
82 is not a power of 3.

243 is a power of 3.
244 is not a power of 3.

729 is a power of 3.
730 is not a power of 3.

2187 is a power of 3.
2188 is not a power of 3.

6561 is a power of 3.
6562 is not a power of 3.

19683 is a power of 3.
19684 is not a power of 3.

59049 is a power of 3.
59050 is not a power of 3.

177147 is a power of 3.
177148 is not a power of 3.

531441 is a power of 3.
531442 is not a power of 3.

1594323 is a power of 3.
1594324 is not a power of 3.

4782969 is a power of 3.
4782970 is not a power of 3.

14348907 is a power of 3.
14348908 is not a power of 3.

43046721 is a power of 3.
43046722 is not a power of 3.

129140163 is a power of 3.
129140164 is not a power of 3.

387420489 is a power of 3.
387420490 is not a power of 3.

1162261467 is a power of 3.
1162261468 is not a power of 3.

3486784401 is a power of 3.
3486784402 is not a power of 3.

>>>

注意： 最近的修订使得这个答案与TMS' answer几乎相同。

2
除非我大错特错，否则这是一个非常愚蠢的实现。Math.Log 不太可能计算出在尾数处全部为 0 的数字；换句话说，它非常忽略浮点舍入误差。 - Carl Smotricz
2
仅供参考 >>> [((math.log(3**i) / math.log(3)) % 1 == 0) for i in range(20)] [True, True, True, True, True, False, True, True, True, True, False, True, True, False, True, False, True, False, True, True] - YOU
1
所以该算法对3^6、3^11和其他数值无法成功。谢谢，S.Mark。我手头没有Python，所以无法自己提供这个证明。 - Carl Smotricz
2
Noctis，我很抱歉听起来有些严厉，但是如果一个算法不能对其定义的输入范围内的所有值产生正确的结果，我认为它是不可接受的。 - Carl Smotricz
@CarlSmotricz 使用log10而不是自然对数应该能够适用于32位整数范围（来自方法2）。 - TWiStErRob
显示剩余5条评论
0

我对一些解决方案进行了时间测量（C＃，平台目标x64）。

using System;
class Program
{
    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();
        for (uint n = ~0u; n > 0; n--) ;
        Console.WriteLine(sw.Elapsed);              // nada   1.1 s
        sw.Restart();
        for (uint n = ~0u; n > 0; n--) isPow3a(n);
        Console.WriteLine(sw.Elapsed);              // 3^20  17.3 s
        sw.Restart();
        for (uint n = ~0u; n > 0; n--) isPow3b(n);
        Console.WriteLine(sw.Elapsed);              // % /   10.6 s
        Console.Read();
    }

    static bool isPow3a(uint n)  // Elric
    {
        return n > 0 && 3486784401 % n == 0;
    }

    static bool isPow3b(uint n)  // starblue
    {
        if (n > 0) while (n % 3 == 0) n /= 3;
        return n == 1;
    }
}

另一种（挑剔的）方式。

using System;
class Program
{
    static void Main()
    {
        Random rand = new Random(0); uint[] r = new uint[512];
        for (int i = 0; i < 512; i++)
            r[i] = (uint)(rand.Next(1 << 30)) << 2 | (uint)(rand.Next(4));
        var sw = System.Diagnostics.Stopwatch.StartNew();
        for (int i = 1 << 23; i > 0; i--)
            for (int j = 0; j < 512; j++) ;
        Console.WriteLine(sw.Elapsed);                    //   0.3 s
        sw.Restart();
        for (int i = 1 << 23; i > 0; i--)
            for (int j = 0; j < 512; j++) isPow3c(r[j]);
        Console.WriteLine(sw.Elapsed);                    //  10.6 s
        sw.Restart();
        for (int i = 1 << 23; i > 0; i--)
            for (int j = 0; j < 512; j++) isPow3b(r[j]);
        Console.WriteLine(sw.Elapsed);                    //   9.0 s
        Console.Read();
    }

    static bool isPow3c(uint n)
    { return (n & 1) > 0 && 3486784401 % n == 0; }

    static bool isPow3b(uint n)
    { if (n > 0) while (n % 3 == 0) n /= 3; return n == 1; }
}
请使用 isPow3x(uint n) 的结果（WriteLine() 建议自己）并说明所使用的编译器和标志。 - greybeard
我（你）可以使用……使用仪器化函数的结果并不是为了了解结果，而是为了防止编译器将未知部分“优化”掉。 - greybeard
你的评论非常有用，谢谢。因此，当使用一个被检测函数的结果时，如果不是为了了解它，要注意编译器可能会优化掉未知部分，可以查看反汇编代码。 - P_P
0

Python程序用于检查一个数字是否是3的幂。

    def power(Num1):
        while Num1 % 3 == 0:
            Num1 /= 3
        return Num1 == 1


    Num1 = int(input("Enter a Number: "))
    print(power(Num1))
这个答案对starblue 2009年的回答有什么补充？ - greybeard
0

基于集合的解决方案...

DECLARE @LastExponent smallint, @SearchCase decimal(38,0)

SELECT
    @LastExponent = 79, -- 38 for bigint
    @SearchCase = 729

;WITH CTE AS
(
    SELECT
        POWER(CAST(3 AS decimal(38,0)), ROW_NUMBER() OVER (ORDER BY c1.object_id)) AS Result,
        ROW_NUMBER() OVER (ORDER BY c1.object_id) AS Exponent
    FROM
        sys.columns c1, sys.columns c2
)
SELECT
    Result, Exponent
FROM
    CTE
WHERE
    Exponent <= @LastExponent
    AND
    Result = @SearchCase

使用SET STATISTICS TIME ON可以记录最低的时间，为1毫秒。

需要第二个表'sys.columns c2'吗？你选择使用sys.columns是出于速度原因吗？ - Nitai Bezerra
我使用了交叉连接来确保我获得足够的行数，并且使用sys.columns，因为我知道它至少有40-50行。而且这是我想到的第一个方法 :-) - gbn
0
另一种方法是在编译时生成一个表格。好处是，您可以将其扩展到4、5、6、7等幂次方。
template<std::size_t... Is>
struct seq
{  };

template<std::size_t N, std::size_t... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...>
{  };

template<std::size_t... Is>
struct gen_seq<0, Is...> : seq<Is...>
{  };

template<std::size_t N>
struct PowersOfThreeTable
{
    std::size_t indexes[N];
    std::size_t values[N];

    static constexpr std::size_t size = N;
};

template<typename LambdaType, std::size_t... Is>
constexpr PowersOfThreeTable<sizeof...(Is)>
    generatePowersOfThreeTable(seq<Is...>, LambdaType evalFunc)
{
    return { {Is...}, {evalFunc(Is)...} };
}

template<std::size_t N, typename LambdaType>
constexpr PowersOfThreeTable<N> generatePowersOfThreeTable(LambdaType evalFunc)
{
    return generatePowersOfThreeTable(gen_seq<N>(), evalFunc);
}

template<std::size_t Base, std::size_t Exp>
struct Pow
{
    static constexpr std::size_t val = Base * Pow<Base, Exp-1ULL>::val;
};

template<std::size_t Base>
struct Pow<Base, 0ULL>
{
    static constexpr std::size_t val = 1ULL;
};

template<std::size_t Base>
struct Pow<Base, 1ULL>
{
    static constexpr std::size_t val = Base;
};

constexpr std::size_t tableFiller(std::size_t val)
{ 
    return Pow<3ULL, val>::val;
}

bool isPowerOfThree(std::size_t N)
{
    static constexpr unsigned tableSize = 41; //choosen by fair dice roll

    static constexpr PowersOfThreeTable<tableSize> table = 
            generatePowersOfThreeTable<tableSize>(tableFiller);

    for(auto a : table.values)
        if(a == N)
            return true;
    return false;
}
其他几个答案也提到了预计算值。你回答的部分...我完全听不懂。再说一遍，我不是C++专家。 - Teepeemm
这将在编译时生成值。 - NaCl
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接