java 位运算与实战

java 位运算与实战

标签（空格分隔）： java

1. 介绍

位运算 -- 有符号位移运算符(>>,<<)

在二进制里面总共有32位，0-31，第31位是表示当前数值的正负，当时0的时候表示这个数值是正数，当是1表示这个数值是负数。

int类型占4个字节(byte);一个字节=8bit(位);一个int类型的数值占32bit(位)int i = 123; 10进制123转为二进制后等于:1111011 完整补位后:00000000 00000000 00000000 01111011

正数左移(<<)

以2<<2为例: 2：00000000 00000000 00000000 00000010 向左移动两位，右侧会空出来两个位置，两个位置用0补位得到的结果如下： 8：00000000 00000000 00000000 00001000 转换成十进制对应的数值为8。因此可以得到2<<2的结果是8。

负数左移(<<)

以-2<<2为例: -2：11111111 11111111 11111111 11111110 向左移动两位，右侧空出的两个位置用0补位，到这里还没有结束，要是想计算出它的值，还要做补位，那就是将当前移位得到的结果(11111111 11111111 11111111 11111000)减一后再取反码，得的结果就是补码的结果。 减一操作： 11111111 11111111 11111111 11110111 取反码的结果： 00000000 00000000 00000000 00001000 这个对应的值是8，因为是负值，那么得到的结果就是-8，因此-2<<2的结果是-8。 左移总结 这里可以看出来，在左移的时候，不论这个目标值(2或-2)是正数还是负数，结果都符合一个规律，即表达式：mx2^n。m表示目标值，n表示的是移位的位数。 -2<<2 = -8，2<<2 = 8，同理可以得到2<<4 = 2x2^4 = 32,-2<<4 = -2x2^4 = -32。

正数右移(>>)

以10>>2为例: 10：00000000 00000000 00000000 00001010 右移两位，右侧的10就会被舍弃，左侧会空出两个空位，空位用符号位补齐，前面说过正数的符号位是0，也就是用0补齐，得到的结果如下： 2：00000000 00000000 00000000 00000010 得到的十进制结果是2，结论就是10>>2=2。

负数右移(>>)

以-10>>2为例: -10：11111111 11111111 11111111 11110110 同样是右移，溢出的部分舍弃，空位的部分用符号位补齐，得到的结果如下： 11111111 11111111 11111111 11111101 减一操作后结果： 11111111 11111111 11111111 11111100 取反码后的结果： 00000000 00000000 00000000 00000011 对应的十进制结果是3，因为是负数，那么结果就是-3。结论是-10>>2。 有符号位移总结 整体的总结来看，正数的左移和右移没有什么问题，但是负数存在一个补码的问题，比较麻烦。补码记住一个口诀就可以，移位、减一、取反码，得到正数结果加个负号。这样就可以得到正确结果。

位运算 -- 无符号位移运算符(>>>)

Java中没有无符号左移的说法，这里只说右移。同样也是分正数和负数来讲。 正数右移(>>>) 以10>>>2为例: 10：00000000 00000000 00000000 00001010 右移后，左侧空出的位置用0补齐，但是这里需要注意的是这个0并不是指符号位，只是一个普通的补位。得到的结果如下： 2：00000000 00000000 00000000 00000010 得到的十进制结果是2，结论就是10>>2=2。这个和有符号位移是得到相同的结果。 负数右移(>>>) 以-10>>>2为例: -10：11111111 11111111 11111111 11110110 右移后，左侧空位用0补，注意不是用1补，后面说原因。 00111111 11111111 11111111 11111101 这个结果就很大了，结果是1073741821，负数变成了这么大的负数，不要怀疑自己的眼神，这个结果是正确的。

总结

所谓的无符号右移，就是将原有的二进制值直接右移得到结果，不论是负数还是正数，没有补码的操作，补位都统一使用0，而不是对应的符号位1或0。

2. 在java中的应用

1. ^：异或的妙用：交换两个整数的值

