位运算

万字详解位运算
常用的位操作【labuladong】

1、使用 x & 1 == 1 判断奇偶数。（注意，一些编辑器底层会把用%判断奇偶数的代码，自动优化成位运算）

2、不使用第三个数，交换两个数。x = x ^ y ， y = x ^ y ， x = x ^ y。

3、两个相同的数异或的结果是 0，一个数和 0 异或的结果是它本身。（对于找数这块，异或往往有一些别样的用处。）

4、x & (x - 1) ，可以将最右边的 1 设置为 0。（这个技巧可以用来检测 2的幂，或者检测一个整数二进制中 1 的个数，又或者别人问你一个数变成另一个数其中改变了多少个bit位，统统都是它）

5、异或可以被当做无进位加法使用，与操作可以用来获取进位。

6、i+(~i)=-1，i 取反再与 i 相加，相当于把所有二进制位设为1，其十进制结果为-1。

7、对于int32而言，使用 n >> 31取得 n 的正负号。并且可以通过 (n ^ (n >> 31)) - (n >> 31) 来得到绝对值。（n为正，n >> 31 的所有位等于0。若n为负数，n >> 31 的所有位等于1，其值等于-1）

8、使用 (x ^ y) >= 0 来判断符号是否相同。（如果两个数都是正数,则二进制的第一位均为0,xy=0；如果两个数都是负数,则二进制的第一位均为1；xy=0 如果两个数符号相反,则二进制的第一位相反,xy=1。有0的情况例外，相同得0，不同得1）
—————————————————-

左移<<

a << n = a * 2^n，左移n位 就是扩大2^n倍

左移不分正负数，低位补0

**正数**：r = 20 << 2
   20的二进制原码：0001 0100
　　
　　20的二进制补码：0001 0100
　　向左移动两位后： 0101 0000
　　　　     结果： r = 80
**负数**：r = -20 << 2
　　-20 的二进制原码 ：1001 0100 （二进制**负**数，最高位为1）
　　-20 的二进制反码 ：1110 1011 （反码：最高位符号位不变，其余位1变0、0变1）
　　-20 的二进制补码 ：1110 1100 （补码：反码+1）
　　左移两位后的补码：1011 0000
　　　　　　　　反码：1010 1111
　　　　　　　　原码：1101 0000
　　　　　　　　结果：r = -80

右移 >>

a >> n = a / 2^n， 右移n位就是缩小2^n倍

如果该数为正，则高位补0，若为负数，则高位补1

正数：r = 20 >> 2

　　20的二进制补码：0001 0100

　　向右移动两位后：0000 0101

　　　　　　　结果：r = 5

负数：r = -20 >> 2

　　-20 的二进制原码 ：1001 0100

　　-20 的二进制反码 ：1110 1011

　　-20 的二进制补码 ：1110 1100 

　　右移两位后的补码：1111 1011 

　　　　　　　　反码：1111 1010

　　　　　　　　原码：1000 0101

　　　　　　　　结果：r = -5

无符号右移 >>>

无符号右移，也叫逻辑右移

即 若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0

正数：　r = 20 >>> 2

　　　　的结果与 r = 20 >> 2 相同；

负数：　r = -20 >>> 2

注：以下数据类型默认为int 32位

　 -20:原码：10000000  00000000   00000000   00010100

　　　　反码：11111111  11111111   11111111   11101011

　　　　补码：11111111  11111111   11111111   11101100

　　　　右移：00111111  11111111   11111111   11111011

　　　　结果：r = 1073741819

^ 异或

相同为0，不同为1

异或，也被称为 不进位加法 即： 1 ^ 1 = 0 1 ^ 0 = 1 0 ^ 0 = 0

1. 一个值与自身的运算，总是为 false。

x ^ x = 0

1. 一个值与 0 的运算，总是等于其本身。

   x ^ 0 = x
   

2. 可交换性

   x ^ y = y ^ x

3. 结合性

     x ^ (y ^ z) = (x ^ y) ^ z