常见的位操作及其应用

概述

与、或、异或、取反或者移位运算这几种基本的位操作想必诸位读者并不陌生，如果我们能在某些合适场景下使用位运算，有些时候可以大大提高算法的效率。但由于本身位运算太过灵活，甚至某些技巧比较苦涩难懂，因而，本篇文章主要介绍几种常见的或者有趣的位操作，并且给出一些用到这些技巧的算法题目，便于读者练习。

有趣的操作

1. 大小写字母转换

1. 利用 或操作 和空格将英文字母转成小写

('a' | ' ') = 'a';
('A' | ' ') = 'a';

2. 利用与运算 & 和下划线将英文字符转换成大写

('b' & '_') = 'B';
('B' & '_') = 'B';

3. 利用异或运算 ^ 和空格进行英文字符大小写互换

('d' ^ ' ') = 'D';
('D' ^ ' ') = 'd'

常用指数： 🔯🔯

容易指数：🔯🔯🔯

PS:上述技巧能够产生奇特效果的原因在于字符类型的数据都是通过 ASCII 进行编码的，字符本身其实就是数字，而刚好这些字符对应的数字通过位运算符就可以得到正确结果，此处就不展开来说了。

2. 判断两个数是否异号

int x = -1, y = 2;
boolean f = ((x ^ y) < 0); // true 两个int类型数据进行异或运算小于零证明异号

int x = 1, y = 2;
boolean f = ((x ^ y) < 0); // false 两个int类型数据进行疑惑运算大于零证明同好

常用指数：🔯🔯🔯

困难指数：🔯

PS： 这个操作在我们判断两个数异号的时候非常有用，一方面运算效率较高，另一方面可以减少 if else 分支的使用。其背后的原理主要是一个正数补码的符号位和一个负数补码的符号位肯定想法，经过疑惑运算后，最后符号位结果肯定是 1(代表负数)。

3. 移除最后一位"1"

byte n = 10;
// n的二进制表示为: 0 0 0 0 1 0 1 0
//       异或运算  ^
//n-1的二进制表示为:0 0 0 0 1 0 0 1
n & (n-1); //结果为:0 0 0 0 1 0 0 0

根据上边的注释以及示意图，整个操作过程应该不难理解

简单来说 n & (n -1 ) 主要作用：就是消除数字 n 的二进制表示中的最后一个 1.

常用指数：🔯🔯🔯🔯🔯

困难指数：🔯🔯

PS： 这个操作特别常用，在好多 leetcode 题目中都有涉及,比如用来判断一个数的二进制数中 1 的个数。

4. 获取最后一个 1

byte n = 10;
//结果为:0 0 0 0 0 0 1 0
(n & (n-1)) ^ n; 

常用指数：🔯🔯🔯🔯

困难指数：🔯🔯🔯

PS: 该操作刚好和操作 3 相反，主要是为了获取数字 n 的二进制表示中的最后一个 1.该操作通常会用在位标记的时候使用（可参考汉明距离）。

5. 异或运算的简单性质

a=0^a=a^0

0=a^a

常用指数：🔯🔯🔯🔯

困难指数：🔯

PS:这个性质在我们判断两个数是否相同的时候非常常用。

应用

前边总结了那么多常用的位操作，下边来做几道题消化吸收一下刚刚所学的知识。

1. 只出现一次的数字

这道题比较简单，说实话即使不用位运算我们也可以有好多种方法求解，比如可以用一个 Map 来对元素进行 boolean 标记来求解。但如果我们此处能想到用异或运算的性质，那这道题目我们便可以简单优雅的解出来。

思路： 用一个初值为 0 的变量不断和数组中的元素进行异或运算，最终得到的变量值便是最终结果。

原因： 因为 0 和任何一个元素进行异或运算都是 0，而任何两个相同元素进行异或之后的结果都是 0，而题目中只有一个数是单独存在的，其他数都是 2 个，因而不断进行异或运算最后的结果必然是那个独特的数值，也就是最终的结果。

