春暖花开

记一次意外的移位错误

移位错误

前天晚上,刷51Nod上面的一个题:通过矩阵快速幂计算斐波那契数列,结果发生了一个意想不到的错误,这件事也告诉了我一个道理:

当代码出错的时候,不要轻易去怀疑工具的问题,而要去想 99% 的可能性是自己的代码有问题.

下面是最开始的代码:

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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll MAXV = 1e9 + 9;
ll base[2][2] = {{1, 1}, {1, 0}};
ll Reult[2][2] = {{1,0}, {0,1}};
void multi(ll A[][2], ll B[][2]){
ll tmp[2][2] = {{0, 0}, {0, 0}};
for(int i = 0; i != 2; ++i){
for(int j = 0; j != 2; ++j){
for(int k = 0; k != 2; ++k){
tmp[i][j] += (A[i][k] * B[k][j]) % MAXV;
tmp[i][j] %= MAXV;
}
}
}
for(int i = 0; i != 2; ++i){
for(int j = 0; j != 2; ++j){
A[i][j] = tmp[i][j];
}
}
}
void QuickPow(int N){
while (N){
if (N&1){
multi(Reult, base);
}
multi(base, base);
N >>= 1;
}
}
int main(){
ll n;
cin >> n;
QuickPow(n-1);
cout << Reult[0][0] <<endl;
return 0;
}

提交之后,有一部分 test cases 发生错误,而且居然还出现超时.之后查看了一下题目,发现是因为函数 QuickPow 的参数是 int 型,而需要计算的数列的项最大是 10^18,因此,导致发生了溢出,之后,将参数由 int 改为 long long 就好了:

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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll MAXV = 1e9 + 9;
ll base[2][2] = {{1, 1}, {1, 0}};
ll Reult[2][2] = {{1,0}, {0,1}};
void multi(ll A[][2], ll B[][2]){
ll tmp[2][2] = {{0, 0}, {0, 0}};
for(int i = 0; i != 2; ++i){
for(int j = 0; j != 2; ++j){
for(int k = 0; k != 2; ++k){
tmp[i][j] += (A[i][k] * B[k][j]) % MAXV;
tmp[i][j] %= MAXV;
}
}
}
for(int i = 0; i != 2; ++i){
for(int j = 0; j != 2; ++j){
A[i][j] = tmp[i][j];
}
}
}
void QuickPow(ll N){
while (N){
if (N&1){
multi(Reult, base);
}
multi(base, base);
N >>= 1;
}
}
int main(){
ll n;
cin >> n;
QuickPow(n-1);
cout << Reult[0][0] <<endl;
return 0;
}

当输入的数过大时,前一个程序由于发生溢出导致计算结果不对我能理解,但是有时候会卡我就无法理解了,讲道理不应该啊,由于两个程序除了一个参数类型之外其他地方完全相同,所以我也就没有怀疑是程序的逻辑出了问题,反而去怀疑是编译器的问题.对目标程序进行反汇编,也没发现什么不对劲的地方,唯一的区别就是前者用的是一个 32 位寄存器传参,后者用的是一个 64 位寄存器传参.

昨天,我去向编译原理老师请教,还在想自己会不会发现了一个天大的编译器错误.当老师给我指出错误的时候,突然觉得无比尴尬,自己宛如一个智障.

错误原因如下:

在C/C++中,无符号数移位是逻辑移位,而有符号数移位是算术移位.我在函数中使用了移位运算,因此,当溢出变为负数之后,我们知道,计算机中数的表示都是补码,负数的符号位是 1 ,因此,算术移位右移时高位补符号位就是补 1,所以导致 N 永远不会变为 0,while 循环永远不会结束,程序自然就卡住了.

看下面一个例子:

从上面例子可以看出,有符号移位是算术移位,右移时高位补符号位.

逻辑移位与算术移位

顺便复习一下逻辑移位和算术移位:

逻辑移位

无论左移还是右移,都是补 0.

算术移位

左移:低位补 0
右移:高位补符号位

0%