06. 按位运算符和移位运算符

FengXueke 10月 18, 2022

post06

按位运算符和移位运算符

前置知识点

1.有符号数/机器数:

一个数在计算机中的二进制表示形式, 叫做这个数的机器数。机器数是带符号的，在计算机用一个数的最高位存放符号, 正数为0, 负数为1.

e.g（假设机器的字长是8位）

+3的二进制->00000011

-3的二进制->10000011

00000011 和 10000011则是机器数

2.真值

因为第一位是符号位，所以机器数的形式值就不等于真正的数值。所以为区别起见，将带符号位的机器数对应的真正数值称为机器数的真值

e.g

00000011的真值是(+0000011)=+3,
10000011的真值是(-0000011)=-3

3.原码，反码和补码

原码, 反码, 补码是机器存储一个具体数字的编码方式

3.1. 原码

原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值

e.g

+3的二进制原码->00000011

-3的二进制原码->10000011

3.2. 反码

正数的反码是其本身

负数的反码是在其原码的基础上, 符号位不变，其余各个位取反.

e.g

1
2
3

[+3] = [00000011]原 = [00000011]反

[-3] = [10000011]原 = [11111100]反

3.3. 补码

正数的补码就是其本身

负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)

[+3] = [00000011]原 = [00000011]补

[-3] = [10000011]原 = [11111100]反 = [11111101]补

现代计算机存储的是补码

4.移位运算规则

4.1. 左移位运算符(<<)能将运算符左边的运算对象向左移动运算符右侧指定的位数(在低位补 0)

4.2. “有符号”右移位运算符(>>)则将运算符左边的运算对象向右移动运算符右侧指定的位数。“有符号”右移位运算符使用了 “符号扩展”:若值为正，则在高位插入0;若值为负，则在高位插入1。

4.3. “无符号”右移位运算符(>>>)，它使用了“零扩展”:无论正负，都在高位插入0。

5.按位运算规则

若两个输入位都是 1，则 按位AND运算符(&) 在输出位里生成一个 1;否则生成 0。

若两个输入位里至少有一个是1，则 按位OR运算符(|) 在输出位里生成一个1;只有在两个输入位都是0的情况下，它才会生成一个 0。

若两个输入位的某一个是 1，但不全都是 1，那么 按位XOR(^，异或) 在输出位里生成一个 1。

按位NOT(~，也叫作“非”运算符) 属于一元运算符;它只对一个自变量进行操作(其他所有运算符都是二元运算符)。按位NOT生成与输入位的相反的值——若输入0，则输出1;输入1，则输出0

使用代码:

public class BitManipulation {
    public static void main(String[] args) {
        Random rand = new Random();
        int i = rand.nextInt();
        int j = rand.nextInt();
        pBinInt("-1", -1);
        pBinInt("+1", +1);
        int maxpos = 2147483647;
        pBinInt("maxpos", maxpos);
        int maxneg = -2147483648;
        pBinInt("maxneg", maxneg);
        pBinInt("i", i);
        pBinInt("~i", ~i);
        pBinInt("-i", -i);
        pBinInt("j", j);
        pBinInt("i & j", i & j); 
        pBinInt("i | j", i | j);
        pBinInt("i ^ j", i ^ j);
        pBinInt("i << 5", i << 5);
        pBinInt("i >> 5", i >> 5);
        pBinInt("(~i) >> 5", (~i) >> 5);
        pBinInt("i >>> 5", i >>> 5);
        pBinInt("(~i) >>> 5", (~i) >>> 5);
        long l = rand.nextLong(); long m = rand.nextLong(); 
        pBinLong("-1L", -1L);
        pBinLong("+1L", +1L);
        long ll = 9223372036854775807L; 
        pBinLong("maxpos", ll);
        long lln = -9223372036854775808L; 
        pBinLong("maxneg", lln);
        pBinLong("l", l);
        pBinLong("~l", ~l);
        pBinLong("-l", -l);
        pBinLong("m", m);
        pBinLong("l & m", l & m);
        pBinLong("l | m", l | m);
        pBinLong("l ^ m", l ^ m);
        pBinLong("l << 5", l << 5); 
        pBinLong("l >> 5", l >> 5); 
        pBinLong("(~l) >> 5", (~l) >> 5); 
        pBinLong("l >>> 5", l >>> 5); 
        pBinLong("(~l) >>> 5", (~l) >>> 5);
    }
    static void pBinInt(String s, int i) {
        System.out.println( s + ", int: " + i + ", binary: ");
        System.out.print(" ");
        for(int j = 31; j >=0; j--)
            if(((1 << j) & i) != 0)
                System.out.print("1");
            else
                System.out.print("0");
        System.out.println(); }
    static void pBinLong(String s, long l) {
        System.out.println(s + ", long: " + l + ", binary: ");
        System.out.print(" ");
        for(int i = 63; i >=0; i--)
            if(((1L << i) & l) != 0)
                System.out.print("1");
            else
                System.out.print("0");
        System.out.println();
    }
} ///:~

