[C++知识库]《剑指2》第一章 整数

一、整数的知识：

1.问题：负数转化为正数的一个问题：对于32位的整数而言，最小的负数是2^31，而最大的正数为2^31-1;因此这种情况的转化会导致溢出。

2.int型整数除法有一种情况会导致溢出，即(-2^31)/(-1);也就是第一条的情况。

二、题目：

1.整数除法：

①个人思路：基于减法实现除法

1.b作用于a，使a即将变号的次数

2.分四类讨论

分析：时间复杂度为O(n)，不会出现溢出的情况

改进空间：分了四类，代码存在冗余，可以统一将除数与被除数变为某一符号，最后对结果根据原符号进行修改；这样子就要考虑溢出问题了，由于负数转正数存在溢出，因此统一将除数与被除数转换为负号。

//C实现
int divide(int a, int b){
    int ret = 0;
    // a为正数
    if(a>=0 && b>0)
    {
        while(a-b >= 0)
        {
            ret++;
            a-=b;
        }
    }
    else if(a>=0 && b<0)
    {
        while(a+b >= 0)
        {
            ret--;
            a+=b;
        }
    }
    //a为负数 
    else if(a<0 && b>0)
    {
        while(a+b <= 0)
        {
            ret--;
            a+=b;
        }
    }
    else if(a<0 && b<0)
    {
        while(a-b <= 0)
        {
            ret++;
            a-=b;
        }
    }
    return ret;
}

②时间复杂度更低的做法：从除数下手

思路：除数翻倍计算

注意：while(divisor>0xc0000000?&&?a?<=?divisor+divisor) 中除数应该大于0x8000000的一半，否则count翻倍会溢出

int divide(int a, int b){
    //最小负数除以-1时会有溢出
    if(a == 0x80000000 && b==-1)
        return 0x7fffffff;
    int flag = 2;
    if(a>0)
    {
        flag--;
        a = -a;
    }
    if(b>0)
    {
        flag--;
        b = -b;
    }
    unsigned int ret = 0;
    while(a<=b)
    {
        int count = 1;
        int divisor = b;
        while(divisor>0xc0000000 && a <= divisor+divisor)
        {
            divisor += divisor;
            count += count;
        }
        ret += count;
        a -= divisor;
    }
    return flag == 1?-ret:ret;
}