位运算及其算法

计算机中的所有数在内存中都是以二进制形式进行存储的 ，位运算就是直接对整数二进制位进行操作，有些时候在程序中使用位运算进行操作，会得到极高的便利性。

有符号整数与无符号整数

我们以int整型为例，每个int占4个字节32个bit位。对于无符号整数，这32位的0、1都可以用来表示数字。而对于有符号整数，其最高位的bit位代表着整数的正负，0为正，1为负。因此有符号整型只有前31位可以用来表示数字，范围自然就小很多。

无符号整数可表示的范围（32位）：0~2的32次方-1（4,294,967,295）

有符号整数可表示的范围（32位）：-2的31次方~2的31次方-1（-2147483648~2147483647）

而我们的位运算，就是通过操作这些bit位来改变数字进而达到想要的效果。接下来我们来介绍一下位运算符号

&（按位与）：相同的bit位均为1才为1，否则均为0，比如0101&1100=0100

|（按位或）：只要有1就是1，只有均为0才是0，比如0101|1100=1101

^（按位异或）：相同为0，不同为1（无进位相加），比如0101^1100=0110

~(按位取反) ：把所有位的0变成1，1变成0，比如^(0101)=1010

<<(左移)：把所有bit位向左移动k位，高位丢弃，低位补0，比如011001<<2=100100

>>（右移）：把所有bit位向右移动k位，若无符号数字，高位补0，有符号数字，高位补1.

（对于正数高位都补0，负数高位都补1）

（十进制）负数的二进制存储（补码）

首先我们要找到其正数的二进制表示（给出-5我们先找到5的二进制表示）然后把正数的二进制取反+1即可。此时得到的是补码，换成原码就是把补码-1再取反。（符号位不变）

正数变成负数（a->-a)：把正数的二进制按位取反+1。

负数变成正数(-a->a)：把负数的二进制（补码）按位取反再+1。

注，以上经过位运算后得到的都是补码，需要我们转换才能变成原码。 

二进制的运算

在进行二进制的运算时，会有原码和补码的概念，而计算机在计算时都是使用补码运算，存储数据时也是用补码保存的。正数的补码是其二进制本身，负数的补码是其原码二进制按位取反+1（符号位不变）。我们平常用二进制表示的数字都是原码，运算时才用补码。

对于负数的位运算，它们的操作都是建立在补码上，得到的运算结果是补码，最后将补码结果转化成一个普通的十进制数（先补码转换成原码然后换成十进制）结果。

（用位运算符进行操作的对象也是补码）

关于按位取反的运算转换成十进制的过程（补码）

如果是正数，首先所有位按位取反，得到一个负数的二进制（补码），然后把该二进制的符号位不变，其他再按位取反再+1即可得到该负数的原码。如果是负数，先将负数用二进制表示然后按位取反得到补码后再转换成原码。

以上这些知识我们来总结一下就是：我们只需要知道，运算的时候都是拿补码进行位运算，负数的原码是如何转换成补码的，负数的二进制补码如何转换，负数的二进制如何表示成十进制整数。用二进制表示整数都是用原码表示。

关于位运算符的优先级

这里建议直接用括号

关于位运算的一些基础操作

首先，我们要把32位编号，从低到高开始从第0位计数，一直到31位。

1.给一个数n确定它的第x位是0还是1

(n>>x)&1==0?0:1

2.将一个数n的第x位改成1

先将1<<x，然后n|=（1<<x)即可

3.第x位改成0

把1<<x,然后按位取反，然后&n，即n&=(~(1<<x))

4.提取一个数中最右侧的1（经过操作后只有该位是1其余全变成0）lowbit

操作：n&（-n）（-n按位取反+1，是补码因此可以运算）

5.除去最右侧的1

n&（n-1）

^的运算律

a^0=a;

a^a=0;

a^b^c=a^(b^c)