整数的pow函数

Question

整数的pow函数

6

我需要一个针对整数的版本pow。我有两个问题需要用pow解决：

如果结果大于我的整数类型，我需要将其夹紧到numeric_limits :: max（）
我需要能够处理41.99999四舍五入为42，而不是四舍五入为41

C ++是否提供了某种内联解决方案，还是我必须编写自己的函数：

template <typename T>
enable_if_t<is_integral_v<T>, T> mypow(const T base, unsigned int exp) {
    T result = exp == 0U ? base : 1;

    while(exp-- > 1U) {
        if(numeric_limits<T>::max() / result <= base) return numeric_limits<T>::max();
        result *= base;
    }
    return result;
}

- Jonathan Mee

你不能使用std::pow函数并在必要时截断结果吗？ - NathanOliver

@NathanOliver 是的...如果有一种方法可以保证不会违反1和2，那么有没有办法实现呢？ - Jonathan Mee

你可以使用尾递归和一些数值技巧来提高运行时性能。此外，您可以将此方法设置为constexpr。https://stackoverflow.com/questions/9348933/using-recursion-to-raise-a-base-to-its-exponent-c - Andrew

2个回答

2

你的代码没有编译成功，如果可能的话，请先检查你的代码是否能够编译成功，在使用编译器或者在编译器探索器上进行检查。

另外，你忘记了考虑负值。这是整数幂的一个非常重要的特征。下面的代码适用于普通int类型。我会让你自己探索如何将其扩展到其他整数类型。

#include <type_traits>
#include <iostream>
#include <cmath>
#include <limits>

using namespace std;

template <typename T>
enable_if_t< is_integral<T>::value, T> 
mypow(T base, unsigned int exp) 
{
    T result = T(1);
    bool sign = (base < 0);

    if (sign) base = -base;

    T temp = result;
    while(exp-- != 0) 
    {
        temp *= base;
        if (temp < result)
        {
            return (sign) ? numeric_limits<T>::min() 
                          : numeric_limits<T>::max();
        }
        result = temp;
    }
    return (sign && (exp & 1)) ? -result : result;
}

template <typename T>
enable_if_t< !is_integral<T>::value, int> 
mypow(const T& base, unsigned int exp) 
{
    T result = T(1);
    int i_base = int(floor(base + .5));
    bool sign = (i_base < 0);

    if (sign) i_base = -i_base;

    int temp = result;
    while(exp-- != 0) 
    {
        temp *= i_base;
        if (temp < result)
        {
            return (sign) ? numeric_limits<int>::min() : numeric_limits<int>::max();
        }
        result = temp;
    }
    return (sign && (exp & 1)) ? -result : result;
}

在现实生活中，即使是在积分的情况下，我会注意使用 floor 函数。

  template<typename T>
   enable_if_t< is_integral<T>::value, T> 
   mypow(T x, unsigned int y) { return T(floor(pow(x, y) + .5)); }

   template<typename T>
   enable_if_t< !is_integral<T>::value, int> 
   mypow(T x, unsigned int y) { return int(floor(pow(floor(x + .5), y) + .5)); }

- Michaël Roy

我只是想举个例子，但是是的，这是我不想编写自己的函数的另一个原因 :( - Jonathan Mee

在支持浮点运算的 CPU 上，使用浮点 pow 通常会更快。一些现代 CPU 具有浮点 pow 指令。 - Michaël Roy

1

@JonathanMee：也许你应该查看一下这个有趣的主题讨论：https://dev59.com/hnVD5IYBdhLWcg3wE3No - Michaël Roy

如果 x 是整数，那么为什么你要使用 floor(x+.5) 而不是 double(x) 呢？你担心64位整数不能表示为 double 吗？它们无论如何都会损坏你的代码。 - Walter

@Walter 抱歉，第二个函数中有一个打字错误，它是用于浮点数的。我将四舍五入该值，因为这是原始问题的一部分。感谢您指出这一点。 - Michaël Roy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- eerorika · Accepted Answer

C++有提供类似内联函数的解决方案吗？

不，标准库中没有整数的pow函数。

那我是不是必须要自己写一个函数呢？

是的，你需要自己编写一个函数。请注意，你展示的乘法循环可能比使用std::pow实现该函数更慢，尤其是因为循环中还有分支和除法：

template<class I>
I int_pow_no_overflow(I base, I exp)
{
    double max = std::numeric_limits<I>::max();
    double result = std::round(std::pow(base, exp));
    return result >= max
        ? max
        : result;
}

为了更通用的方法，您可能还需要考虑下溢。

除了您展示的线性方法之外，还有其他更快的整数幂算法（例如见平方乘法），但我不确定除非您处理任意精度算术或没有浮点单位的嵌入式系统，否则是否值得考虑它们。