欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

c++的整数表达讲解

程序员文章站 2022-06-26 10:25:18
由于老是记不太住short,int,long,long long所表示的数的范围,所以在这里记录一下。 int的表示与编译器有关,一般的编译器用四个字节来表示。4个字节有32位,...

由于老是记不太住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