位运算及原码、反码、补码

程序中的所有数在计算机内存中都是以二进制的形式储存的，位运算就是直接对整数在内存中的二进制位进行操作。

位运算是更底层一些的操作，位运算通常相比其他运算有着更高的效率。

运算符号

含义	C\C++	Java
按位与（AND）	a & b	a & b
按位或（OR）	a | b	a | b
按位异或（XOR）	a ^ b	a ^ b
按位取反（NOT）	~ a	~ a
左移	a << b	a << b
右移	a >> b	a >> b
无符号右移	无	a >>> b

按位与（AND）

按位与处理两个长度相同的二进制数，两个相应的二进位都为1，该位的结果值才为1，否则为0。例如：

    0101（十进制5）
AND 0011（十进制3）
  = 0001（十进制1）

按位或（OR）

按位或处理两个长度相同的二进制数，两个相应的二进位中只要有一个为1，该位的结果值为1。例如：

   0101（十进制5）
OR 0011（十进制3）
 = 0111（十进制7）

按位异或（XOR）

按位异或运算，对等长二进制模式按位或二进制数的每一位执行逻辑按位异或操作。
操作的结果是如果某位不同则该位为1，否则该位为0。例如：

    0101（十进制5）
XOR 0011（十进制3）
  = 0110（十进制6）

按位取反（NOT）

取反是一元运算符，对一个二进制数的每一位执行逻辑反操作。使数字1成为0，0成为1。例如：

NOT 0111（十进制7）
  = 1000（十进制8）

左移

左操作数按位左移右操作数指定的位数，移位后空缺的部分全部填0。

    0001（十进制1）
<<     3（左移3位）
  = 1000（十进制8）

右移

左操作数按位右移右操作数指定的位数，左边的用原有标志位补充，右边超出的部分舍弃。

     1010（十进制10）
>>      2（右移2位）
   = 0010（十进制2）

无符号右移

相比 C、C++、JAVA中有一个特有的无符号右移操作符“>>>”，此操作将忽略操作数的符号 同样的还有>>>=。

按位右移补零操作符。左操作数的值按右操作数指定的位数右移，左边部分总是以0填充，右边超出的部分舍弃。

int a = -8;
int b = a >> 3;
int c = a >>> 3;

结果：
a -8         11111111111111111111111111111000
b -1         11111111111111111111111111111111
c 536870911     11111111111111111111111111111

小结

计算机中所有数都是以补码形式存储的（正数的补码是本身）。

原码：10进制转换成2进制是原码

反码： 正数的反码是本身，负数的反码是负数的原码0变为1,1变为0 （负数求反码时候的符号位不参与变换）

补码： 正数的补码是本身，负数的补码就是负数的反码加一

总结： 正数的原码，反码 ，补码三值合一， 负数的原码，反码，补码不同。

补码的意义：

• 使符号位能与有效值部分一起参与运算，从而简化运算规则
• 使减法运算转换为加法运算，进一步简化计算机中运算器的线路设计。

-8
原码 1000 0000 0000 0000 0000 0000 0000 1000
​反码 1111 1111 1111 1111 1111 1111 1111 0111
补码 1111 1111 1111 1111 1111 1111 1111 1000

带符号右移（左边的用原有标志位补充，右边超出的部分舍弃），即

1111 1111 1111 1111 1111 1111 1111 1000 变成：
1111 1111 1111 1111 1111 1111 1111 1111

补码 1111 1111 1111 1111 1111 1111 1111 1111
反码 1111 1111 1111 1111 1111 1111 1111 1110
原码 1000 0000 0000 0000 0000 0000 0000 0001 转化为十进制也就是 -1

无符号右移（左边部分总是以0填充，右边超出的部分舍弃），即

1111 1111 1111 1111 1111 1111 1111 1000 变成：
0001 1111 1111 1111 1111 1111 1111 1111

补码 0001 1111 1111 1111 1111 1111 1111 1111 （正数的原码，反码 ，补码三值合一）
反码 0001 1111 1111 1111 1111 1111 1111 1111 （正数的原码，反码 ，补码三值合一）
原码 0001 1111 1111 1111 1111 1111 1111 1111 转化为十进制也就是 53687091

位运算应用

很多源码中有关于使用位运算的优化。但一般的业务场景不建议使用这些优化，因为大多数编译器会帮我们优化代码。还有就是这样代码的可读性也会大大降低。我们更应该关注的是整体算法的效率，把一个时间复杂度为 O(n^2) 的代码优化到 O(n*logn) 的意义会更大。

