-1 > 0x7fffffff ???

---

今天在研究KMP算法的时候，KMP算法研究的一窍不通，完全看不懂这个神仙算法的思路。那想着先照葫芦画瓢，先不管三七二十一，知道KMP要干啥，至于为啥要那样做咋先不管，咋先把这个算法写一遍，然后再去理解，但是这个就出问题了，出了一个莫名其妙的bug，这是怎么找都找不到啊，找的我头大啊！！！

我先确定了出问题的函数，这个很简单。

然后我又确定了出问题的部分是什么，这不确定不得了，发现是while循环出错了，while循环只是循环了一次就退出了。。。

代码如下：

int KMPsearch(string str, string sub, int* next) {
    int i = 0, j = 0;
    while (i < str.length() && j < sub.length()) {
        if (j == -1 || str[i] == sub[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == subLen) {
        return i - j;
    } else {
        return -1;
    }
}

这个代码看着是十分的没有问题，但是我就是定位到这个函数有问题了而且是while循环一次就退出while循环一次之后i是1，j是-1，str.length()和sub.length()肯定是一直都不会变的啊？那么究竟是1>=26还是-1>=6?

这搞得我非常的懵逼。。。我的编译器出问题了，开始跟我瞎搞了？

    // 原因是这样子的 str.length()返回类型是size_t是无符号类型的
    // j 是int是有符号类型的，一般情况下还真的没问题，但是问题就在与这里的j可以为-1
    // 有符号值与无符号的值进行比较的时候，有符号值会转换成无符号的值
    // -1 是 0xffffffff 变成有符号的数还是 0xffffffff 可怕。。。这个比0x7fffffff(MAX_INT)还大！！

数据在电脑中的存储和计算都是以补码的形式.

-1的原码是 1000 0000 0000 0000 0000 0000 0000 0001
-1的反码是 1111 1111 1111 1111 1111 1111 1111 1110
-1的补码是 1111 1111 1111 1111 1111 1111 1111 1111

反码是除了符号位其余的位取反

正整数的补码是就是原码

负整数的补码是反码加1

size_t i = 0x7fffffff;
int j = -1;
if (j > i){
    cout << "-1 > 0x7fffffff"<<endl;
}

当一个有符号数和无符号数进行比较的时候，就不会把-1这个符号位1当成符号位.

也就是说-1 == (unsigned int)0xffffffff > (unsigned int)0x7fffffff

0x7fffffff是啥玩意？是MAX_INT（定义在limits.h中)

0x80000000是MIN_INT，咦这个不是-0的原码嘛？

0x80000000 -1 = 0x7fffffff 取反就是 0x00000000，这不是0嘛？蛤蛤蛤这也就是为嘛最大的负数的绝对值要比最大的正数大上1.

-0的原码是0x80000000 反码是0xfffffff

补码是0x00000000，咦为啥呢？

因为溢出了1 0000 0000，这个只是取后八位，所以说-0和0的补码都是0。

#include <stdio.h>
#include <limits.h>

int main(){
    if (INT_MIN == 0x80000000 && INT_MAX == 0x7fffffff){
        printf("INT_MIN: 0x80000000\nINT_MAX: 0x7fffffff\n");
    }else{
        printf("No");
    }
    return 0;
}

有符号的数和无符号的数时要注意：有符号的数会变成无符号的数。

这不禁又让我想起来我之前遇到的一个大体相同bug

for (size_t i = 10; i>=value; i--){
    // ... 
}

这个value是-1，导致这个循环死的了，当时找bug找的我也是头发昏，找到了的原因也是如此

无符号与有符号的数进行比较！！！

有符号的数会变成无符号的数！

有符号的数会变成无符号的数！

有符号的数会变成无符号的数！

我被坑的已经不止这一次了，嘤嘤嘤~，继续看KMP算法去了。