c++的整数表达讲解

由于老是记不太住short,int,long,long long所表示的数的范围，所以在这里记录一下。

int的表示与编译器有关，一般的编译器用四个字节来表示。4个字节有32位，其中第一位用来表示“正负”，其余31位用来表示数值，那么int范围是（-2^31，2^31-1）【为什么负数能多表示一个，简单来说是和原码，反码，补码有关系，人为规定补码中 1000 0000 表示 -128】。

其他类型的表示范围如下：

short : 2字节（-2^15~2^15-1）也就是（-32768~32767），即（SHRT_MIN~SHRT_MAZ）（包含在头文件中）；

int : 4字节 （-2^31,2^31-1）也就是（-2147483648，2147483648），即（INT_MIN~INT_MAZ）；

long : 4字节 （-2^31,2^31-1）也就是（-2147483648，2147483648），即（LONG_MIN~LONG_MAZ）；

long long : 8字节 （-2^63,2^63-1）也就是（-9223372036854775807，9223372036854775807），即（LLONG_MIN~LLONG_MAZ）；

做到leetcode的【204. Count Primes】题（计算小于整数n的素数的个数）的时候，看到一个算法叫厄拉多塞筛法。大致意思如下：先把2到n-1个数标记为false，然后开始遍历，当遍历到i的时候，把后面的i的倍数的数标记为true。当遍历到j的时候，如果它没有被标记为true，那么它就是一个素数。

我看leetcode的Discuss里面点赞最多的解法如下：

int countPrimes(int n) {
    if (n<=2) return 0;
    vector<bool> passed(n, false);
    int sum = 1;
    int upper = sqrt(n);
    for (int i=3; i<n; i+=2) {
        if (!passed[i]) {
            sum++;
            //avoid overflow
            if (i>upper) continue;
            for (int j=i*i; j<n; j+=i) {
                passed[j] = true;
            }
        }
    }
    return sum;
}

然而我觉得这个upper的设置没有必要【好吧当时，没有看懂它的注释“//avoid overflow”指的是什么】。因为我觉得j=i*i,如果太大的话，会直接大于n，不执行循环，和它的continue的功能是一样的，然而，我删掉upper这两句之后，当输入是“499979”报错了。于是自己在本地建工程调试，发现会有非法访问数组的问题。后来发现是int表示范围不够的问题，sqrt(INT_MAX)的大小是46341，当i>46341的时候，int会表示不了这个好大的整数，然后就会溢出成一个负数，所以还是会小于n，会进入循环，所以访问passed[j]，就会出错。解决方法有两个：

1. 像上面一样用一个upper来判断，这样可以用整型就可以做到；

2. 用long long类型来表示j以及i*i, 也就是循环写成for (long long j=（long long）i*i; j