移位运算代码, 以及移位前后值的比较

package com.isflee.c03_1_8_ur_shift;

//: URShift.java
//移位运算，有符号数和无符号数的区别

public class URShift {


    static String toBinary( byte[] bytes )
    {
        StringBuilder sb = new StringBuilder(bytes.length * Byte.SIZE);
        for( int i = 0; i < Byte.SIZE * bytes.length; i++ )
            sb.append((bytes[i / Byte.SIZE] << i % Byte.SIZE & 0x80) == 0 ? '0' : '1');
        return sb.toString();
    }

    public static void main(String[] args) {
        int i = -1;
        //i的类型是int， 占32位(bit)
        System.out.println("{int i = num;} \n-移位前-> [num]真值".replace("num", i+""));
        System.out.println("-移位前-> ["+ pBinInt(i) +"]补");
        i >>>= 10;
        System.out.println("{int i = num;} \n-移位后-> [num]真值".replace("num", i+""));
        System.out.println("-移位后-> ["+ pBinInt(i) +"]补");
        System.out.println("");
        long l = -1;
        //l的类型是long， 占64位(bit)
        System.out.println("{long l = num;} \n-移位前-> [num]真值".replace("num", l+""));
        System.out.println("-移位前-> ["+ pBinLong(l) +"]补");
        l >>>= 10;
        System.out.println("{long l = num;} \n-移位后-> [num]真值".replace("num", l+""));
        System.out.println("-移位后-> ["+ pBinLong(l)+"]补");
        System.out.println("");
        short s = -1;
        //s的类型是short， 占16位(bit)
        //转成int的二进制->
        //[11111111111111111111111111111111]补
        //[00000000001111111111111111111111]补
        //截取后16位->
        //[1111111111111111]补 = [-1]真值
        System.out.println("{short s = num;} \n-移位前-> [num]真值".replace("num", s+""));
        System.out.println("-移位前-> ["+ pBinShort(s) +"]补");
        s >>>= 10;
        System.out.println("{short s = num;} \n-移位后-> [num]真值".replace("num", s+""));
        System.out.println("-移位后-> ["+ pBinShort(s) +"]补");
        System.out.println("");
        byte b = -1;
        //b的类型是byte，占8位(bit)
        System.out.println("{byte b = num;} \n-移位前-> [num]真值".replace("num", b+""));
        System.out.println("-移位前-> ["+ pBinByte(b) +"]补");
        b >>>= 10;
        System.out.println("{byte b = num;} \n-移位后-> [num]真值".replace("num", b+""));
        System.out.println("-移位后-> ["+ pBinByte(b) +"]补");

    }

    //以下4个方法改写自BitManipulation.java, 用于输出对应的二进制的值（补码）
    //print short
    static String pBinShort(short sVal) {
        StringBuilder result = new StringBuilder("");
        for(int i = 15; i >=0; i--)
            if(((1L << i) & sVal) != 0)
                result.append("1");
            else
                result.append("0");
        return result.toString();
    }
    //print byte
    static String pBinByte(byte bVal) {
        StringBuilder result = new StringBuilder("");
        for(int i = 7; i >=0; i--)
            if(((1L << i) & bVal) != 0)
                result.append("1");
            else
                result.append("0");
        return result.toString();
    }

