位运算java集合源码体系研究之基础，让你面试胖揍面试官

　　源码分享说明 本人非常热衷于源码研究，同时也非常愿意将自己在源码方面研究的心得进行分享，如果读者也想对源码进行研究，可以关注我分享的文章。 在进行源码解析的过程中，将会选择庖丁解牛式剖析，将会解析清楚每一行核心代码，让读者能够真正透彻理解，这样无论是在以后的面试中还是独立开发中间件都会有很大好处。
　　序言 这个系列主要分享Java集合类源码，由于Java集合中每一个容器类都是基于特定的数据结构实现。其实我本人也是直接就分享源码，但是如果读者本身的基础不是很好，导致最终分享的效果不是很好，只能退而求其次，通过基础系列补充对应的数据结构方面的基础，当然在数据结构内容的选取方面，只会选取跟Java集合类相关的东西，数据结构基础越扎实，阅读源码的效果就越好。 数据在计算机中是以补码的形式存在，并且一般都是基于整数，Java集合类中会有大量的位运算，常见的位运算有取反，与，或，异或，左移，右移这六种，考虑到读者对这方面的知识可能不是很熟悉，所以特地分享这一篇技术文章，首先从概念上进行阐述，为了更好的巩固这些东西，精心选取了几个示例进行讲解，相信能够对读者有些帮助。
　　1.数据表示形式
　　我们都知道在数字有原码，反码，补码，移码这4中表示形式，但是为了让符号位能够跟数据位参与一样的运算规则，在计算机中使用补码的形式表示数据，同时在Java集合中，参与位运算都是整数，所以着重讲解整数补码操作。
　　把符号＂数字化＂的数称为机器数，而把带＂+＂或＂-＂符号的数称为真值
　　原码：符号位为0表示整数，符号位为1表示负数，数值位即真值的绝对值，故原码表示又称为带符号的绝对值表示。
　　例如：[+14]原 = 0,1110;[-14]原 = 1,1110;
　　反码：
　　例如：[+14]反 = 0,1110;[-14]反 = 1,0001;
　　补码：
　　例如：[+14]补 = 0,1110;[-14]补 = 1,0010;
　　综上所述，三种机器数有如下特点 三种机器数的最高位均为符号位。 当真值位正时，原码，反码，补码表示形式相同，即符号位用0表示，数值部分与真值相同。 当真值位负时，原码，反码，补码表示形式不同，但其符号位用1表示，而数值部分关系为反码是原码的每位求反，补码是原码每位求反加1。
　　2.位运算
　　我们常见的位运算有取反，与，或，异或，左移，右移这六种
　　取反：0取反得1,1取反得0
　　例如：
　　~0000 1010 = 1111 0101；
　　~1000 1010 = 0111 0101；
　　与，或，异或
　　与(&)
　　0&0=0
　　0&1=0
　　1&0=0
　　1&1=1
　　或(|)
　　0|0=0
　　0|1=1
　　1|0=1
　　1|1=1
　　异或(^)
　　0^0=0
　　0^1=1
　　1^0=1
　　1^1=0
　　其实对于异或运算，你可以理解为无进位相加
　　例如：
　　0 ^ 0 = 0 ==>> 0 + 0 = 0；
　　0 ^ 1 = 1 ==>> 0 + 1 = 1；
　　1 ^ 0 = 0 ==>> 1 + 0 = 1；
　　1 ^ 1 = 0 ==>> 1 + 1 = 10 舍弃进位1就得到1 + 1 = 0；
　　左移运算符
　　m << n表示把m左移n位。如果左移n位，那左端的n位将会被丢弃，同时在最右边补上n个0
　　例如：
　　0000 1010 << 2 = 0010 1000；
　　1000 1010 << 3 = 0101 0000；
　　无符号右移运算符
　　m >>> n表示把m无符号右移n位。如果无符号右移n位，那右端的n位将会被丢弃，同时在最左边补上n个0
　　例如：
　　0000 1010 >>> 2 = 0000 0010；
　　1000 1010 >>> 3 = 0001 0001；
　　右符号右移运算符
　　m >> n表示把m有符号右移n位。如果有符号右移n位，那右端的n位将会被丢弃，同时在最左边补上n个符号位
　　例如：
　　0000 1010 >> 2 = 0000 0010；
　　1000 1010 >> 3 = 11111 0001；
　　位运算尽管定义得非常简洁，但是如果你使用的好，威力将是无穷，举上几例让你们感受一下，对于例题中给出的结论要牢牢记住并且能够做到融会贯通。
　　3.实例操作
　　结论：n & (n-1)将n最右端的1变为0
　　例1：给定一个32位整数n，可为0，可为正，也可为负，返回该整数二进制表达式中1的个数
　　首先分析一下n & (n-1)这个位运算的结果
　　为了便于直观，我们先随机取一个数n = 0100 0100，n - 1 = 0100 0011
　　n & (n-1) = 0100 0100 & 0100 0011 = 0100 0000 即将最右端的1变为0
　　其实这个结论也是非常容易证明，试证一下，假如n最右端1出现在i位上，这样n - 1的结果体现为：i位变成0，i位前面不变，i位后面全部变成了1，这样n & (n-1)的结果就是i位变成0，同时i位后面本来就是0，所以没有影响。从而证明了n & (n-1)将n最右端的1变为0
　　有了如上这个结论 n &= (n-1)可理解为将n最右端的1变为0再赋值给n public int resolve(int num){      int result = 0;        //每一次循环都去掉num中最右端的1      //等所有num中所有1都去掉之后      //num = 0结束循环,得到num中1的个数      while(num != 0) {          //去掉num中最右端的1       　　num &= (num - 1);             　　result++;       }        return result; }
　　结论：n & (-n)得到n最右端第一次出现1的位置
　　根据补码的结论有 -n = ~n + 1
　　例2：在一个数字序列中，有两个数出现了奇数次，其他数都出现了偶数次，寻找这两个数。
　　异或运算符合两个性质：交换律和结合律，也就是说
　　a ^ b = b ^ a;
　　a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
　　其实这两个性质我们可以统一来证明一下，我们上面说到异或运算，可以理解为无进位相加，有了这个上面两条性质就很好证明了a ^ b的结果就是a转化为二进制和b转化为二进制，按对应每一个二进制位相加组合而得到，自然a ^ b = b ^ a。类似可以证明a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c
　　异或运算又有如下两个性质，根据异或运算，可以理解为无进位相加很轻易得到
　　a ^ a = 0
　　a ^ 0 = a
　　这样就有如此结论：偶数次异或为0，奇数次异或为本身
　　下面证明结论：n & (~n + 1)得到n最右端第一次出现1的位置
　　假如n最右端1出现在i位上，~n第i位为0，i位前面全部取反，i位后面全部变成了1，加上1之后，第i位重新变为1，i位后面全部变成了0，在跟n进行&运算，由于在i位前面，n与-n全部相反，自然&运算之后全部为0，~n第i位后面全部变成了0，与任何数&运算之后也全部为0，同时
　　n和-n第i位都是1，所以&运算之后第i位还是1，证毕。 //假如两个数出现了奇数次分别为m,n public void resolve(int[] arr){     int res_one = 0;             for(int value:arr){         res_one ^= value;     }     //经过上面异或运算之后res_one = m ^ n     //由于m != n，所以res_one肯定不为0     //res_one二进制下必然有某一位为1，这里选择最右边的1        //上面我们证明了通过 res_one & (~res_one + 1)得到最右端为1的位     //假如最右端第i位为1，则m,n在第i位必然有一个为1，另一个为0     //不然与res_one第i位为1相矛盾     int right_one = res_one & (~res_one + 1);     int res_two = 0;     for(int value:arr){         //将数组中第i位为1和为0的元素分开         //假如m第i位为1,n第i位为0         //找出第i位为1的元素跟res_two异或         //整个循环结束之后res_two就是m的值         if((value & right_one) != 0) {             res_two ^= value;         }     }     //res_one = m ^ n，res_two = m，     //res_one^res_two = m ^ n ^ m = n     System.out.println(res_two+＂ ＂ +(res_one^res_two)); }
　　例3：位图
　　每个元素为＂0＂或＂1＂，表示其对应的元素不存在或者存在。为了表示某个数字存在，将对应索引位的bit值置为1。
　　如果使用char M [N]这种结构存储，可以存储 N * 8个数据，但是最大的数只能是
　　N * 8 - 1。
　　例如我们要存储数据范围为0-15，则只需要使得N=2，就可以把数据存进去。
　　如果我们需要使用位图表示数据【5，1，7，15，0，4，6，10】，只需要将位图中【5，1，7，15，0，4，6，10】对应bit位的值变为1，最终位图结构中如下所示
　　下面代码示例了使用位图进行添加操作，至于其它的操作(删除/检索)都是类似，没有书写对应代码，因为觉得没有必要，毕竟本意是让读者能够更好的理解位运算。 public class BitMap {     private long[] bits;             //一个long有64个bit位，根据构造时传入的最大值     // 决定需要多少个连续的long值存储     public BitMap(int max) {     // 如果是一个数字，即使这个数字是0，也需要申请一个。     // n >> 6 是将n除以64进行向上取整     bits = new long[(max + 64) >> 6];     }          public void add(int num) {         //为了更好的理解下面这行代码的逻辑         //我们选择举一个例子直观说明         // 例如需要添加数字170         //我们需要知道long[]哪个索引的long负责存储         // 0位索引long负责整数：0-63（第一位管0，第63位管64）         // 1位索引long负责整数：64-127         // 2位索引long负责整数：128-191         //170在这个范围之内，就使用2位索引long存储         //现在我们已经找到哪个索引long存储         //还需要知道170处于这个long中哪个bit位中         //前面2个long存储了128个bit         //170对应在第3个long中bit位为170-128=42              //对应的操作已经说清楚了，现在需要说明怎样通过代码实现                  //1.得到long[]哪个索引的long负责存储         //将给定数字/64进行向上取整就可以，转换为位运算就是给定数字>>6         //2.得到long[]对应索引long中的bit位         //特此说明一下在n为2的指数次幂-1就会num % n = num & n         //这个在hashmap中也使用了这个性质,其实证明也很简单，读者可以尝试证明         // num % 64 就是 num & 63，也就是把小于64的数字都取出来，这就是余数         // 63 的二进制:(这里还有32位) 00000000 00000000 00000000 000111111         // 170的二进制:(这里还有32位) 00000000 00000000 00000000 010101010         // 结果：(这里还有32位) 00000000 00000000 00000000 000101010         bits[num >> 6] |= (1L << (num & 63));     } }