By

1、使用位运算乘法。

把一个乘数变为2进制后，使用位运算完成乘数的乘法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 
 * 输入：正整数k 和 正整数m 
 * 输出：k*m 
 */   
__int64 km(__int64 k, __int64 m){  
   __int64 x = k;  
   int w = (int)floor(log(m) / log(2)) -1;  
   __int64 e = 1 << w;  
   for(int i=0; i<=w; i++){  
       x <<= 1;  
       if(m & e)  
            x += k;  
       e >>= 1;  
   }  
   return x;  
}

2、使用位运算的乘方运算

指数变为2进制后，使用位运算完成乘方运算。

伪代码：

algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 
 * 输入：正整数v mod m 和 g mod m  
 * 输出：g^v mod m  
 */  
__int64 gvmm(__int64 g, __int64 v, __int64 m){  
    int w = (int)floor(log(v) / log(2)) - 1;  
    __int64 e = 1 << w;  
    __int64 x = g;  
    for(int i=0; i<=w; i++){  
        x = (x * x) % m;  
        if(v & e){  
             x = (g * x) % m;  
        }  
        e >>= 1;  
    }  
    return x;  
}

乘方的测试：
使用普通算法和位运算算法比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>  
#include <math.h>  
#include <time.h>    
using namespace std;  
  
/* 
 * 输入：正整数v mod m 和 g mod m  
 * 输出：g^v mod m  
 */  
__int64 gvmm(__int64 g, __int64 v, __int64 m){  
    int w = (int)floor(log(v) / log(2)) - 1;  
    __int64 e = 1 << w;  
    __int64 x = g;  
    for(int i=0; i<=w; i++){  
        x = (x * x) % m;  
        if(v & e){  
             x = (g * x) % m;  
        }  
        e >>= 1;  
    }  
    return x;  
}  
/* 
 * 验证结果的普通算法  
 */  
int verify(__int64 g, __int64 v, __int64 m){  
    __int64 x = 1;  
    for(int i=0; i<v; i++){  
        x *= g;  
        x %= m;  
    }  
    return x;  
}  
  
int main(){  
    clock_t begin = clock();  
    cout << verify(23229,1892123, 23894)  << endl;  
    clock_t end = clock();    
    double cost = (double)(end - begin) / CLOCKS_PER_SEC;    
    printf("ordinary : %lf seconds\n", cost);    
    begin = clock();    
    cout << gvmm(23229,1892123, 23894) << endl;  
    end = clock();    
    cost = (double)(end - begin) / CLOCKS_PER_SEC;    
    printf("bit calculation: %lf seconds\n", cost);       
    system("pause");  
}

按照程序中给出的稍复杂的乘方运算，其效率分别为（多次测量后都差不多这个数量级）
21963
ordinary : 0.071000 seconds
21963
bit calculation: 0.001000 seconds
差不多普通算法比位运算算法慢了50-70倍。