int a=3,b=5;a = a ^ b;b = a ^ b;//a = (a^b)^b a = a ^ b; a= a^(a^b)System.out.println("a:" + a + ",b=" + b);

输出a=5,b=3 这个灵活的用到了异或来实现。下面做个简单的说明。 a = 3：00000011 b = 5：00000101 a异或b得到的结果是：00000110，这个结果赋值给a； b异或a得到的结果是：00000011，这个结果赋值给b; a异或b得到的结果是：00000101，这个结果赋值给a； 所以最终得到的结果是： a = 5：00000101 b = 3：00000011

2. <<：左移，相当于乘于2的y次方

System.out.println((2<<3));

输出：a=16

3. >>：右移，相当于除于2的-y次方，移位后不足的位用符号补充

x>>y 等于x*2-y 8>>:3 的结果为8 * 2(-3) = 1

4. >>>:与3 的区别就是，移位后不足的位用0补充

位运算只用于整数，并且如果超过范围所得值为0。比如8>>4，并不是0.5而是0

5. &：只要两边的boolean表达式结果有一个为false，即为false，只有两边为true才为ture。

6. ^：两边相同是false，两边不同是true。

7. |：两边只要有一个为true即为true，只有两边都为false时结果为false。

8. ~：取反（正变负，负变正）-1，~1=-2，~-1=0；~0=-1。

9. &与&&的区别：

• &：无论左边是true还是false，右边都要运算；
• &&：当左边为false时，右边就不运算，即短路原理。

10. 判断一个数的奇偶性

if((n & 1 ) == 0){奇数}else{偶数}

1的二进制是00000000 00000000 00000000 00000001，&运算的规则是只有都是1，结果才是1，很明显，不管是什么数，和1进行&运算，前31位都是0，只有最后一位可能得出不同的结果。偶数最后一位肯定是0，奇数肯定是1

11. |与||的区别：

• |：两边都参与运算；
• ||：当左边为true，右边不再运算，即短路原理。

12. 取绝对值

(n ^ (n>>31)) - (n >> 31);

13. hashmap中的应用

