Java 位运算

位运算

1、原码, 反码, 补码

对于一个数，计算机要使用一定地编码方式进行存储，原码、反码、补码是机器存储一个具体数字的编码方式。

原码，反码，补码的产生过程，就是为了解决，计算机做减法和引入符号位（正号和负号）的问题。

1.1 机器数

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

比如，十进制中的数 +3 ，计算机字长为 8 位，转换成二进制就是 00000011。如果是 -3 ，就是 10000011 。

那么，这里的 00000011 和 10000011 就是机器数。

1.2 真值

因为第一位是符号位，所以机器数的形式值就不等于真正的数值。例如上面的有符号数 10000011，其最高位 1 代表负，其真正数值是 -3 而不是形式值 131（10000011 转换成十进制等于 131）。

所以，为区别起见，将带符号位的机器数对应的真正数值称为机器数的真值。

例：0000 0001 的真值 = +000 0001 = +1，1000 0001 的真值 = –000 0001 = –1

1.3 原码

原码是人脑最容易理解和计算的表示方式。

原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值.
比如如果是 8 位二进制:

[+1]原 = 0000 0001
[-1]原 = 1000 0001

因为第一位是符号位，所以 8 位二进制的取值范围是：
[1111 1111 , 0111 1111] 即 [-127 , 127]

1.4 反码

反码的表示方法是:

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

示例：

[+1] = [00000001]原 = [00000001]反
[-1] = [10000001]原 = [11111110]反

如果一个反码表示的是负数, 人脑无法直观的看出来它的数值. 通常要将其转换成原码再计算.

1.5 补码

补码的表示方法是:

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

负数补码的另一种算法：

负数的补码等于他的原码自低位向高位，尾数的第一个‘1’及其右边的‘0’保持不变，左边的各位按位取反，符号位不变。

示例：

[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补

对于负数, 补码表示方式也是人脑无法直观看出其数值的. 通常也需要转换成原码在计算其数值。

1.6 负数

现在我们知道了计算机可以有三种编码方式表示一个数. 对于正数因为三种编码方式的结果都相同:

[+1] = [00000001]原 = [00000001]反 = [00000001]补

所以不需要过多解释. 但是对于负数:

[-1] = [10000001]原 = [11111110]反 = [11111111]补

1.7 参考及详解传送门：

2、位运算

位运算主要包括按位与(&)、按位或(|)、按位异或(^)、取反()、左移(<<)、右移(>>)这几种。
其中除了取反()以外，其他的都是二目运算符，即要求运算符左右两侧均有一个运算量。

2.1 按位与(&)

参加运算的两个数，换算为二进制后，进行与（&）运算。只有当相应位上的数都是 1 时，该位才取 1，否则该为为 0。

运算规则：两位同时为“1”，结果才为“1”，否则为 0

0&0=0;
0&1=0;
1&0=0;
1&1=1;

示例：
3&5 即 0000 0011& 0000 0101 = 00000001 因此，3&5的&运算值为1。

另，负数按补码形式参加按位或运算。

与(&)运算的用途

清零。如果想将一个单元清零，即使其全部二进制位为 0，只要与一个各位都为零的数值相与，结果为零。
取一个数中指定位。（00001111 即取一个数的低四位）

2.2 按位或(|)

参加运算的两个数，换算为二进制后，进行或（|）运算。只要相应位上存在 1，那么该位就取 1，均不为 1，即为 0。

运算规则：参加运算的两个对象只要有一个为 1，其值为 1。

0|0=0；
0|1=1；
1|0=1；
1|1=1；

示例：
3|5　即 00000011 | 0000 0101 = 00000111 因此，3|5的|运算的值为7。

另，负数按补码形式参加按位或运算。

或(|)运算的用途

常用来对一个数据的某些位置置为 1。
例：将X=10100000的低4位置1 ，用X | 0000 1111 = 1010 1111即可得到。

2.3 按位异或(^)

参加运算的两个数，换算为二进制后，进行异或运算。只有当相应位上的数字不相同时，该为才取 1，若相同，即为 0。

运算规则：参加运算的两个对象，如果两个相应位为“异”（值不同），则该位结果为 1，否则为 0。

0^0=0；
0^1=1；
1^0=1；
1^1=0；

示例：
10 ^ -10 即 0000 1010 ^ 1111 0110 = 1111 1100

异或(^)的用途

异或其实就是不进位加法,如 1+1=0 ,0+0=0 , 1+0=1。

使特定位翻转找一个数，对应 X 要翻转的各位，该数的对应位为 1，其余位为零，此数与 X 对应位异或即可。
例：X=10101110，使 X 低 4 位翻转，用 X ^0000 1111 = 1010 0001 即可得到。
与 0 相异或，保留原值，X ^ 00000000 = 1010 1110。

2.4 取反(~)

参加运算的两个数，换算为二进制后，进行取反运算。每个位上都取相反值，1 变成 0，0 变成 1。

运算规则：单目运算符，1 变 0，0 变 1。

~0=1;
~1=0;

2.5 左移(<<)

参加运算的两个数，换算为二进制后，进行左移运算，用来将一个数各二进制位全部向左移动若干位。

运算规则：将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补 0）。

0000 1010<<2 = 0010 1000

若左移时舍弃的高位不包含 1，则每左移一位，相当于该数乘以 2。

2.6 右移(>>)

参加运算的两个数，换算为二进制后，进行右移运算，用来将一个数各二进制位全部向右移动若干位。

运算规则：将一个数的各二进制位全部右移若干位，正数左补 0，负数左补 1，右边丢弃。

0000 1010>>2 = 0000 0010

操作数每右移一位，相当于该数除以 2。

2.7 参考及详解传送门：

3、Java 中的位运算

以下内容转自：https://www.jianshu.com/p/416dd46dea7b

Java 中的位运算共有与(&)、或(|)、非(~)、异或(^)、左移(<<)、右移(>>)、无符号右移(>>>) 这 7 种，概览见下表：

3.1Java 位运算基础操作

a|0 == a;
a&-1 == a;
a&0 == 0;

a^a == 0;
a^0 == a;

a|~a == -1;
a&~a == 0;
a&a == a;
a|a == a;

a|(a&b) == a;
a&(a|b) == a;

3.2 位运算进阶操作

a. 判断奇偶

可以很简单归纳出，只需判断一个正整数的二进制补码最后一位是 0 是 1，是 0 为偶数，是 1 为奇数

public void isOddOrEven(int n){
        if ((n & 1) == 1) {//n是奇数
            System.out.println("Odd");
        }else {//n是偶数
            System.out.println("Even");
        }
    }

b. 省去中间变量交换两整数的值（面试常考）

public void swap(){
        int a = 1, b = 2;
        a ^= b;
        b ^= a;//b == 1
        a ^= b;//a == 2
        System.out.println("a:" + a);//a:2
        System.out.println("b:" + b);//b:1
    }

这里还有另一种做法，今早上跟舍友讨论了一下：

a = 1,b = 2;
若要让ab俩值交换，则先让a=a+b, 然后 b=a,然后a = a-b;
感觉和位运算差不多的。

c. 变换符号，正变负，负变正

只需对待操作数应用取反操作后再加 1 即可

public void negate(){
        int a = -10, b = 10;
        System.out.println(~a + 1);//10
        System.out.println(~b + 1);//-10
    }

d. 求绝对值，

对于负数可以通过上面变换符号的操作得到绝对值，
正数直接返回即可，因此我们要先判断符号位来得知当前数的正负。

public int abs(int a){
        int i = a >> 31;//得到符号位，0 为正数，-1 为负数
        return i == 0 ? a : (~a + 1);//符号位为 0 直接返回，否则返回 ~a + 1
    }

或者，n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31 等于-1。若 n 为正数 n^0-0 数不变，若 n 为负数 n^-1 需要计算 n 和-1 的补码，异或后再取补码，结果 n 变号并且绝对值减 1，再减去-1 就是绝对值

public int abs(int a){
        return a ^ (a >> 31)) - (a >> 31);
    }