    static String pBinInt(int i) {
        StringBuilder result = new StringBuilder("");
        for(int j = 31; j >=0; j--)
            if(((1 << j) & i) != 0)
                result.append("1");
            else
                result.append("0");
        return result.toString();
    }
    static String pBinLong(long l) {
        StringBuilder result = new StringBuilder("");
        for(int i = 63; i >=0; i--)
            if(((1L << i) & l) != 0)
                result.append("1");
            else
                result.append("0");
        return result.toString();
    }


} ///:~

运行结果:

{int i = -1;} 
-移位前-> [-1]真值
-移位前-> [11111111111111111111111111111111]补
{int i = 4194303;} 
-移位后-> [4194303]真值
-移位后-> [00000000001111111111111111111111]补

{long l = -1;} 
-移位前-> [-1]真值
-移位前-> [1111111111111111111111111111111111111111111111111111111111111111]补
{long l = 18014398509481983;} 
-移位后-> [18014398509481983]真值
-移位后-> [0000000000111111111111111111111111111111111111111111111111111111]补

{short s = -1;} 
-移位前-> [-1]真值
-移位前-> [1111111111111111]补
{short s = -1;} 
-移位后-> [-1]真值
-移位后-> [1111111111111111]补

{byte b = -1;} 
-移位前-> [-1]真值
-移位前-> [11111111]补
{byte b = -1;} 
-移位后-> [-1]真值
-移位后-> [11111111]补

在《java编程思想》中有关移位运算符有以下描述,

左移位运算符(<<)能将运算符左边的运算对象向左移动运算符右侧指定的位数(在低位补 0)。

“有符号”右移位运算符(>>)则将运算符左边的运算对象向右移动运算符右侧指定的位数。“有符号”右移位运算符使用了 “符号扩展”:若值为正，则在高位插入0;若值为负，则在高位插入1。

Java 也添加了一种“无符号”右移位运算符(>>>)，它使用了“零扩展”:无论正负，都在高位插入0。这一运算符是C 或C++没有的。

若对char，byte或者short进行移位处理，那么在移位进行之前，它们会自动转换成一个int。只有右侧的 5 个低位才会用到。这样可防止我们在一个 int 数里移动不切实际的位数。

若对一个 long 值进行处理，最后得到的结果也是long。此时只会用到右侧的6个低位，防止移动超过long值里现成的位数。

但在进行“无符号”右移位时，也可能遇到一个问题。若对 byte 或 short 值进行右移位运算，得到的可能不是正确的结果 (Java 1.0 和Java 1.1 特别突出)。它们会自动转换成int 类型，并进行右移位。但“零扩展”不会发生，所以在那些情况下会得到-1 的结果。

纵观整段文字, 其中提及了三个运算符, 左移位运算符(<<)、“有符号”右移位运算符(>>)、“无符号”右移位运算符(>>>). 至于为何只有这三个运算符, 我的理解是:

1.首先对于移位操作, 则可以分为左移和右移;

2.对于左移, 因为左移变化的是低位, 不会产生符号问题(补1还是补0), 所以对于左移运算就不需要考虑“有符号”还是“无符号”的问题, 因此只有 左移位运算符(<<);

3.对于右移, 因为右移变化的是高位, 而计算机用一个数的最高位存放符号, 右移操作时就会产生符号问题(补1还是补0), 所以对于右移操作, 首要考虑要操作的数是“有符号”还是“无符号”, 就有了 “有符号”右移位运算符(>>) 和 “无符号”右移位运算符(>>>)

此处将对这段话进行详细的拆分与理解,并举例说明:

1.左移位运算符(<<)能将运算符左边的运算对象向左移动运算符右侧指定的位数(在低位补 0)。

e.g
对于数据类型是int(32bit), 以1为例, 进行左移10位的操作.

int i = 1;
i << 10;

移位前, 1的补码和真值如下: 
[00000000000000000000000000000001]补 = [1]真值
左移10位后, 1的补码和真值如下:
[00000000000000000000010000000000]补 = [1024]真值

