阅读796 返回首页    go 阿里云 go 技术社区[云栖]

编程珠玑之1.2位逻辑运算实现位向量

    所谓位向量就是由一些二进制位组成的向量，位逻辑运算有与（&）.或（|），非（！），移位（<<  >>）等。

   使用位逻辑运算实现位向量所指实现位向量的设置，清零以及探测功能。

#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));
}


最后更新：2017-04-04 07:03:27

  上一篇：go android Setting中隐藏项
  下一篇：go 【最近面试遇到的一些问题】JAVA UTF-8 GB2312 编码互转