C ++中整数的幂
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1505675/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
power of an integer in c++
提问by skazhy
I need to get the result from pow(a,b)as an integer (both a and b are integers too). currently the calculations where (int) pow( (double)a, (double)b)is included are wrong. Maybe someone can help with a function that does the pow(a,b) with integers and returns an integer too?
我需要从pow(a,b)整数中获取结果（a 和 b 也是整数）。目前(int) pow( (double)a, (double)b)包含的计算是错误的。也许有人可以帮助使用整数执行 pow(a,b) 并返回整数的函数？
But here is the odd part: I made my script in Linux with Geany (and g++/gcc compiler) and had just pow(a,b)the script compiled and worked fine. But in university I have Dev-C++ (and MS Windows). In Dev-C++ the script didn't compile with an error [Warning] converting toint' from double'
但这是奇怪的部分：我在 Linux 中使用 Geany（和 g++/gcc 编译器）制作了我的脚本，并且只pow(a,b)编译了脚本并且运行良好。但是在大学里我有 Dev-C++（和 MS Windows）。在 Dev-C++ 中，脚本没有编译，错误[Warning] converting toint' 来自double'
I need to make this scrpit work under Windows (and Mingw compiler) too.
我也需要让这个 scrpit 在 Windows（和 Mingw 编译器）下工作。
采纳答案by Zed
A nice recursive approach you can show off:
你可以炫耀的一个很好的递归方法：
int myPow(int x, int p) {
if (p == 0) return 1;
if (p == 1) return x;
return x * myPow(x, p-1);
}
回答by Matthieu M.
A better recursive approach than Zed's.
比 Zed 更好的递归方法。
int myPow(int x, int p)
{
if (p == 0) return 1;
if (p == 1) return x;
int tmp = myPow(x, p/2);
if (p%2 == 0) return tmp * tmp;
else return x * tmp * tmp;
}
Much better complexity there O(log2(p)) instead of O(p).
更好的复杂度是 O(log2(p)) 而不是 O(p)。
回答by fmuecke
Or you could use a litte bit of template metaprogramming :)
或者你可以使用一点模板元编程:)
template<int X, int P>
struct Pow
{
enum { result = X*Pow<X,P-1>::result };
};
template<int X>
struct Pow<X,0>
{
enum { result = 1 };
};
template<int X>
struct Pow<X,1>
{
enum { result = X };
};
int main()
{
std::cout << "pow(3,7) is " << Pow<3,7>::result << std::endl;
return 0;
}
This code has the best complexity, O(1), because the evaluation will happen at compile time. Of course this will only work with integer values. However, this function is is only provided for completeness (and fun).
这段代码的复杂度最高，为O(1)，因为评估将在编译时发生。当然，这只适用于整数值。但是，提供此功能只是为了完整性（和乐趣）。
回答by Steve314
Mostly in reply to Zeds simple recursion...
主要是为了回复 Zeds 简单的递归......
Why is recursion assumed better than iteration? Especially in C++. What's wrong with...
为什么假设递归比迭代更好？尤其是在 C++ 中。怎么了...
int myPow (int x, int p) {
int i = 1;
for (int j = 1; j <= p; j++) i *= x;
return i;
}
I'm not saying your answer is wrong or in any way worse - it's just that I got the impression you think it's good becauseit's recursive. IMO, in C++ particularly, that bias can lead to slow and even broken programs. Slow programs because you're growing a huge stack, causing cache and virtual memory paging. Broken programs because you get a stack overflow where an iterative solution would work.
我并不是说你的答案是错误的或者更糟——只是我觉得你认为它很好，因为它是递归的。IMO，尤其是在 C++ 中，这种偏见会导致程序缓慢甚至损坏。程序变慢，因为你正在增长一个巨大的堆栈，导致缓存和虚拟内存分页。程序损坏，因为您会遇到堆栈溢出，而迭代解决方案将在其中起作用。
Some would look at your answer and think it's tail recursive and would be optimised into iteration anyway. Of course that's not true - after each recursive call exits, there is a multiply still to do, so it is not tail recursive. The thing is, in C++, there are a lot of more subtle things that prevent tail recursion optimisations - even if the compiler does them at all. For example...
有些人会看你的答案，认为它是尾递归的，无论如何都会被优化为迭代。当然这不是真的——在每次递归调用退出后，还有一个乘法要做，所以它不是尾递归。问题是，在 C++ 中，有很多更微妙的事情会阻止尾递归优化——即使编译器根本没有这样做。例如...
void myrecurse (plan *p)
{
plan i;
i.prev = p;
// more plan setup, checks, and special case handling
myrecurse (&i);
}
In this case, all the "plan" instances must remain on the stack. Therefore, stack frames cannot be discarded. Therefore this is not optimizable into iteration, even though there are precisely zero operations done after the recursive call. Not even hidden operations like destructor cleanups, since plan is assumed to be a POD struct.
在这种情况下，所有“计划”实例必须保留在堆栈中。因此，堆栈帧不能被丢弃。因此，即使在递归调用之后精确地执行了零操作，这也不能优化到迭代中。甚至没有像析构函数清理这样的隐藏操作，因为计划被假定为一个 POD 结构。
Incidentally, this is based on something I've done in real code - a data structure operation that is planned during the recursion, but nothing is changed in the original nodes until the recursion reaches the root/leaf, all new nodes needed have been successfully allocated, all locks acquired, and there's no curruption to make worse. At that point, an iteration is done through that linked list of plan instances to commit the changes - the logic was clearer as an iteration than being broken up into fragments relating to the unwinding of the recursive calls.
顺便说一句，这是基于我在实际代码中所做的一些事情 - 在递归期间计划的数据结构操作，但是在递归到达根/叶之前，原始节点中没有任何更改，所有需要的新节点都已成功已分配，已获取所有锁，并且不会有更糟的中断。在这一点上，通过计划实例的链接列表完成迭代以提交更改 - 作为迭代的逻辑比被分解为与递归调用的展开相关的片段更清晰。
The point here obviously isn't to claim that recursion is automatically bad. It just makes me nervous when people seem to assume recursion is better than iteration by default.
这里的重点显然不是声称递归自然是坏的。当人们似乎认为默认情况下递归比迭代更好时，这让我感到紧张。
回答by Ian Burris
Wouldn't a tail-recursive function be best? Something like:
尾递归函数不是最好的吗？就像是：
int myPow_helper(int x, int p, int result) {
if (p == 0) {
return result;
} else {
return myPow_helper(x, p-1, result*x);
}
}
int myPow(int x, int p) {
return myPow_helper(x, p, 1);
}
回答by John Millikin
I assume your homework assignment is to write an integral exponent function. First, take a look at what an exponent is:
我假设你的家庭作业是写一个积分指数函数。首先，看看什么是指数：
http://en.wikipedia.org/wiki/Exponent
http://en.wikipedia.org/wiki/Exponent
Then, look in your textbook for how to multiply numbers in C. You'll want to use a forloop.
然后，查看您的教科书，了解如何在 C 中将数字相乘。您将需要使用for循环。
回答by jdh8
Binary powering, aka exponentiation by squaring.
int powi (int base, unsigned int exp)
{
int res = 1;
while (exp) {
if (exp & 1)
res *= base;
exp >>= 1;
base *= base;
}
return res;
}
Note that this returns 1 for powi(0,0).
请注意，这会为 powi(0,0) 返回 1。
回答by Calyth
Instead of casting the double to an int in the (int) pow((double)a, (double)b)line, try rounding the results of pow, and then cast to int if necessary.
不要(int) pow((double)a, (double)b)在行中将 double 转换为 int，而是尝试对 pow 的结果进行四舍五入，然后在必要时转换为 int。
It's probably one of those floating point problem when you truncate, especially if your result's off by one.
截断时，这可能是浮点问题之一，尤其是当结果相差 1 时。
回答by jfs
C++ standard doesn't have int pow(int, int)(It has double pow(double, int), float ...). Microsoft's cmath uses C math.h that has not ipow. Some cmath headers define template version of pow.
C++ 标准没有int pow(int, int)（它有double pow(double, int), float ...）。微软的 cmath 使用没有 ipow 的 C math.h。一些 cmath 头文件定义了pow.
$ cat main.cpp
#include <cmath>
int main() {
std::pow(2,2);
}
$ gcc main.cpp # this cmath has template pow
...snip... std::pow<int, int>(int, int)]+0x16): undefined reference to `pow'
collect2: ld returned 1 exit status
1 ;( user@host:
$ gcc main.cpp -lm
Search for function:ipow lang:c++on Google Code .
在 Google Code 上搜索function:ipow lang:c++。
Here's example from the first link:
这是第一个链接中的示例：
template <typename Type1, typename Type2>
Type1 ipow(Type1 a, Type2 ex)
// Return a**ex
{
if ( 0==ex ) return 1;
else
{
Type1 z = a;
Type1 y = 1;
while ( 1 )
{
if ( ex & 1 ) y *= z;
ex /= 2;
if ( 0==ex ) break;
z *= z;
}
return y;
}
}
See calculating integer powers (squares, cubes, etc.) in C++ code.
回答by Judegar
Why linearly? Try it logarithmic!!
为什么是线性的？试试对数！！
long long powx( int val, int exp )
{
long long actual = val;
long long prod = 1;
int i;
for ( i = 0; i < 32; i++ )
{
if ( exp & 0x1 )
{
prod *= actual;
}
exp >>= 1;
actual *= actual;
}
return prod;
}
回答by Mamuka
There are two alternatives here, when we want to count power(a,n) we may write code which is very short and works in O(logn) time, but is recursively and therefore requires creating new stackframe for each call and needs a bit more time than loop iteration. So short code is:
这里有两种选择，当我们想要计算 power(a,n) 时，我们可能会编写很短的代码并且在 O(logn) 时间内工作，但是它是递归的，因此需要为每个调用创建新的堆栈帧并且需要一点比循环迭代更多的时间。所以简短的代码是：
int power(int a, int n){
if(n == 0) return 1;
int keep = power(a,n/2);
if(n & 1) return keep*keep*a; // (n & 1) is and operation of 1 and the
return keep*keep; // last bit of n
}
and as for the faster code, here it is using while loop:
至于更快的代码，这里使用的是 while 循环：
int power(int a, int n) {
int res = 1;
while (n) {
if (n & 1)
res *= a;
a *= a;
n >>= 1;
}
return res;
}