2.“有符号”右移位运算符(>>)则将运算符左边的运算对象向右移动运算符右侧指定的位数。“有符号”右移位运算符使用了 “符号扩展”:若值为正，则在高位插入0;若值为负，则在高位插入1。
e.g
对于数据类型是int(32bit), 以1073741824(等于2的30次方)和-1073741824(等于2的30次方的负数)为例, 进行 “有符号”右移 10位的操作.

以1073741824为例

int i = 1073741824;
i >> 10;

移位前, 1073741824的补码和真值如下: 
[01000000000000000000000000000000]补 = [1073741824]真值
右移10位后, 1073741824的补码和真值如下:
[00000000000100000000000000000000]补 = [1048576]真值

以-1073741824为例

int i = -1073741824;
i >> 10;

移位前, -1073741824的补码和真值如下: 
[11000000000000000000000000000000]补 = [-1073741824]真值
右移10位后, -1073741824的补码和真值如下:
[11111111111100000000000000000000]补 = [-1048576]真值

3.Java 也添加了一种“无符号”右移位运算符(>>>)，它使用了“零扩展”:无论正负，都在高位插入0。这一运算符是C 或C++没有的。

e.g
对于数据类型是int(32bit), 以1073741824(等于2的30次方)和-1073741824(等于2的30次方的负数)为例, 进行 “无符号”右移 10位的操作.

以1073741824为例

int i = 1073741824;
i >>> 10;

移位前, 1073741824的补码和真值如下: 
[01000000000000000000000000000000]补 = [1073741824]真值
右移10位后, 1073741824的补码和真值如下:
[00000000000100000000000000000000]补 = [1048576]真值

以-1073741824为例

int i = -1073741824;
i >>> 10;

移位前, -1073741824的补码和真值如下: 
[11000000000000000000000000000000]补 = [-1073741824]真值
右移10位后, -1073741824的补码和真值如下:
[00000000001100000000000000000000]补 = [3145728]真值

4.若对char，byte或者short进行移位处理，那么在移位进行之前，它们会自动转换成一个int。只有右侧的 5个低位才会用到。这样可防止我们在一个 int 数里移动不切实际的位数。

我的理解是对于char(16位), byte(8位), short(16位), 在移位之前, 自动转成int(32位)类型, 此时值的大小没发生变化, 相当于将他们扩展到int的位数, 再对这个int的二进制进行移位操作.

而“只有右侧的 5个低位才会用到。这样可防止我们在一个 int 数里移动不切实际的位数。”, 就比较难理解了. 首先我们要明确这两句话中讨论的是“移动的位数”, 整句话的理解就是, 针对这个“移动的位数”的二进制, 我们只会用到这个二进制数的右侧的5个低位, 比如我们想要右移33位(超过了int的位数(32位), 也就是在一个 int 数里移动不切实际的位数),
33就要先转化成二进制, 并截取右侧5个低位, 如下

[100001]补 = [33]真值,

取右侧5个低位,

[00001]补 = [1]真值,

最终, 在代码层面,

1 2	int i = -1073741824; i >> 33;

就相当于i被右移了1位

1 2	int i = -1073741824; i >> 1;

运算结果如下

1 2	{int i = -1073741824;} -移位前-> [01000000000000000000000000000000]补 {int i = -1073741824;} -移位后-> [00100000000000000000000000000000]补

而对于“移动的位数”先转换成二进制, 再截取这个二进制右侧的5位, 就等同于 (“移动的位数” 模 32), 转化为数学定义, 就是 33 mod 32 == 1; 从而解决了“在一个 int 数里移动不切实际的位数”的问题.

此处放上原文和我在stackoverflow找到的可以帮助理解的知识.

If you shift a char, byte, or short, it will be promoted to int before the shift takes place, and the result will be an int. Only the five low-order bits of the right-hand side will be used. This prevents you from shifting more than the number of bits in an int.

https://stackoverflow.com/questions/30116352/java-shift-operator-and-auto-promotion

