所谓位向量就是由一些二进制位组成的向量,位逻辑运算有与(&).或(|),非(!),移位(<< >>)等。
算法解析:
1.set算法中i>>SHIFT相当于i/32,也就是2^5,功能是找出i对应数组中到哪一行,每一行都是32Bit,需要将相应到位置置为0或者1;需要1<<(i&MASK),其中i&MASK是计算需要左移的位数,然后把1向左移动这么多位,剩下的就是和数组中的元素或运算。set算法可以改写为:
2.clr算法中通过1<<(i&MASK),其中i&MASK是计算需要左移的位数,然后把1向左移动这么多位,然后把该数字取反,和数组中到元素与运算,即可置第i位为0.clr算法可以改写为:
使用位逻辑运算实现位向量所指实现位向量的设置,清零以及探测功能。
#define BITPERWORD 32 #define SHIFT 5 #define MASK 0x1F #define N 10000000 int a[1+N/BITPERWORD] //设置数组第i位为1 void set(int i) { a[i>>SHIFT] |= (1<<(i&MASK)); } //清空数组第i位为0 void clr(int i) { a[i>>SHIFT] &= ~ (1<<(i&MASK)); } //查询数组第i位数字 void test(int i) { return a[i>>SHIFT] &(1<<(i&MASK)); }
算法解析:
1.set算法中i>>SHIFT相当于i/32,也就是2^5,功能是找出i对应数组中到哪一行,每一行都是32Bit,需要将相应到位置置为0或者1;需要1<<(i&MASK),其中i&MASK是计算需要左移的位数,然后把1向左移动这么多位,剩下的就是和数组中的元素或运算。set算法可以改写为:
void set(int i) { a[i/32] |= (1<<(i%32)); }
2.clr算法中通过1<<(i&MASK),其中i&MASK是计算需要左移的位数,然后把1向左移动这么多位,然后把该数字取反,和数组中到元素与运算,即可置第i位为0.clr算法可以改写为:
void clr(int i) { a[i/32] &= ~ (1<<(i%32)); }3.test算法中通过1<<(i&MASK),其中i&MASK是计算需要左移的位数,然后把1向左移动这么多位,然后把和数组中到元素与运算,数组中元素为1就返回1,数组中元素为0就返回0.test算法可以改写为:
void test(int i) { return a[i/32] &(1<<(i%32)); }