作者：nnamyp_826 | 来源：互联网 | 2023-08-18 17:26
位向量&＃xff1a;用位来存储一个数&＃xff0c;例如N&＃61;10000000个数&＃xff0c;每一位代表一个数
定义一个int类型的数组int a[N],如果a[9]&＃61;1,则代表文件中存在一个值为9&＃xff0c;不过由于这里我们定义的是int,一个int是4字节&＃xff0c;也就是32位&＃xff0c;有效利用这个32位的可以缩减实际所开数组大小的&＃39;N&＃39;值,这里实际上也就只用开到int [n>>5]; 这样每一个数组的值,例如&＃xff1a;
a[0]代表了0-31; a[1]代表了32-63...依次类推
而隐藏掉的32位需要通过特定手段找回来才能确定具体代表的是哪一个值&＃xff0c;由mask&＃61;31&＃xff0c;与i值相与可以得到末尾的那32位值&＃xff0c;由此再通过&＃xff08;1<<(mask&i))就可以表达出是该组中的32个数中的哪一个数
这样
void set(int i){ a[i>>SHIFT] |&＃61; (1<<(i & MASK) ); }
void clr(int i){ a[i>>SHIFT] &&＃61; ~(1<<(i&MASK) ); }
void test(int i){ return a[i>>SHIFT]&(1<<(i&MASK) ); }
京公网安备 11010802041100号