关于位运算符的笔记

主要讨论位与运算符（&）、位或运算符（l）、位异或运算符（^）

1 定义和概念

• 位运算符作用于整数类型的运算对象，并把运算对象看成是二进制位的集合。位运算符提供检查和设置二进制位的功能。
• 一般来说，如果运算对象是“小整型”，则它的值会被自动提升成较大的整数类型。运算对象可以是带符号的，也可以是无符号的。如果运算对象时带符号的且值为负，那么位运算符如何处理运算对象的“符号位”依赖于机器。而且，此时的左移操作可能会改变符号位的值，因此是一种未定义的行为。关于符号位如何处理没有明确的规定，所以强烈建议仅将位运算符用于处理无符号类型。

2 位与位或位异或运算符

• 对于位与运算符（&）来说，如果两个运算对象的对应位置都是1则运算结果中该位为1，否则为0
• 对于位或运算符（l）来说，如果两个运算对象的对应位置至少有一个为1则运算结果中该位为1，否则为0
• 对于位异或运算符（^）来说，如果两个运算对象的对应位置有且只有一个为1则运算结果中该位为1，否则为0

3 使用位运算符解决汉明距离问题

在《C++ Primer》中，这一节举了一个学生测验的例子，很好的说明了使用位运算符可以很容易的解决一些实际问题。刚好这几天刷题也遇到了一个使用位运算符的问题，在此记录一下。

题目如下：

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.Given two integers x and y, calculate the Hamming distance.(0≤ x，y <$2^{31}$ )

这道题就是在求汉明距离，汉明距离指的是两个整数转换成二进制后，相应位不同的位置共有几个。比如：

那么1和4之间的汉明距离就是2。学习位运算符之后，这道题就容易多了，不用自己去将整数转换成二进制，只要两步工作就能到达目的。

1. 首先将两个整数进行异或操作，相应不同的位置一定是一个为1一个为0，这样得出的整数对应的二进制数上有几个1就说明两个整数有几个不同的位置。
2. 然后计算下上一步得到的数上有多少个1就是题目要求的汉明距离了

对于第一步代码显而易见

int z = x ^ y;

第二步可以用三种方法

• 右移位：将该数与1进行与运算,最右位为1时操作结果为true,n+1

  while(z){
    if(z & 1){
        ++n;
    }
    z = z >> 1;
  }
  

• 左移位：基本思路和右位移相同

  unsigned int iFlag = 1;
  while(iFlag){
    if(z & iFlag){
        ++n;
    }
    iFlag = iFlag << 1;
  }
  

• 与运算：将一个整数减去1后，其对应的二进制中最右边的一个1会变为0，若其后存在0，则其后所有0都会变成1。因此整数n，n&(n-1)后，会消掉二进制最右边的1。将一个数中所有1消掉次数即为该整数对应的二进制中1的个数

  while(z){
    ++n;
    n &= (n-1);
  }
  

完整代码：

int hammingDistance(int x, int y) {
        int z=x^y;
        int n=0;
        while(z){
            z&=(z-1);
            ++n;
        }
        return n;
    }

小结：左移位或者是右移位循环的次数取决于计算机的位数。而与运算的方法执行的次数只与该数中1的个数有关，因此与运算方法是三种方法中最好的。

参考资料

《C++ Primer》

• ← Previous Post
• Next Post →