位运算-yuyu888 Blog

序言

位运算是计算机的基础，熟练使用位运算，将极大的扩展我们的思路和眼界，也可以提高算法的计算效率降低系统开销；

位运算基础

&

按位与

如果两个相应的二进制位都为1，则该位的结果值为1，否则为0
|

按位或

两个相应的二进制位中只要有一个为1，该位的结果值为1
^

按位异或

若参加运算的两个二进制位值相同则为0，否则为1
~

取反

~是一元运算符，用来对一个二进制数按位取反，即将0变1，将1
«

左移

用来将一个数的各二进制位全部左移N位，右补0
»

右移

将一个数的各二进制位右移N位，移到右端的低位被舍弃，对于无符号数，高位补0

题解

判断两个数是否相同

!(num1 ^ num2)

判断偶数

!(num & 1)

判断num是否是2的n次方

!(num & (num - 1))
一个数如果是2的n次方，那么它的二进制只有1个1，比如10, 100, 1000，这个数减1是01, 011, 0111，这样相与必然等于0，这就是!(num & (num -1))的判断, 有一个例外情况是0，0不是2的幂，但它和任意数与都为0，所以应该将它排除在外，所以最严谨的公式
num && (!(num & (num - 1)))

bit串截取

num&( (1<<len) - 1 )

异或加密

异或加密是一个很简单且速度很快的算法，它利用了xor的这个特性：A ^ B ^ B = A，其中A是明文，B是密钥。

加密过程是：A ^ B = C，A和B异或后得到密文C。
解密过程是：C ^ B = A，密文C和B异或后得到明文A。

为什么这个等式能成立呢，因为异或的两个规律：

一个数和它自己异域的结果等于0，即N ^ N = 0
一个数和0异域的结果等于它自己，即N ^ 0 = N

现在我们来推导这个过程：

A ^ B ^ B = A ^ (B ^ B) = A ^ 0 = A

演算

A=17 B=5

17^5=20

10001 ^ 00101 = 10100

20^5=17

10100 ^ 00101 = 10001

位图（bitmap）运算

假如我们有一组数字：2，3，7，8 我们把存入到集合set里；set初始值设为0；

添加

    set = set | (1 << (num-1))

    例如：

    插入 2 ：set = 0 | (1 << (2-1) ) = 10

    插入 3 ：set = 10 | ( 1 << (3-1) ) = 110

    插入 7 ：set = 110 | ( 1 << (7-1) ) = 100 0110

    插入 8： set = 100 0110 | ( 1 << (8-1) ) = 1100 0110

删除

    set = set ^ (1 << (num-1)) 

    例如：

    删除 7 ：1100 0110 ^ (1 << (7-1)) = 1100 0110 ^ 0100 0000 = 1000 0110 

    当 num 确实存在于set中时， 上述表示时正确的， 最正确的表示方法

    set = set & (~(1 << (num-1)))

是否存在

    set & (1 << (num-1)) 

    例如：

    是否存在 7 ： 1100 0110 & (1 << (7-1)) = 1100 0110 & 0100 0000 = 0100 0000 

    是否存在 6 ： 1100 0110 & (1 << (6-1)) = 1100 0110 & 0010 0000 = 0000 0000 => 0

是否是子集

    !(( set1 & set2 ) ^ set2)
  
    演算：

    【例1】

    set1 初始化为 { 2，3，7，8 } 的集合 1100 0110

    set2 初始化为 { 2, 3 }      的集合 0000 0110

    则 !((1100 0110 & 0000 0110) ^ 0000 0110) = !(0000 0110 ^ 0000 0110) = !(0000 0000) 

    【例2】

    set1 初始化为 { 2，3，7，8 } 的集合 1100 0110

    set2 初始化为 { 2, 4 }      的集合 0000 1010

    则 !((1100 0110 & 0000 0110) ^ 0000 1010) = !(0000 0010 ^ 0000 1010) = !(0000 1000)

遍历bitmap

方法一

遍历每一位，判断是否是1，具体做法是判断当前最右一位是否为1，然后右移一次，循环往复

  function bitmap_traversal($bitmap){
      $list = array();
      $n=1;
      while($bitmap!=0){
          if($bitmap&1){
              $list[] = $n;
          }
          //$n = $n<<1;
          $n++;
          $bitmap = $bitmap>>1;
      }
      return $list;
  }

方法二

参考【判断num是否是2的n次方】我们可以通过 num & (num-1) 这种方式把最后一位1移除掉

演算过程

  num = 1100
  num-1 = 1011
  num & (num-1) = 1000

  我们需要做的就是：记录用当前值减去移除最后一位1后的值的差值，再把当前值设位移除最后一位1的数

  function bitmap_traversal2($bitmap)
  {
      $list = array();
      while($bitmap != 0){
          $list[] = log($bitmap-($bitmap & ($bitmap-1)),2)+1;
          $bitmap = $bitmap & ($bitmap-1);
      }
      return $list;
  }

位运算

序言