位操作

引言：

犹如噩梦一般的移位，带符号右移，无符号右移等
并，或，异或，非等操作
大学也学过位操作，哎，可是那时候没认真听讲，说实话，位操作我也会，但是在代码里我不知道它的作用是啥。位操作，难倒是不难，很容易理解和单独的写出一个二进制数的位操作结果，可是，要是在代码中实际运用就不行了。这篇笔记，记录一下位操作的概念，以及在代码中的用途。
强调一点：计算机中的正数（不管正负）存的都是补码。
最后，我是真的想说一句：当年欠下的债，总有一天要还的。

引用一段leetcode上对位操作的说明：

位操作（Bit Manipulation）是程序设计中对位模式或二进制数的一元和二元操作。在许多古老的未处理器上，位运算比加减运算略快，通常位运算比乘除运算要快很多。在现在架构中，情况并非如此：位运算的速度通常与加减法运算相同（但是仍然快于乘除运算）。

位操作有哪些：

按位与（AND）
按位或（OR）
按位异或（XOR）
取反（NOT）
移位：这也是位操作中最难的一个操作。移位是一个二元运算符，用来将一个二进制数中的每一位全部都向一个方向移动指定位，溢出的部分将被舍弃，而空缺的部分填入一定的值。
移位又可以分为两个小类：算术移位、逻辑移位。
对二进制数进行位操作的时候，可以将0看成false，1看成true。

二进制的符号位：

大学期间学的二进制数里有一个概念——最高位表示符号位，但是什么时候最高位表示符号位呢？什么时候又不表示呢？这个问题在大学期间折磨过我，我那时候就光想，也不去解决，然后今天又遇到了，哎，还真是欠下的债，总是要还的。
现在捋一捋什么时候最高位表示符号位，什么时候最高位又不表示符号位。其实很简单的，题目有说明那么自然最高位表示符号位，题目没有说明，那么都按照没有符号的二进制数处理。就比如上面举的两个移位例子，一个右移（>>>），一个带符号右移（>>），两个操作符是不一样的。

比如：
10000010 如果最高位不表示符号位，那么这个二进制数表示：130，如果最高位表示符号位那么这个数就是：-2。但是什么时候是这个二进制数最高位表示符号位什么时候不表示符号位呢？如果题目有说明最高位表示符号位的话，那么这个数就是-2。没说明的话就是130。在程序中对该二进制操作的时候什么时候表示带符号，什么时候表示不带符号呢？如果用>>符号进行右移位，那么最高位表示是符号位。如果是>>>右移，默认最高位不是符号位。

按位与（AND）

              010101
    AND  101001
  结果： 000001

按位或（OR）

              010101
    OR    101001
  结果： 111101

按位异或（XOR）

              010101
    XOR   101001
  结果：  111100

个人觉得异或比较拗口，其实是因为我们的高级语言，比如java，用的通常都是与，或，和非，异或基本没有用到。
异或表示对应位的两个操作数不一致，那么返回true，一致的都返回false。
比如，0和0，1和1一致的都返回false。1和0，0和1两个不一样的，返回true。

按位非（NOT）

              010101
    NOT  
  结果：  101010

移位

（1）左移位

重点：

左移位没有无符号左移，只有带符号左移。也就是只有<< 运算符。
不存在 <<< 这个符号，所以带符号左移也叫做左移
如果移动的位数超过了该类型的最大位数，那么编译器会对移动的位数取模。如对int型移动33位，实际上只移动了33%32=1，所以只需往左移动1位。

先用例子说话：

    eg：3 << 2（int 类型的）

首先在做这个题目之前，我们得能读懂题目，简单的翻译一下，将3（二进制的3）向左移动2位。
然后括号里说明了是int类型的。这句话有啥用？我们先来看看，3在二进制里的表示是多少，是 11 。如果这时候我们将11左移两位那成啥了？00？（这里再强调一下，溢出的部分是被舍弃的。）所以这里的int类型是间接的定义了二进制数的位数。int类型通常来说是占四个字节，一个字节占8个比特位（比特位就是位数，一个二进制数的一位），所以这里的3用二进制表示，并非是11,而是
0000 0000 0000 0000 0000 0000 0000 0011 得需要32位
这时向左移动两位之后的结果是：
0000 0000 0000 0000 0000 0000 0000 1100 换成10进制数表示是12。

贴上代码运行结果，更有说服力一点：

左移位的数学意义：

左移一位，相当于把当前的数扩大了2^1倍。
同理得出，左移n为，相当于当前数扩大了2^n倍。

（2）右移位

（2.1）无符号右移

（2.1.1）正数

    eg：3 >>> 2（int 类型的）

这里就不再解释这个题目的含义了。
原先表示为：0000 0000 0000 0000 0000 0000 0000 0011
向右移2位之后：0000 0000 0000 0000 0000 0000 0000 0000
所以最后的答案是 0。
贴上代码运行结果，更有说服力一点：

数学意义：

右移之后的值为当前数值除以/2^nn表示右移位数。

（2.1.2）负数

将最高位的符号位一起向右移动，溢出部分舍去，左边空出的最高位补0。

例子说明：

    eg：-1 >>> 2（int 类型的）

-1在计算机中存储的二进制补码是：1111 1111 1111 1111 1111 1111 1111 1111
无符号右移两位之后是：0011 1111 1111 1111 1111 1111 1111 1111

将无符号右移之后的二进制表示为十进制：

二进制转十进制根据除二取余的方法，然后再根据等比数列前n项和公式：

可以很快的算出上面这个答案为：2^30 - 1

程序算出的结果为：

pic-1596417625757.png

再来看下，这个结果和刚刚算出的2^30 - 1的比值是否为1

pic-1596417625758.png

很显然，结果是正确的。

（2.2）带符号右移

（2.2.1）正数

和无符号右移一样。

数学意义：

右移之后的值为当前数值除以/2^nn表示右移位数。

pic-1596417625759.png

（2.2.2）负数

带符号右移，将最高位的符号位一起向右移动，溢出部分舍去。左边空出的最高位那边补1（符号位）

例子说明：

    eg：-1 >> 2（int 类型的）

-1在计算机中存储的二进制补码是：1111 1111 1111 1111 1111 1111 1111 1111
无符号右移两位之后是：1111 1111 1111 1111 1111 1111 1111 1111

不要觉得两个32位二进制是一样的，然后觉得没有变化，其实是有进行移除2位，然后在左边最高位补1的。

向右移动两位之后的二进制对应的十进制是 -1；

将一个负数的补码转成十进制数的公式：

将补码减去1；
然后除了最高位符号位外，取反。
再最后将得到的二进制数转成10进制，注意，最高位是符号位。

数学意义：

右移之后的值为当前数值除以/2^n 再加上 -1n表示右移位数。

参考文献

java中右移运算符>>和无符号右移运算符>>>的区别