bitmap_guisu，程序人生。 逆水行舟，不进则退。(2)

c语言实现：

#define BITSPERWORD 32 #define SHIFT 5 #define MASK 0x1F #define N 10000000 int a[1 N/BITSPERWORD];//申请内存的大小 //set 设置所在的bit位为1 void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); } //clr 初始化所有的bit位为0 void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); } //test 测试所在的bit为是否为1 int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); } int main() {int i; for (i = 0; i < N; i) clr(i); while (scanf("%d", &i) != EOF) set(i); for (i = 0; i < N; i) if (test(i)) printf("%d\n", i); return 0; }

注明： 左移n位就是乘以2的n次方，右移n位就是除以2的n次方

解析本例中的void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
1) i>>SHIFT：
其中SHIFT=5，即i右移5为，2^5=32,相当于i/32，即求出十进制i对应在数组a中的下标。比如i=20，通过i>>SHIFT=20>>5=0 可求得i=20的下标为0；

2) i & MASK：
其中MASK=0X1F,十六进制转化为十进制为31，二进制为0001 1111，i&（0001 1111）相当于保留i的后5位。

比如i=23，二进制为：0001 0111，那么
0001 0111
& 0001 1111 = 0001 0111 十进制为：23
比如i=83，二进制为：0000 0000 0101 0011，那么
0000 0000 0101 0011
& 0000 0000 0001 0000 = 0000 0000 0001 0011 十进制为：19

i & MASK相当于i%32。

3) 1<<(i & MASK)
相当于把1左移 (i & MASK)位。
比如(i & MASK)=20，那么i<<20就相当于：
0000 0000 0000 0000 0000 0000 0000 0001 << 20
=0000 0000 0001 0000 0000 0000 0000 0000

注意上面 “|=”.

在博文：位运算符及其应用提到过这样位运算应用：

将int型变量a的第k位清0，即a=a&~(1<<k)
将int型变量a的第k位置1， 即a=a|(1<<k)

这里的将 a[i/32] |= (1<<M));第M位置1 .

4) void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }等价于：
void set(int i) { a[i/32] |= (1<<(i%32)); }

即实现上面提到的三步：

1.求十进制0-N对应在数组a中的下标：n/32

2.求0-N对应0-31中的数： N%32=M

3.利用移位0-31使得对应32bit位为1: 1<<M，并置1;

php实现是一样的：

<?php error_reporting(E_ERROR); define("MASK", 0x1f);//31 define("BITSPERWORD",32); define("SHIFT",5); define("MASK",0x1F); define("N",1000); $a = array(); //set 设置所在的bit位为1 function set($i) { global $a; $a[$i>>SHIFT] |= (1<<($i & MASK)); } //clr 初始化所有的bit位为0 function clr($i) { $a[$i>>SHIFT] &= ~(1<<($i & MASK)); } //test 测试所在的bit为是否为1 function test($i){ global $a; return $a[$i>>SHIFT] & (1<<($i & MASK)); } $aa = array(1,2,3,31, 33,56,199,30,50); while ($v =current($aa)) { set($v); if(!next($aa)) { break; } } foreach ($a as $key=>$v){ echo $key,'=', decbin($v),"\r\n"; } 然后我们打印结果：

0=11000000000000000000000000001110
1=1000001000000000000000010
6=10000000

31 30 3 2 1

0= 1 1 00 0000 0000 0000 0000 0000 0000 1 1 1 0

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/ruanjian/article-6531-2.html