事實上,我們是用每一個 元素表示一個32位的二進制字符串,這樣這個元素可以保留相鄰32個號碼是否存在的信息,數組范圍就下降到10000000/32了.例如對于號碼 89256,由于89256 mod 32=2789…8,這樣我們應該置a[2789]中32位字符串的第8位(從低位數起)為1.
#define WORD 32#define SHIFT 5 ////移動5個位,左移則相當于乘以32,右移相當于除以32取整#define MASK 0x1F //16進制下的31#define N 10000000int bitmap[1 + N / WORD];/* * 置位函數――用"|"操作符,i&MASK相當于mod操作 * m mod n 運算，當n = 2的X次冪的時候,m mod n = m&(n-1) */void set(int i) { bitmap[i >> SHIFT] |= (1 << (i & MASK));}/* 清除位操作，用&~操作符 */void clear(int i) { bitmap[i >> SHIFT] &= ~(1 << (i & MASK));}/* 測試位操作用&操作符 */int test(int i) { return bitmap[i >> SHIFT] & (1 << (i & MASK));}實現排序（不能重復）：
int main(void) { FILE *in = fopen("in.txt", "r"); FILE *out = fopen("out.txt", "w"); if (in == NULL || out == NULL) { exit(-1); } int i = 0; int m; for (i = 0; i < N; i++) { clear(i); } while (!feof(in)) { fscanf(in, "%d", &m); printf("%d/n", m); set(m); } printf("abnother"); for (i = 0; i < N; i++) { if (test(i)) { printf("%d/n", i); fprintf(out, "%d/n", i); } } fclose(in); fclose(out); return EXIT_SUCCESS;}新聞熱點
疑難解答
圖片精選
