Java位运算

前言

从原补反到Java位运算，学习记录。

机器数

一个数在计算机的存储形式是二进制数，我们称这些二进制数为机器数，机器数是有符号，在计算机中用机器数的最高位存放符号位，0表示正数，1表示负数。

因为带有符号位，所以机器数的形式值不等于其真值，以机器数1000 0111为例，其真正表示的值为-7，而形式值为135。将带符号的机器数的真正表示的值称为机器数的真值。

无符号数是指整个机器字长的全部二进制位均表示数值位，相当于数的绝对值。还是以1000 0111为例，无符号数就是指其形式值135。Java中不存在无符号整数类型。

原码、反码、补码

简单起见，假设使用8位二进制数（一个字节）存储整数，实际上在Java中为四个字节，即32位。

原码的表示与机器数真值表示的一样，即用第一位表示符号，其余位表示数值。

反码的表示中，正数的反码是其原码本身，负数的反码是在其原码的基础上，符号位不变，其余各位取反。

补码的表示中，正数的补码是其原码本身，负数的补码是在其原码的基础上，符号位不变，其余各位取反后加1。

以十进制正数1和-1为例，其各码如下：

1:
原码=反码=补码=0000 0001

-1:
原码=1000 0001
反码=1111 1110
补码=1111 1111

计算机中整数实际只存储补码，因为只有补码的计算是准确的，这一点在此不作证明了。同时原码转换为补码的过程，也可以理解为数据存储到计算机内存中的过程，如下图：

八位原码和八位反码能够表示的区间只有[-127, 127]，而八位补码可以表示的范围为[-128, 127]，因为十进制-127和-1的相加运算用补码表示算得的结果为1000 0000，即用原本的“-0”来表示-128。所以计算机中一个字节的取值范围是[-128,127]。

需要注意的是，在计算机运算过后，对于负数结果需要转换为原码才能得到其真值。例如补码0b1000 0001，先转换为反码0b1000 0000，再按位取反（符号位不变）得到原码0b1111 1111，可知其真值为-127。

Java中的位运算符

Java 定义的位运算（bitwise operators）直接对整数类型的位进行操作，这些整数类型包括 long（64位），int（32位），short（16位），char（16位） 和 byte（8位）。

位运算符主要用来对操作数二进制的位进行运算。按位运算表示按每个二进制位（bit）进行计算，其操作数和运算结果都是整型值。

Java 语言中的位运算符分为位逻辑运算符和位移运算符两类，下面详细介绍每类包含的运算符。

位逻辑运算符

位逻辑运算符包含 4 个：&（AND）、|（OR）、~（NOT）和 ^（XOR）。除了 ~ 为单目运算符外，其余都为双目运算符。

位与运算符为&，其运算规则是：参与运算的数字，低位对齐，高位不足的补零，如果对应的二进制位同时为 1，那么计算结果才为 1，否则为 0。因此，任何数与 0 进行按位与运算，其结果都为 0。

位或运算符为|，其运算规则是：参与运算的数字，低位对齐，高位不足的补零。如果对应的二进制位只要有一个为 1，那么结果就为 1；如果对应的二进制位都为 0，结果才为 0。

位异或运算符为^，其运算规则是：参与运算的数字，低位对齐，高位不足的补零，如果对应的二进制位相同（同时为 0 或同时为 1）时，结果为 0；如果对应的二进制位不相同，结果则为 1。即相同为0，不同为1。

位取反运算符为~，其运算规则是：只对一个操作数进行运算，将操作数二进制中的 1 改为 0，0 改为 1。

位移运算符

位移运算符用来将操作数向某个方向（向左或者右）移动指定的二进制位数，它们都属于双目运算符。

左移位运算符为<<，其运算规则是：按二进制形式把所有的数字向左移动对应的位数，高位移出（舍弃），低位的空位补零。

有符号右位移运算符为>>，其运算规则是：按二进制形式把所有的数字向右移动对应的位数，低位移出（舍弃），若操作数为正数则高位补0，操作数为负数则高位补1。也称为算数右移。

无符号右位移运算符为>>>，其运算规则是：按二进制形式把所有的数字向右移动对应的位数，低位移出（舍弃），高位补0。也称为逻辑右移。

