首页 > 其他 > 详细

位处理的低级筛法

时间:2015-03-18 13:55:30      阅读:286      评论:0      收藏:0      [点我收藏+]

不得不说位操作是件很神奇的东西

//低级筛法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
using namespace std;
int _count(unsigned int a){
    int sum=0;
    for(unsigned int x=a;x;x>>=1)
        if(x&1) sum++;
    return sum;
}
void sieve(unsigned int* p){
    for(int i=2;i<=10000;++i)
        if(p[i/32]&(1<<i%32))//i/32位第i/32个整数;i%32为第i/32个整数的第i%32位
            for(int j=i*i;j<100000000;j+=i)
                p[j/32]&=~(1<<j%32);
}
int main()
{
    clock_t start=clock();
    unsigned int *p=(unsigned int*)malloc(12500000);
    /*一亿个数只要用12500000个字节表示,每个字节8位.按一个整数32位计算,
    只要12500000/4个整数型就可以表示
    */
    if(!p){
        cout<<"no enough memory."<<endl;
        return 1;
    }
    memset(p,255,12500000);
    sieve(p);
    int sum=-2;
    for(int i=0;i<12500000/4;++i)
        sum+=_count(p[i]);
    free(p);
    printf("%d,%7.3f\n",sum,(clock()-start)/CLK_TCK);
    return 0;
}

 

位处理的低级筛法

原文:http://www.cnblogs.com/vactor/p/4346905.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!