5.若对一个 long 值进行处理，最后得到的结果也是long。此时只会用到右侧的6个低位，防止移动超过long值里现成的位数。

请参考第4点, 这是对long(64位)的特别说明, 若右移66位(移动超过long值里现成的位数), 这里的66位的二进制是

[1000010]补 = [66]真

用到右侧的6个低位, 结果是

[000010]补 = [2]真

或者我们直接对移动的位数模64, 66 mod 64 == 2, 来得出机器中实际移动的位数, 从而进一步得出结果.

在代码层面

1 2	long l = 9223372036854775807L; l >>= 66;

等同于

1 2	long l = 9223372036854775807L; l >>= 2;

运算结果如下

1
2

{long l = 9223372036854775807;} -移位前-> [0111111111111111111111111111111111111111111111111111111111111111]补
{long l = 2305843009213693951;} -移位后-> [0001111111111111111111111111111111111111111111111111111111111111]补

6.但在进行“无符号”右移位时，也可能遇到一个问题。若对 byte 或 short 值进行右移位运算，得到的可能不是正确的结果 (Java 1.0 和Java 1.1 特别突出)。它们会自动转换成int 类型，并进行右移位。但“零扩展”不会发生，所以在那些情况下会得到-1 的结果。

这里的翻译似乎有些问题, 并补对应我找到的原文.

There is a problem, however, with the unsigned right shift combined with assignment. If you use it with byte or short, you don’t get the correct results. Instead, these are promoted to int and right shifted, but then truncated as they are assigned back into their variables, so you get -1 in those cases.
此处谷歌翻译过来就是:
然而，无符号右移与赋值相结合存在一个问题。如果将它与 byte 或 short 一起使用，则不会得到正确的结果。相反，它们被提升为 int 并右移，但随后在它们被分配回它们的变量时被截断，所以在这些情况下你会得到 -1。
e.g
对于数据类型是byte(8位), 以-1为例, 进行“无符号”右移10位的操作.

byte b = -1;
b >>>= 10;

移位前, 1的补码和真值如下: 
[11111111]补 = [-1]真值
“无符号”右移10位后, -1的补码和真值如下:
[11111111]补 = [-1]真值

byte b = -1会扩展成int, 此时二进制为:

[11111111111111111111111111111111]补 = [-1]真

而“无符号”右移10位时, 需要对参数b的高10位进行操作(零扩展), 此时需要截取的参数b的低8位并不会受到任何任何影响, 这样看的话“零扩展”就显得没有必要了, 或者说“零扩展”不会发生, 结果仍然是-1.

同理, 对于数据类型是short(16位), 以-1位例, 同样进行“无符号”右移10位的操作. 在参数s被扩展成int之后, 右移的10位仍然不足以影响需要截取的低16位, 因此“零扩展”也不会发生

short s = -1;
s >>>= 10;

运算结果如下:
{short s = -1;} 
-移位前-> [-1]真值
-移位前-> [1111111111111111]补
{short s = -1;} 
-移位后-> [-1]真值
-移位后-> [1111111111111111]补

对于“不会得到正确的结果”的理解, 因为short/byte会被提升(扩展)成int, 移位后又进行截取变回short/byte, 此时就有了从高精度(int)到低精度(short/byte)的转换, 精度会损失, 得出不正确的结果.

如果想要以上例子的结果发生变化, 结合之前的理解,

对于byte类型,

需要移位24以上(即int的32位减去byte的8位得到我们要移动的位数需要超过高24位, 即位数 > 24 ), 代码如下:

byte b = -1;
b >>>= 25;

结果如下:
{byte b = -1;} 
-移位前-> [-1]真值
-移位前-> [11111111]补
{byte b = 127;} 
-移位后-> [127]真值
-移位后-> [01111111]补

同理, 对于short类型, 需要移动16位以上( 位数 > 16 ):

short s = -1;
s >>>= 17;

运算结果如下:
{short s = -1;} 
-移位前-> [-1]真值
-移位前-> [1111111111111111]补
{short s = 32767;} 
-移位后-> [32767]真值
-移位后-> [0111111111111111]补