1. 起因
在实现kmp算法时,出现了诡异的现象,看下面的代码:
int KMP (const char *s, const char *t)
{
int lenS = strlen (s);
int lenT = strlen (t);
int next[lenT];
get_next (next, t);
int i = 0;
int j = 0;
while (i < lenS && j < lenT) {
if (j == -1 || s[i] == t[j]) {
++i;
++j;
} else {
j = next[j];
}
}
if (j == strlen (t))
return i - j;
else
return -1;
}
代码过程不重要。
乍一看lenS
和strlen(s)
是等价的,可是如果将lenS
都替换成strlen(s)
,lenT
都替换成strlen(t)
,就会得到非预期结果,??? 一脸问号
2. 发现问题
注意到strlen()
返回的类型是size_t
,有了一丝怀疑。
于是,改掉其中两行:
int lenS = strlen (s);
int lenT = strlen (t);
// 换成下面的
size_t lenS = strlen(s);
size_t lenT = strlen(t)
结果,代码果然不能正常工作了,拿gdb单步追踪,发现了问题所在:索引变量j
的值可能为-1,此时 j
为有符号负数,而size_t
是无符号的,于是 -1 < strlen(t)
这个条件就为false
。
3. 验证
换个更直观的demo:
#include <stdio.h>
int main (void)
{
int a = -1;
size_t b = 100;
if (a < b) {
puts ("a < b");
} else {
puts ("a > b");
}
}
输出结果为a > b
,与预期截然相反,总以为编译器会聪明地处理好这种情况,然而并没有。
从概率上来讲,这个错误是很容易犯的,而且不是很好查。然而居然头一次遇到,多少有些后怕。
看下这个demo的汇编代码:
可以看到,第 20行将-1赋值给%-4(rbp)
(a),将100赋值给-16(%rbp)
(b),也就是我们定义的两个整型变量。文章来源:https://www.toymoban.com/news/detail-605573.html
将a存入%eax
,然后用ctlq
(cdeq)指令将它符号位扩展至%rax
(0xFFFFFFFFFFFFFFFF),最后用无符号比较指令jnb
来进行条件判断。文章来源地址https://www.toymoban.com/news/detail-605573.html
到了这里,关于无符号数和有符号数的“bug”的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!