乘法

a << n 等价于 a * pow(2, n)

除法

a >> n 等价于 a / pow(2, n)

取余

等价于 a & (pow(2, n) - 1) 等价于 a % pow(2, n)

交换两个数

a ^= b 
b ^= a 
a ^= b

等价于

a += b
b = a - b
a = a - b

等价于

temp = a
a = b
b = temp

绝对值

int a = -100;
int sign = a >> 31;
int b = (a + sign) ^ sign

等价于

int a = -100;
int b = Math.abs(a);

判断奇偶性

(a & 1) == 0 等价于 a % 2 != 0

判断大小

public static boolean less(long n1, long n2) {
    n2 = ~(n2 - 1);
    return (n1 & n2) == 0;
}

等价于

n1 < n2

bit状态位

在一个系统中，用户一般有查询(Select)、新增(Insert)、修改(Update)、删除(Selete)四种权限，四种权限有多种组合方式，也就是有16中不同的权限状态（2的4次方）。每一位代表一个状态是true还是false。

public class NewPermission {
    // 是否允许查询，二进制第1位，0表示否，1表示是
    public static final int ALLOW_SELECT = 1 << 0; // 0001
    
    // 是否允许新增，二进制第2位，0表示否，1表示是
    public static final int ALLOW_INSERT = 1 << 1; // 0010
    
    // 是否允许修改，二进制第3位，0表示否，1表示是
    public static final int ALLOW_UPDATE = 1 << 2; // 0100
    
    // 是否允许删除，二进制第4位，0表示否，1表示是
    public static final int ALLOW_DELETE = 1 << 3; // 1000
    
    // 存储目前的权限状态
    private int flag;
 
    /**
	 *  重新设置权限
	 */
    public void setPermission(int permission) {
        flag = permission;
    }
 
    /**
	 *  添加一项或多项权限
	 */
    public void enable(int permission) {
        flag |= permission;
    }
    
    /**
	 *  删除一项或多项权限
	 */
    public void disable(int permission) {
        flag &= ~permission;
    }
    
    /**
	 *  是否拥某些权限
	 */
    public boolean isAllow(int permission) {
        return (flag & permission) == permission;
    }
    
    /**
	 *  是否禁用了某些权限
	 */
    public boolean isNotAllow(int permission) {
        return (flag & permission) == 0;
    }
    
    /**
	 *  是否仅仅拥有某些权限
	 */
    public boolean isOnlyAllow(int permission) {
        return flag == permission;
    }
}

位计数

基于bit状态位，某个状态数里面，有多少个状态是true，就是计算这个状态数里面多少位是1。

比较朴素的方法就是：先判断n的奇偶性，为奇数时计数器增加1，然后将n右移一位，重复上面的步骤，直到移位完毕。

int n = Integer.MAX_VALUE;
int count = 0;
while(n!=0) {
    if((n & 1) == 1){
        count++;
    }
    n= n>>1;
}

高效一点的方法通过：

1. n & (n - 1)可以移除最后一位1 （假设最后一位本来是0， 减一后必为1，0 & 1为 0， 最后一位本来是1，减一后必为0，0 & 1为 0）
2. 移除了最后一位1之后，计数加1，如果结果不为零，则用结果继续第一步。

int n = Integer.MAX_VALUE;
int count = 0;
while(n != 0) {
    n &= n - 1;
    count++;
}

更高效的方法：

n = n - ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
n = (n + (n >> 4)) & 0x0F0F0F0F;
n = n + (n >> 8);
n = n + (n >> 16);
count = n & 0x0000003F;

将一个数向上取整为2的幂

HashMap 中的源码：

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

扰动函数

HashMap 中的源码：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

参考：HashMap这次是真的懂了，扰动函数、负载因子、扩容拆分全搞定

为什么1字节表示的范围是[-128,127]

一个字节8位，即可表示2^8 =256，有符号数那就可以表示2^7 =128个正数、2^7 =128个负数了，但是1000 0000和0000 0000其实都是0,所以理论上它只能表示[-127, 127]。
如果计算机用原码或者反码，会多占用一个表达（+0、-0都会有各自的原码和反码）。但计算机中使用的是补码，+0、和-0的补码都是0000 0000,所以1000 0000可以用来多表达一个数，用来表示-128最合理。
还可以从另外一个角度来理解： -127 的补码是1000 0001.再减去1 就是1000 0000 。那-127-1=-128。
总结：补码不仅解决了符号的表示的问题，还统一了符号位和数值位，使得符号位可以和数值位一起直接参与运算。