设为首页 加入收藏

TOP

c++的整数表达讲解
2017-12-31 06:06:56 】 浏览:42
Tags:整数 表达 讲解

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


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇数据结构:hash map表 下一篇2 Keys Keyboard“编程题”

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目