Java基础 -- 位运算

简介

程序中的所有数在计算机内存中都是以二进制的形式存储的。位运算(Bitwise operation)就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高。

详解

Java位运算细化划分可以分为按位运算和移位运算，见下表。

在进行位运算详解之前，先来普及下计算机中数字的表示方法。对于计算机而言，万物皆0、1，所有的数字最终都会转换成0、1的表示，有3种体现形式，分别是：原码、反码和补码。

• 原码：原码表示法在数字前面增加了一位符号位，即最高位为符号位，正数位该位为0，负数位该位为1.比如十进制的5如果用8个二进制位来表示就是00000101，-5就是10000101。
• 反码：正数的反码是其本身，负数的反码在其原码的基础上，符号位不变，其余各个位取反。5的反码就是00000101，而-5的则为11111010。
• 补码：正数的补码是其本身，负数的补码在其原码的基础上，符号位不变，其余各位取反，最后+1。即在反码的基础上+1。5的反码就是00000101，而-5的则为11111011。

了解了这几个概念后，我们现在先记住一个结论，那就是在计算机系统中，数字一律用补码来表示、运算和存储，具体的原因可以看这篇文章的讨论，这里不做更多讨论，因为不是本文的重点。

与运算（&）

规则：转为二进制后，两位为1，则结果为1，否则结果为0。

或运算（|）

规则：转为二进制后，有一位为1，则结果为1，否则结果为0。

非运算（~）

规则：转为二进制后，~0 = 1,~1 = 0。

异或运算（^）

规则：转为二进制后，两位不相同，结果为1，否则为0。

左移运算（<<）

规则：转为二进制后，各二进制位全部左移N位，高位丢弃，低位补0。

右移运算（>>）

规则：转为二进制后，各二进制位全部右移N位，若值为正，则在高位插入 0，若值为负，则在高位插入 1。

无符号右移运算（>>>）

规则：转为二进制后，各二进制位全部右移N位，无论正负，都在高位插入0。

应用

不用额外的变量实现两个数字互换

见参考资料中的BitOperationTest，方法reverse通过三次异或操作完成了两个变量值的替换。

证明很简单，我们只需要明白异或运算满足下面规律（实际不止如下规律）：

0^a = a，a^a = 0；
a ^ b = b ^ a；
a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c；
a ^ b ^ a = b；

假设a,b两个变量，经过如下步骤完成值交换：a=a^b,b=b^a,a=a^b。 证明如下： 　　因为a ^ b = b ^ a，又a=a^b,b=b^a。故b=b^a= b^ (a^b)=a。 　　继续a=a^b，a=（a^b) ^ b^ (a^b)，故a=b。完成值交换。

不用判断语句实现求绝对值

公式如下：(a^(a>>31))-(a>>31)

先整理一下使用位运算取绝对值的思路：若a为正数，则不变，需要用异或0保持的特点；若a为负数，则其补码为原码翻转每一位后+1，先求其原码，补码-1后再翻转每一位，此时需要使用异或1具有翻转的特点。

任何正数右移31后只剩符号位0，最终结果为0，任何负数右移31后也只剩符号位1，溢出的31位截断，空出的31位补符号位1，最终结果为-1.右移31操作可以取得任何整数的符号位。

那么综合上面的步骤，可得到公式。a>>31取得a的符号，若a为正数，a>>31等于0，a^0=a，不变；若a为负数,a>>31等于-1 ，a^-1翻转每一位。

判断一个数的奇偶性

通过与运算判断奇偶数，伪代码如下：

n&1 == 1?”奇数”:”偶数”

奇数最低位肯定是1，而1的二进制最低位也是1，其他位都是0，所以所有奇数和1与运算结果肯定是1。

查找落单的数

将数组的数全部做异或，最后得到的数就是要找的数，因为和一个数做两次异或不会改变。

参考文章: 一文搞懂位运算