代码如下：

public int singleNumber(int[] nums) {
        int result = 0;
        for (int i =0;i<nums.length;i++){
            result ^=nums[i];
        }
        return result;
    }

2. 汉明距离

这个问题，我们常规思路可能是通过一次 for循环 并且在循环过程中判断不同位置的二进制位是否相同，同时做计数。

但同样的我们通过位运算可以比较快速的解决该问题

思路： 通过一次异或运算，获取一个不同位置二进制数构成的一个整数，然后计算该整数中 1 的个数即为最终结果。在计算 1 个数的时候一个小技巧，可以通过 n & (n-1)不断做移位运算来计算。

实现代码如下：

 public int hammingDistance(int x, int y) {
    x = x ^ y;
    int count = 0;
    while (x != 0) {
      x = x & (x - 1);
      count++;
    }
    return count;
  }

1. 只出现一次的数字 III

这个问题跟只出现一次的数字很像，主要差别可能在这个唯一的数是两个，而不是一个。同样的这个问题有很多常规的结果，比如街主要 map 来统计和标注每个数字出现的次数。但我们使用位运算的时候我们会发现其速度是极快的。

思路：

前面分析了此题目和原来题目的最大区别在于只出现一次的数字不再是唯一的了，而变成了两个。因而我们考虑能否对着集合元素按照某种标准做一个分类，经过分类之后，每一个类别都分别包含一个特殊的元素以及若干相同的元素。此时该问题就转换成了问题 1，那个简单的问题。

其实分类标准应该不难找，由于这两个元素是不相等的，因此这两个元素的某个二进制位必然是不相等。因此我们可能考虑根据该二进制位为 0 或者 1 将数组分成 A 组合 B 组。而这个数组中其它数字要么就属于 A 组，要么就属于 B 组。再对 A 组和 B 组分别执行“异或”解法就可以得到 A，B 了。而要判断 A，B 在哪一位上不相同，只要根据 A 异或 B 的结果就可以知道了，这个结果在二进制上为 1 的位就说明 A，B 在这一位上是不相同的。

比如：

int a[] = {1, 1, 3, 5, 2, 2}

整个数组异或的结果为 3^5，即 0x0011 ^ 0x0101 = 0x0110

对 0x0110，第 1 位（由低向高，从 0 开始）就是 1。因此整个数组根据第 1 位是 0 还是 1 分成两组。

a[0] =1  0x0001  第一组

a[1] =1  0x0001  第一组

a[2] =3  0x0011  第二组

a[3] =5  0x0101  第一组

a[4] =2  0x0010  第二组

a[5] =2  0x0010  第二组

第一组有{1,1,5}，第二组有{3,2,2}，然后对这二组分别执行“异或”解法就可以得到 5 和 3 了。\

实现代码如下：

public int[] singleNumber(int[] nums) {
    int xorVal = 0;
    for (int num : nums) {
        xorVal ^= num;
    }
    // 获取最后一个 1
    xorVal = (xorVal & (xorVal - 1)) ^ xorVal;

    int res[] = new int[2];
    //根据和xorVal的与运算结果不同进行分类
    for (int num : nums) {
        if ((num & xorVal) == 0) {
            res[0] ^= num;
        } else {
            res[1] ^= num;
        }
    }
    return res;
}

总结

以上便是一些常用的位操作，以及对应的一些简单应用。其实关于微操作的技巧很多，有很多也非常有趣，其中有一个叫做 BitTwiddling Hacks 的外国网站收集了几乎所有位操作的黑科技玩法，感兴趣的话，可以看一看哈！！

参考

1. https://leetcode-cn.com/problems/single-number-iii/solution/java-yi-huo-100-yao-shi-kan-bu-dong-wo-jiu-qu-chu-/
2. https://greyireland.gitbook.io/algorithm-pattern/shu-ju-jie-gou-pian/binary_op#chang-jian-ti-mu