特别需要注意的是，在对char、byte、short类型的数进行移位操作前，编译器都会自动地将数值转化为int类型，然后才进行移位操作（这也导致位移表达式返回值为整型）。由于int型变量只占4字节，当右移位数超过32bit时，移位运算没有任何意义。所以，在Java语言中，为了保证移动位数地有效性，以使移动的位数不超过32bit，采取了取余的操作，即a>>n等价于a>>(n%32)。这一性质对于左右移位都有效。

另外，左移$n$位表示原来的值乘$2^n$，经常用来代替乘法操作，由于CPU直接支持位运算，因此位运算比乘法运算效率高。

复合位赋值运算符

所有的二进制位运算符都有一种将赋值与位运算组合在一起的简写形式。复合位赋值运算符由赋值运算符与位逻辑运算符或位移运算符组合而成。

包括&=、｜=、^=、<<=、>>>=和>>=。

实验

关于位运算呢，虽然看起来容易掌握，但是实际使用中可能还是会遇到一些问题，有时是由于真值与补码混淆造成的，我写了一个小demo来解释一下：

// author: SilenceZheng66
public static void bitwiseOperation(){
        byte a = -1;
        byte b = 1;

        System.out.println(~a); // 0
        System.out.println(~b); // -2
        System.out.println(a&b); // 1
        System.out.println(a|b); // -1
        System.out.println(b^a); // -2

        b^=a;
        System.out.println(b); // -2
        System.out.println(b>>1); // -1
        System.out.println(b<<1); // -4

        System.out.println(Integer.toBinaryString(a>>>2));// 00111111111111111111111111111111
        System.out.println(Integer.toBinaryString(a>>2)); // 11111111111111111111111111111111
    }

首先明确“真值=原码“，所以可以得到$a$的原码为1000 0001，$b$的原码为0000 0001。但在内存中，$a$被存储为1111 1111，这是由1000 0001 -> 1111 1110 -> 1111 1111得到的，也就是原码转换为补码的过程。$b$由于是正数，仍然被存储为原码形式。

那么~a为何是$0$呢？可以列出计算过程：1111 1111(a) -> 0000 0000(~a)。由于0000 0000的原码与补码相同，故其真值为$0$。下面再计算一个b^a吧，过程如下：

先计算异或：0000 0001 ^ 1111 1111 = 1111 1110
补码转化为真值：1111 1110 -> 1111 1101 -> 1000 0010
得到结果为-2

例题一：Leetcode190. 颠倒二进制位

问题描述：颠倒给定的 32 位无符号整数的二进制位。

思路一（我的愚蠢解法）：获取读入十进制数的二进制字符串，存入字符数组，反转后再转为int输出。

实现：

// author: SilenceZheng66
public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        String input = Integer.toBinaryString(n);
        char[] input_arr = input.toCharArray();
        char[] ans = new char[32];
        int j = 0;
        for(int i = input_arr.length-1; i>=0; i--){
            ans[j] = input_arr[i];
            j++;
        }
        // toBinaryString中高位的0不输出，需要补充。
        while(j<32){
            ans[j] = '0';
            j++;
        }
        return Integer.parseUnsignedInt(String.valueOf(ans), 2);
    }
}

思路二（官解一）：将 $n$ 视作一个长为 32 的二进制串，从低位往高位枚举 $n$ 的每一位，将其倒序添加到翻转结果中。代码实现中，每枚举一位就将 $n$ 右移一位，这样当前 $n$ 的最低位就是我们要枚举的比特位。当 $n$ 为 0 时即可结束循环。

实现：

public class Solution {
    public int reverseBits(int n) {
        int rev = 0;
        for (int i = 0; i < 32 && n != 0; ++i) {
            // n&1 只保留低位
            // << (31 - i) 移到反转后的位置
            // rev = rev ｜ (n & 1) << (31 - i) 存入翻转结果 rev
            rev |= (n & 1) << (31 - i);
            // n = n >>> 1 逻辑右移，高位补0
            n >>>= 1;
        }
        return rev;
    }
}

思路三（JDK用法）：Integer包装类提供了reverse方法，速度很快。

实现：

public class Solution {
    public int reverseBits(int n) {
        return Integer.reverse(n);
    }
}

参考

[1]http://c.biancheng.net/view/784.html
[2]https://blog.csdn.net/xwu_09/article/details/78285785
[3]https://www.cnblogs.com/linjiaxin/p/14870850.html
[4]https://zhuanlan.zhihu.com/p/371184302
[5]https://blog.csdn.net/MaybeForever/article/details/89109596

后记

首发于 silencezheng.top，转载请注明出处。

赏

谢谢打赏哟！

支付宝

微信