二进制数代替数组做标记

今天做一道输出第一次出现的数题目时，使用了用一个数组存储之前出现过的数，然后搜索数组判断是否出现过。这是用时间换空间的方法。

当然也可以用空间换时间，如果数据范围已知且不大，比如为1到100
可以直接定义一个大小为100的数组 初始化为0
输入一个数时，若a[i-1]为0则输出，并对a[i-1]做标记

然后想到了用二进制数作为标记的方法，进一步节省空间。但是只能用于数据范围很小的数 比如0-30
若0出现了则第0位为1
30出现了则第30位置为1，即该数加上2的30次方
输入时，比如要判断30是否出现过，将该数除以2的30次方然后mod10不为0则第30位为1

#include<stdio.h>
int main()
{
   
 int a[20]={
   0};
 int i,n;
 for(i=0;i<20;i++)
 {
   
  scanf("%d",&a[i]);
  if(search(a,a[i],i)==0)
  {
   
   printf("%d ",a[i]);
  }  
 }  
 return 0;
}
int search(int a[],int t,int size)
{
   
 int i;
 for(i=0;i<size;i++)
 {
   
  if(a[i]==t)
  return 1;
 }
 return 0;
}

#include<stdio.h>
int i,a,b,n;
long long num[8]={
   0};
for(a=1;a<20;a++)
{
   
    for(b=1;b<20;b++)
    {
   
        n=a*a+b*b;
        if(n<=400)
        {
   
           num[n/64]=(((num[n/64]>>(n%64))|1)<<(n%64))|num[n/64];
        }
    }
}

for(i=0;i<=400;i++)
{
   
 if((num[i/64]<<63)>>63&1==1)
 printf("%d ",i);
 num[i/64]=num[i/64]>>1;
}

关键代码：
num[n/64]=(((num[n/64]>>(n%64))|1)<<(n%64))|num[n/64];
n为要标记的数，n/64确定标记数组中的下标，也就是数组中第一个long long 负责标记0-63 第二个标记64-127 以此类推
n%64为应该标记数组中第n/64个数的第几位
通过先右移，最低位置1，然后左移实现修改
由于右移过程中低位丢失，所以需要再与原来的数按位取或，恢复前面的值

读取标记位
if((num[i/64]<<63)>>63&1==1)
通过左移后右移再与1按位与判断最低位是否为1

并且每轮num[i/64]=num[i/64]>>1; 右移一位