今天做一道輸出第一次出現的數題目時，使用了用一個數組存儲之前出現過的數，然后搜索數組判斷是否出現過。這是用時間換空間的方法。

當然也可以用空間換時間，如果數據范圍已知且不大，比如為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; 右移一位

總結

以上是生活随笔為你收集整理的二进制数代替数组做标记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。