key经过hash函数作用后得到一个槽（buckets或slots）的索引（index），槽中保存着我们想要获取的值。 640

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;}
static final int hash(Object key) {  int h;  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}/** * Retrieve object hash code and applies a supplemental hash function to the * result hash, which defends against poor quality hash functions.  This is * critical because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */final int hash(Object k) {    int h = hashSeed;    if (0 != h && k instanceof String) {        return sun.misc.Hashing.stringHash32((String) k);    }    h ^= k.hashCode();    // This function ensures that hashCodes that differ only by    // constant multiples at each bit position have a bounded    // number of collisions (approximately 8 at default load factor).    h ^= (h >>> 20) ^ (h >>> 12);    return h ^ (h >>> 7) ^ (h >>> 4);}/** * Returns index for hash code h. */static int indexFor(int h, int length) {    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";    return h & (length-1);}

length must be a non-zero power of 2，注意到注释里面的英文没有？当容量是2^n时，h & (length - 1) == h % length 这个表达式就成立了。 m&(n-1)==m%n 成立的条件为n为2的整数次幂：

分析一下12%16  16=2^4备注：右移1位=/2的效果，例16>>1=16/2=81100 >>4 =0 ；1100%16==1100 也就是低四位干掉，这样余数也就是低四位例如11110%16其实应该就是1110k%（2^n）=（k的低n位）k/(2^n)=k向右移n位取一个整数低n位又是怎么样呢。也就是与一个低四位例如12%16=12的低四位=12&00001111=12&（16-1）

在哈希表容量（也就是buckets或slots大小）为length的情况下，为了使每个key都能在冲突最小的情况下映射到[0,length)（注意是左闭右开区间）的索引（index）内，一般有两种做法：

• 让length为素数，然后用hashCode(key) mod length的方法得到索引
• 让length为2的指数倍，然后用hashCode(key) & (length-1)的方法得到索引

关于方法1为什么要用素数，我这里不想过多介绍，大家可以看这里（http://suo.im/5aKbBh） 方法2的情况是： 因为length为2的指数倍，所以length-1所对应的二进制位都为1，然后在与hashCode(key)做与运算，即可得到[0,length)内的索引

如果hashCode(key)的大于length的值，而且hashCode(key)的二进制位的低位变化不大，那么冲突就会很多，举个例子： Java中对象的哈希值都32位整数，而HashMap默认大小为16，那么有两个对象那么的哈希值分别为：0xABAB0000与0xBABA0000，它们的后几位都是一样，那么与16异或后得到结果应该也是一样的，也就是产生了冲突。 造成冲突的原因关键在于16限制了只能用低位来计算，高位直接舍弃了，所以我们需要额外的哈希函数而不只是简单的对象的hashCode方法了。 具体来说，就是HashMap中hash函数干的事了 首先有个随机的hashSeed，来降低冲突发生的几率 然后如果是字符串，用了sun.misc.Hashing.stringHash32((String) k);来获取索引值 最后，通过一系列无符号右移操作，来把高位与低位进行异或操作，来降低冲突发生的几率 右移的偏移量20，12，7，4是怎么来的呢？因为Java中对象的哈希值都是32位的，所以这几个数应该就是把高位与低位做异或运算，至于这几个数是如何选取的，就不清楚了，网上搜了半天也没统一且让人信服的说法，可以参考下面几个链接： http://stackoverflow.com/questions/7922019/openjdks-rehashing-mechanism/7922219#7922219 http://stackoverflow.com/questions/9335169/understanding-strange-java-hash-function/9336103#9336103 http://stackoverflow.com/questions/14453163/can-anybody-explain-how-java-design-hashmaps-hash-function/14479945#14479945

14.ThreadPoolExecutor中的ctl:

private final AtomicInteger ctl = new AtomicInteger(ctlOf(RUNNING, 0));private static final int COUNT_BITS = Integer.SIZE - 3;private static final int CAPACITY   = (1 << COUNT_BITS) - 1;
// runState is stored in the high-order bitsprivate static final int RUNNING    = -1 << COUNT_BITS;private static final int SHUTDOWN   =  0 << COUNT_BITS;private static final int STOP       =  1 << COUNT_BITS;private static final int TIDYING    =  2 << COUNT_BITS;private static final int TERMINATED =  3 << COUNT_BITS;
// Packing and unpacking ctlprivate static int runStateOf(int c)     { return c & ~CAPACITY; }private static int workerCountOf(int c)  { return c & CAPACITY; }private static int ctlOf(int rs, int wc) { return rs | wc; }

15. 判断一个数是否是2的幂次方

如果该数是无符号整数，可以使用：

private static boolean isPowerOfTwo(int val) {      return (val & (val-1)) == 0;}

如果一个数是2的n次方，那么这个数用二进制表示时其最高位为1，其余位为0，(val-1)和val都错开了0和1，那么&一定是0。 如果该数是无符号整数，也可以使用：

private static boolean isPowerOfTwo(int val) {      return (val & -val) == val;}

如果一个数是2的n次方，那么这个数用二进制表示时其最高位为1，其余位为0，(val & -val)就是获取最右1的位，那么如果和val等于就是了。 扩展下，如何判断一个无符号数是2的n次方-1

private static boolean isPowerOfTwoLoseOne(int val) {      return (val & (val+1)) == 0;}

理由其实和上面类似了。

16. 操作位代表类型

JDK SelectionKey有四种操作类型，分别为：

OP_READ = 1 << 0；OP_WRITE = 1 << 2；OP_CONNECT = 1 << 3；OP_ACCEPT = 1 << 4。

由于只有四种网络操作类型，所以用4 bit就可以表示所有的网络操作位，由于JAVA语言没有bit类型，所以使用了整形来表示，每个操作位代表一种网络操作类型，分别为：0001、0010、0100、1000,这样做的好处是可以非常方便的通过位操作来进行网络操作位的状态判断和状态修改，提升操作性能。

17. 非2的幂次方转换为2的幂次方

在jdk很多集合框架里面，不知道你们还发现了，集合的大小都会是2的幂次方，哈哈，所以就引出了下面的话题。

 int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?                   MAXIMUM_CAPACITY :
    private static final int tableSizeFor(int c) {        int n = c - 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;    }

实例化ConcurrentHashMap时带参数时，会根据参数调整table的大小，确保table的大小总是2的幂次方，调用tableSizeFor的时候每次返回的都是大于等于离该数最近的2的幂次方的数。比如调用tableSizeFor传入c为151的时候 比151大的2的幂次方的数就是256了，核心就是上面的位运算操作。

其中ReentrantReadWriteLock中读写锁最多支持65535个递归写入锁和65535个递归读取锁。

刚刚上面是求一个数离它最近的大于等于2的幂次方的数，如果求小于等于2的幂次方的数，我们应该怎么办呢？

 private static final int tableSizeFor(int n) {        n |= n >>> 1;        n |= n >>> 2;        n |= n >>> 4;        n |= n >>> 8;        n |= n >>> 16;        return  n-(n>>1);    }

说明：由于集合的大小都会是2的幂次方，那么求table大小的0.75倍的时候，可以使用（n - (n >>> 2)）即可，取模的时候，可以使用hash & 0x7FFFFFFF来进行操作即可。

18. 将高16位全部抹去与无符号补0右移16位

在ReentrantLock中使用一个int类型的state来表示同步状态，该值表示锁被一个线程重复获取的次数。但是读写锁ReentrantReadWriteLock内部维护着两个一对锁，需要用一个变量维护多种状态。所以读写锁采用“按位切割使用”的方式来维护这个变量，将其切分为两部分，高16为表示读，低16为表示写。分割之后，读写锁是如何迅速确定读锁和写锁的状态呢？通过为运算。假如当前同步状态为S，那么写状态等于 S & 0x0000FFFF（将高16位全部抹去），读状态等于S >>> 16(无符号补0右移16位)。ReentrantReadWriteLock内部的同步容器框架Sync中的读写状态state，分成高16位与低16位，其中高16位表示读锁个数，低16位表示写锁个数。代码如下：

    static final int SHARED_SHIFT   = 16;    static final int SHARED_UNIT    = (1 << SHARED_SHIFT);    static final int MAX_COUNT      = (1 << SHARED_SHIFT) - 1;    static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;    static int sharedCount(int c)    { return c >>> SHARED_SHIFT; }    static int exclusiveCount(int c) { return c & EXCLUSIVE_MASK; }

19. 参考

https://mp.weixin.qq.com/s?_biz=MzIwMTY0NDU3Nw==&mid=2651935620&idx=1&sn=e0f594d35af319526ba7c6b049dd4f55&chksm=8d0f3ccaba78b5dcb2aea5fb1f02999ccc4a013223b29528a459cdf0502f5858a8427339b58a&mpshare=1&scene=1&srcid=0610UhyS6aEMD4mkPcews3PX&key=4aaedc7deb86b11c93067ea716c21b8aa59a20acd92357f1626472d812a5c5edcf5998b5c9f991563e5d2d6a0cd2630cda172a7f50f2eada95d34c69622035d205442e2054df9936c3894095c7ad4a0c&ascene=1&uin=MjY1ODQ5Mzk2Mw%3D%3D&devicetype=Windows+10&version=62060739&lang=zhCN&pass_ticket=PVb0cWp3ggxYQ%2Bh0VMcnzzLQRauX6nl%2Bj2D5vBFGofLTNAUvDCqHbGElZMaYuJzy

https://mp.weixin.qq.com/s/XZk9ZVozYiMCAP8K0YaUqg