题解 | 明明的随机数

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n,a;
    while(scanf("%d",&n) != EOF)
    {
        unsigned char bitmask[125] = {0};
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a);
            bitmask[(a-1)/8] |= (1 << ((a-1)%8));  //如5，bitmask[0]:00010000;不减1就要申请126个字节的空间l;
        }
        for(int i=1;i<=1000;i++)
        {
            if(bitmask[(i-1)/8] & (1 << (i-1)%8))  //查询1到1000对应的位是否被置1;
            {
                printf("%d\n",i);
            }
        }
    }
    return 0;
}

基于桶排序的位运算，桶排序需要分配int count[1000]的大小，来记录题目给定范围的整数a(1~1000)有没有出现过，出现就count[a]置1，然后i从最小值1开始遍历到1000，并用if(count[i])判断，成立则输出i；

位运算改进，申请unsigned char bitmask[1000/8]的大小，以bit来标记是否数字出现，如1，就在bitmask[0]的bit0，二进制表现为00000001；8就是第0个字节的bit7，二进制为10000000；1000，就在bitmask[124]的bit7。