e. 判断一个数 num 是不是 2 的幂

如果是 2 的幂，n 一定是 10000...（也就是二进制位里只有一个是 1，且是首位，其余全是 0），n-1 就是 0111111... 所以做与运算结果为 0。

    public static boolean judgeNum(int num){
        if (num < 1)
            return false;
        return (num & (num - 1)) == 0;
    }

f. 判断一个数 num 是不是 4 的幂

理论上数字 4 幂的二进制类似于 100，10000，1000000，... 这些形式。
不难归纳出如下结论：
4 的幂一定是 2 的。
4 的幂和 2 的幂一样，二进制位里只有一个是 1，且是首位。但是，4 的幂中的 1 总是出现在奇数位。
这里贴下 Kotlin 代码（非最佳实现）：

    public static boolean judgeNum(int num){
        if (num < 1)
            return false;
        return (num & (num - 1)) == 0 && (Integer.toBinaryString(num).length() & 1) == 1;
    }

g. 其他进阶操作

// 7. int 型最大值是什么?
System.out.println((1 << 31) - 1);// 2147483647， 注意运算符优先级，括号不可省略
System.out.println(~(1 << 31));// 2147483647

// 8. int 型最小值是什么？
System.out.println(1 << 31);
System.out.println(1 << -1);

// 9. long 型最大值是什么？
System.out.println(((long)1 << 127) - 1);

// 10. 整数n乘以2是多少？
n << 1;

// 11. 整数n除以2是多少？(负奇数的运算不可用)
n >> 1;

// 12. 乘以2的n次方，例如计算10 * 8(8是2的3次方)
System.out.println(10<<3);

// 13. 除以2的n次方，例如计算16 / 8(8是2的3次方)
System.out.println(16>>3);

// 14. 取两个数的最大值（某些机器上，效率比a>b ? a:b高）
System.out.println(b&((a-b)>>31) | a&(~(a-b)>>31));

// 15. 取两个数的最小值（某些机器上，效率比a>b ? b:a高）
System.out.println(a&((a-b)>>31) | b&(~(a-b)>>31));

// 16. 判断符号是否相同(true 表示 x和y有相同的符号， false表示x，y有相反的符号。)
System.out.println((a ^ b) > 0);

// 17. 计算2的n次方 n > 0
System.out.println(2<<(n-1));

// 18. 求两个整数的平均值
System.out.println((a+b) >> 1);

// 19. 从低位到高位,取n的第m位
int m = 2;
System.out.println((n >> (m-1)) & 1);

// 20. 从低位到高位.将n的第m位置为1，将1左移m-1位找到第m位，
//得000...1...000，n 再和这个数做或运算
System.out.println(n | (1<<(m-1)));

// 21. 从低位到高位,将n的第m位置为0，将1左移m-1位找到第m位，
//取反后变成111...0...1111，n再和这个数做与运算
System.out.println(n & ~(0<<(m-1)));

//22.取模的操作 a % (2^n) 等价于 a&(2^n-1),后者效率更高一点
System.out.println("the 345 % 16 is "+(345%16)+ " or "+(345&(16-1)));

3.3 位运算的应用

位运算作为底层的基本运算操作，往往是和'高效'二字沾边，适当的运用位运算来优化系统的核心代码，会让你的代码变得十分的精妙。

位运算常用来用作标志位：如 1100 ，四位可表示四种标志，1 为 true，0 为 false。
下面用一个例子来演示一下。

位运算