《算法通关村——位运算常用技巧》

《算法通关村——位运算常用技巧》

位运算的性质有很多，此处列举一些常见性质，假设以下出现的变量都是有符号整数。

●幂等律：a &a=a，a ∣ a=a（注意异或不满足幂等律）；

●交换律：a & b=b & a，a ∣ b=b ∣ a，a⊕b=b⊕a；

●结合律：(a & b) & c=a & (b & c)，(a ∣ b) ∣ c=a ∣ (b ∣ c)，(a⊕b)⊕c=a⊕(b⊕c)；

●分配律：(a & b) ∣ c=(a ∣ c) & (b ∣ c)，(a ∣ b) & c=(a & c) ∣ (b & c)，(a⊕b) & c=(a & c)⊕(b & c)；

●德摩根律：∼(a & b)=(∼a) ∣ (∼b)，∼(a ∣ b)=(∼a) & (∼b)；

●取反运算性质：−1=∼0，−a=∼(a−1)；

●与运算性质：a & 0=0，a & (−1)=a，a & (∼a)=0；

●或运算性质：a ∣ 0=a；

●异或运算性质：a⊕0=a，a⊕a=0；

根据上面的性质，可以得到很多处理技巧，这里列举几个：

●a & (a−1) 的结果为将 a 的二进制表示的最后一个 1 变成 0；

●(补码)a & (−a)的结果为只保留 a 的二进制表示的最后一个 1，其余的 1 都变成 0。

处理位操作时，还有很多技巧，不要死记硬背，理解其原理对解决相关问题有很大帮助。下面的示例中，1s和0s分别表示与x等长的一串1和一串0：

而如何获取、设置和更新某个位的数据，也有固定的套路。例如：

1. 获取

该方法是将1左移i位，得到形如00010000的值。接着堆这个值与num执行”位与“操作，从而将i位之外的所有位清零，最后检查该结果是否为零。不为零说明i位为1，否则i位为0。代码如下：

boolean getBit(int num,int i){
  return ((num&(1<<i))!=0);
}
1
2
3

2. 设置（将某一位设置为1）

setBit先将1左移i位，得到形如00010000的值，接着堆这个值和num执行”位或“操作，这样只会改变i位的数据。这样除i位外的位均为零，故不会影响num的其余位。代码如下：

int setBit(int num,int i){
 return num |(1<<i);
}
1
2
3

3. 清零（将某一位设置为0）

该方法与setBit相反，首先将1左移i位获得形如00010000的值，对这个值取反进而得到类似11101111的值，接着对该值和num执行”位与“，故而不会影响到num的其余位，只会清零i位。

int clearBit(int num ,int i){

  int mask=~(1<<i);

  return num&mask;

 }
1
2
3
4
5
6
7

4. 更新

这个方法是将setBit和clearBit合二为一，首先用诸如11101111的值将num的第i位清零。接着将待写入值v左移i位，得到一个i位为v但其余位都为0的数。最后对之前的结果执行”位或“操作，v为1这num的i位更新为1，否则为0：

int updateBit(int num,int i,int v){
  int mask=~(1<<i);
  return (num&mask)|(v<<i); 
}	
1
2
3
4

点击链接：我正在「编程导航」和朋友们讨论有趣的话题，你⼀起来吧？

也可以加我QQ（2837468248）咨询说明来意！