事实上,我们是用每一个 元素表示一个32位的二进制字符串,这样这个元素可以保留相邻32个号码是否存在的信息,数组范围就下降到10000000/32了.例如对于号码 89256,由于89256 mod 32=2789…8,这样我们应该置a[2789]中32位字符串的第8位(从低位数起)为1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#define WORD 32
#define SHIFT 5 ////移动5个位,左移则相当于乘以32,右移相当于除以32取整
#define MASK 0x1F //16进制下的31
#define N 10000000
/*
* 置位函数——用"|"操作符,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));
}
|
实现排序(不能重复):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
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;
}
|