Java位运算—基础与常见问题总结

写在前：从现代计算机中所有的数据二进制的形式存储在设备中。即0、1两种状态，计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算，即将符号位共同参与运算的运算。

我们每一种语言最终都会通过编译器转换成机器语言来执行，所以直接使用底层的语言就不需要便编译器的转换工作从而得到更高的执行效率，当然可读性可能会降低，这也是为什么汇编在大部分情况下有更快的速度。

位运算基础

在Java中，位运算符有很多，主要有与(&)、非(~)、或(|)、异或(^）移位(>与>>>)，详细说明如下表所示。

image.png

注意以下几点:

• 在这6种操作符，只有 ~ 是单目操作符，其它5种都是双目操作符。

• 位操作只能用于整型数据，对 float 和 double 类型进行位操作会被编译器报错。

• 位操作符的运算优先级比较低（低于算数运算符），所以尽量使用括号来确保运算顺序，否则容易计算出错。比如要得到像 1，3，5，9 这些 2^i+1 的数字。写成 int a = 1 是不对的，程序会先执行 i + 1，再执行左移操作。应该写成 int a = (1 。

• 另外位操作还有一些复合操作符，如 &=、|=、 ^=、>=

• 运算符的优先级：~ 的优先级最高，其次是 > 和 >>>，再次是＆，然后是 ^，优先级最低的是 |。

常用技巧

1.判断奇偶

使用&1运算判断奇偶，主要依据一个最未位是 0 还是 1 来决定，为 0 就是偶数，为 1 就是奇数。如1,为… 0001，2为… 0010。

if (a == 5)
a & 1 == 1 替换 a % 2 == 1  //奇数
if (a == 2)
a & 1 == 0 替换 a % 2 == 0  //偶数

2.不使用交换两个数

private void swap1(int[] arr, int i, int j) {
    if (i == j) return;
    arr[i] ^= arr[j];
    arr[j] ^= arr[j];
    arr[i] ^= arr[j];
}

public void swap2(int[] arr,  int i,  int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

注意：当下标i == j 时，异或运算结果都为0，会出现错误。解决方案：（1）加判断，如上swap1();（2）使用tmp变量，如swap2()所示。

异或原地交换值涉及规则：

• 异或运算满足交换律
• 相同的数异或结果为0
• 任何数与0异或都不变

3.位掩码

在Web开发中，为了实现一个良好的访问控制系统，权限和角色管理是个很重要的部分，而如何保存、修改某个角色的权限，是个很值得思考的问题（当然，这个在任何涉及权限控制的系统中都适用）。而在某些情况下，某个组件可能具有多个可叠加的属性状态，这个也可以使用位掩码。

在这种情况下，使用位掩码的话，可以提供很大的灵活性，并且可以相对地减少存储空间（相对于你使用权限的集合或者多个布尔值来表示）。

位掩码的思想是，每个位表示一种权限或者属性，1表示具有，0表示不具有。这样，仅仅使用n个位，就可以表示2^n个权限状态。

举个栗子，数据库的基本操作：增（INSERT）、删（DELETE）、改（UPDATE）、查（SELECT）。我们需要四个位来表示这些权限：

int INSERT=1

如果我们以变量permission存储权限的话，以INSERT为例，可以有下面这些操作：

permission |= INSERT;//添加权限
permission &= ~INSERT;//删除权限
bool allowed = (permission & INSERT) == INSERT;//是否具有权限

4.子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

来源：力扣（LeetCode 78）链接：https://leetcode-cn.com/problems/subsets

示例:输入: nums = [1,2,3]

输出:

[
 [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

分析：事实上n个元素的集合的子集共有2^n个(包含空集)，集合的每个元素，都有可以选或不选，如下图所示{A, B, C}的子集分析：

A 元素为 100 = 4； B元素为010 = 2； C元素为001 = 1
若要构造某个集合，即使用A，B，C对应的三个整数依次与该集合对应的整数做&运算，当为真（为1）时，将该元素push进集合。

代码实现：

public List> subsets(int[] nums) {
    List> ans = new ArrayList();
    int n = nums.length, count = 1  sub = new ArrayList();
        for (int j = 0; j > j) & 1) == 1) {    // 第j位存在，加入子集中
                sub.add(nums[j]);
            }
        }
        ans.add(sub);
    }
    return ans;
}

PS:

• count = 1
• i >> j ：就是 i 化为二进制的存储，整体右移 j 位

5.待补充…

参考链接：
https://www.cnblogs.com/ktyanny/archive/2009/12/25/1632297.html
https://blog.csdn.net/zmazon/article/details/8262185