为什么是一亿

1 从编译器&操作系统考虑
在ubuntu12.04 + g++4.6.3的实验中，32位的操作系统只能开出1<<28的数组，在64位操作系统中这一数值是1<<30；
如果采用STL中的bitset，那么32位操作系统中最大能开出1<<31,在64位操作系统中开出1<<34（如果再大ld会报错）；
以上的数组都是在程序的global scope中开出，空间在程序的DATA 或者 BSS 段，且这两个段都取决与所用的操作系统。
2 从磁盘空间考虑
1<<30个数需要的空间为1<<32Bytes = 4GB

#生成指定范围内所有互不相同的数
解法的一般思路：

将需要生成的数顺序存放，随机生成下标，取出对应下标的值，将最后的数填补到刚刚的下标对应的位置上，修改随机数生成的下标，循环此过程。
将需要生成的数顺序存放，随机生成下标，标记该数已被访问，循环直到所有数都被标记。
随机生成指定范围内的一个数，标记该数，循环此过程，直到所有该范围的数都被标记。
用什么标记
直接用数组标记；array[Upper_bound]
用STL中的bitset；bitset<(Upper_bound/32)>，内存需求是方法1的1/32；

使用位向量；使用数组，但是每个数组元素标记32个需要生成的数，因为sizeof(int) = 4，总共4B * 8bits/B = 32 bits；所以内存需求和bitset一样，该方法的具体代码为（摘自编程珠玑）：

#define BITSEPRWORD 32
#define SHIFT 5
#define MASK 0x1F

int a[1 +100000000/BITSEPRWORD];
int set(int i) { a[i>>SHIFT] |= (1<<(i&MASK));}
int clr(int i) { a[i>>SHIFT] &= ~(1<<(i&MASK));}
itn test(int i) { return a[i>>SHIFT] &　(1<<(i&MASK));}

实例

一种基于位向量和rand()的实现方法

#define BITSWORD 32
#define SHIFT 5
#define MASK 0x1f
#define SET(A,POS) (A[POS>>SHIFT] |= (1<<(POS&MASK)))
#define CLR(A,POS) (A[POS>>SHIFT] &= ~(1<<(POS&MASK)))
#define TEST(A,POS) (A[POS>>SHIFT] & (1<<(POS&MASK)))
#define MAX (0x1ULL<<27)

unsigned a[1+MAX/BITSWORD]={0};
int main()
{
    unsigned r,ans=0;
    long long tick = 0, confilicts =0;
    while(ans <MAX)
    {
        r = rand()%MAX;
        tick++;
        bool in = TEST(a,r);
        if(!in)
        {
            SET(a,r);
            ans++;
        }
        else
            confilicts++;
    }
    cout<<tick/1024/1024<<"M"<<endl;
    cout<<confilicts/1024/1024<<"M"<<endl;
    return 0;
}

以上算法的结果为：

1
2
3

182.29 S //执行时间
2479 M   //总共生成的随机数，M=1024*1024
2351 M   //冲突的个数

也就是说，为了生成一千万个数，rand执行了2479M次，而且只生成了一千万个。

下面是一种改进的算法，对于每次生成的随机数，如果之前已经生成过了，那么根据遍历找到第一个没有被标记的数，然后输出。

#define BITSWORD 32
#define SHIFT 5
#define MASK 0x1f
#define SET(A,POS) (A[POS>>SHIFT] |= (1<<(POS&MASK)))
#define CLR(A,POS) (A[POS>>SHIFT] &= ~(1<<(POS&MASK)))
#define TEST(A,POS) (A[POS>>SHIFT] & (1<<(POS&MASK)))
#define MAX (0x1ULL<<30)

unsigned a[1+MAX/BITSWORD]={0};
int main()
{
    unsigned r,ans=0;
    long long tick = 0;
    long long confilicts =0;
    while(ans <MAX)
    {
        r = rand()%MAX;
        tick++;
        bool in = TEST(a,r);
        if(!in)
        {
            SET(a,r);
            ans++;
        }
        else
        {
            unsigned pos=1;
            long long inc;
            while(r<MAX)
            {
                inc = pos*pos;
                if((r+inc)>MAX || (r-inc)<0)
                    break;
                if(!TEST(a,r+inc))
                {
                    SET(a,r+inc);
                    ans++;
                    break;
                }
                else if(!TEST(a,r-inc))
                {
                    SET(a,r-inc);
                    ans++;
                    break;
                }
                pos++;
            }
            if((r+inc)>MAX || (r-inc)<0)
            confilicts++;
        }
    }

    cout<<"total random: "<<tick/1024<<"k"<<endl;
    cout<<"confilicts: "<<confilicts<<endl;
    return 0;
}

以上算法结果：

1
2
3

732.19 S
1049039k
474631

求知若饥，虚心若愚

生成一亿个互不相同的数

为什么是一亿

用什么标记

实例