C實作bitmap位圖

事實上,我們是用每一個 元素表示一個32位的二進制字元串,這樣這個元素可以保留相鄰32個号碼是否存在的資訊,數組範圍就下降到10000000/32了.例如對于号碼 89256,由于89256 mod 32=2789…8,這樣我們應該置a[2789]中32位字元串的第8位(從低位數起)為1.

基本的操作：

[cpp] 
   ​​view plain​​​
   ​​​copy​​ 
   
 
   
 
 
1. #define WORD 32
2. #define SHIFT 5 移動5個位,左移則相當于乘以32,右移相當于除以32取整
3. #define MASK 0x1F //16進制下的31
4. #define N 10000000
5. int bitmap[1 + N / WORD];
6. /*
7. * 置位函數——用"|"操作符,i&MASK相當于mod操作
8. * m mod n 運算，當n = 2的X次幂的時候,m mod n = m&(n-1)
9. */
10. void set(int i) {
11. bitmap[i >> SHIFT] |= (1 << (i & MASK));
12. }
13. /* 清除位操作，用&~操作符 */
14. void clear(int i) {
15. bitmap[i >> SHIFT] &= ~(1 << (i & MASK));
16. }
17. /* 測試位操作用&操作符 */
18. int test(int i) {
19. return bitmap[i >> SHIFT] & (1 << (i & MASK));
20. }
 
 實作排序（不能重複）：
 
 
 
   [cpp] 
   ​​view plain​​​
   ​​​copy​​ 
   
 
   
 
 
1. int main(void) {
2. FILE *in = fopen("in.txt", "r");
3. FILE *out = fopen("out.txt", "w");
4. if (in == NULL || out == NULL) {
5. exit(-1);
6. }
7. int i = 0;
8. int m;
9. for (i = 0; i < N; i++) {
10. clear(i);
11. }
12. while (!feof(in)) {
13. "%d", &m);
14. "%d/n", m);
15. set(m);
16. }
17. "abnother");
18. for (i = 0; i < N; i++) {
19. if (test(i)) {
20. "%d/n", i);
21. "%d/n", i);
22. }
23. }
24. fclose(in);
25. fclose(out);
26. return EXIT_SUCCESS;
27. }