首页 > 其他 > 详细

快速求幂运算笔记

时间:2014-06-09 22:27:56      阅读:670      评论:0      收藏:0      [点我收藏+]

如何快速求x得n次方呢?

首先C++里面有个pow如何实现呢?自己查查,里面使用double,肯定更麻烦,还有jianzhi

我们会顺手写下

int res=1;

for(int i=1;i<=n;i++)

{

res*=x;

}

学习一下快速幂,logn内计算出来,使用N的二进制,只需要logN就可以计算。

正要的就是计算每个为1对应的基数。列入: 11是多少?是二进制的话,就是1*2^1+1

那么x^(11)呢,两个1对应的基数是多少呢?低位1对应的是X,高位1对应的是X^2,因此,就是位于第一位基数为x,第二位基数为X^2,第三位是X^4,X^8 ,从中我们看出前一位的基数的平方是后一位的基数。

因此对于 11011 就是对于0位,就是1,对于1为……

 

bubuko.com,布布扣
#include<iostream>
using namespace std;
int pow1(int x,int n)
{
    int res=1;
    for(int i=1;i<=n;i++)
    {
        res*=x;
    }

    return res;

}
int pow2(int x,int n)
{
    int base=x;
    int res=1;
    while(n)
    {
        if(n&1) res*=base;
        base=base*base;//每一位的基数的增长。

        n=n>>1;
    
    
    }

    return res;

}
//顺便写一个

int main()
{
    int x, n;
    cin>>x>>n;
    while(x)
    {
    cout<<pow1(x,n)<<endl;
    cout<<pow2(x,n)<<endl;
    cout<<pow(x,n)<<endl;
    cin>>x>>n;
    
    }



}
bubuko.com,布布扣

快速求幂运算笔记,布布扣,bubuko.com

快速求幂运算笔记

原文:http://www.cnblogs.com/hansongjiang/p/3775183.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!