位运算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
　　例如：
　　0000101011110101；
　　1000101001110101；
　　与，或，异或
　　与（）
　　000
　　010
　　100
　　111
　　或（）
　　000
　　011
　　101
　　111
　　异或（）
　　000
　　011
　　101
　　110
　　其实对于异或运算，你可以理解为无进位相加
　　例如：
　　000000；
　　011011；
　　100101；
　　1101110舍弃进位1就得到110；
　　左移运算符
　　mn表示把m左移n位。如果左移n位，那左端的n位将会被丢弃，同时在最右边补上n个0
　　例如：
　　00001010200101000；
　　10001010301010000；
　　无符号右移运算符
　　mn表示把m无符号右移n位。如果无符号右移n位，那右端的n位将会被丢弃，同时在最左边补上n个0
　　例如：
　　00001010200000010；
　　10001010300010001；
　　右符号右移运算符
　　mn表示把m有符号右移n位。如果有符号右移n位，那右端的n位将会被丢弃，同时在最左边补上n个符号位
　　例如：
　　00001010200000010；
　　100010103111110001；
　　位运算尽管定义得非常简洁，但是如果你使用的好，威力将是无穷，举上几例让你们感受一下，对于例题中给出的结论要牢牢记住并且能够做到融会贯通。
　　3。实例操作
　　结论：n（n1）将n最右端的1变为0
　　例1：给定一个32位整数n，可为0，可为正，也可为负，返回该整数二进制表达式中1的个数
　　首先分析一下n（n1）这个位运算的结果
　　为了便于直观，我们先随机取一个数n01000100，n101000011
　　n（n1）010001000100001101000000即将最右端的1变为0
　　其实这个结论也是非常容易证明，试证一下，假如n最右端1出现在i位上，这样n1的结果体现为：i位变成0，i位前面不变，i位后面全部变成了1，这样n（n1）的结果就是i位变成0，同时i位后面本来就是0，所以没有影响。从而证明了n（n1）将n最右端的1变为0
　　有了如上这个结论n（n1）可理解为将n最右端的1变为0再赋值给npublicintresolve（intnum）｛intresult0；每一次循环都去掉num中最右端的1等所有num中所有1都去掉之后num0结束循环，得到num中1的个数while（num！0）｛去掉num中最右端的1num（num1）；｝｝
　　结论：n（n）得到n最右端第一次出现1的位置
　　根据补码的结论有nn1
　　例2：在一个数字序列中，有两个数出现了奇数次，其他数都出现了偶数次，寻找这两个数。
　　异或运算符合两个性质：交换律和结合律，也就是说
　　
　　abca（bc）（ab）c；
　　其实这两个性质我们可以统一来证明一下，我们上面说到异或运算，可以理解为无进位相加，有了这个上面两条性质就很好证明了ab的结果就是a转化为二进制和b转化为二进制，按对应每一个二进制位相加组合而得到，自然abba。类似可以证明abca（bc）（ab）c
　　异或运算又有如下两个性质，根据异或运算，可以理解为无进位相加很轻易得到
　　aa0
　　a0a
　　这样就有如此结论：偶数次异或为0，奇数次异或为本身
　　下面证明结论：n（n1）得到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，npublicvoidresolve（int〔〕arr）｛intresone0；for（intvalue：arr）｛｝经过上面异或运算之后resonemn由于m！n，所以resone肯定不为0resone二进制下必然有某一位为1，这里选择最右边的1上面我们证明了通过resone（resone1）得到最右端为1的位假如最右端第i位为1，则m，n在第i位必然有一个为1，另一个为0不然与resone第i位为1相矛盾intrightoneresone（resone1）；intrestwo0；for（intvalue：arr）｛将数组中第i位为1和为0的元素分开假如m第i位为1，n第i位为0找出第i位为1的元素跟restwo异或整个循环结束之后restwo就是m的值if（（valuerightone）！0）｛｝｝resonemn，restwom，resonerestwomnmnSystem。out。println（restwo（resonerestwo））；｝
　　例3：位图
　　每个元素为0或1，表示其对应的元素不存在或者存在。为了表示某个数字存在，将对应索引位的bit值置为1。
　　如果使用charM〔N〕这种结构存储，可以存储N8个数据，但是最大的数只能是
　　N81。
　　例如我们要存储数据范围为015，则只需要使得N2，就可以把数据存进去。
　　如果我们需要使用位图表示数据【5，1，7，15，0，4，6，10】，只需要将位图中【5，1，7，15，0，4，6，10】对应bit位的值变为1，最终位图结构中如下所示
　　下面代码示例了使用位图进行添加操作，至于其它的操作（删除检索）都是类似，没有书写对应代码，因为觉得没有必要，毕竟本意是让读者能够更好的理解位运算。publicclassBitMap｛privatelong〔〕一个long有64个bit位，根据构造时传入的最大值决定需要多少个连续的long值存储publicBitMap（intmax）｛如果是一个数字，即使这个数字是0，也需要申请一个。n6是将n除以64进行向上取整bitsnewlong〔（max64）6〕；｝publicvoidadd（intnum）｛为了更好的理解下面这行代码的逻辑我们选择举一个例子直观说明例如需要添加数字170我们需要知道long〔〕哪个索引的long负责存储0位索引long负责整数：063（第一位管0，第63位管64）1位索引long负责整数：641272位索引long负责整数：128191170在这个范围之内，就使用2位索引long存储现在我们已经找到哪个索引long存储还需要知道170处于这个long中哪个bit位中前面2个long存储了128个bit170对应在第3个long中bit位为17012842对应的操作已经说清楚了，现在需要说明怎样通过代码实现1。得到long〔〕哪个索引的long负责存储将给定数字64进行向上取整就可以，转换为位运算就是给定数字62。得到long〔〕对应索引long中的bit位特此说明一下在n为2的指数次幂1就会numnnumn这个在hashmap中也使用了这个性质，其实证明也很简单，读者可以尝试证明num64就是num63，也就是把小于64的数字都取出来，这就是余数63的二进制：（这里还有32位）000000000000000000000000000111111170的二进制：（这里还有32位）000000000000000000000000010101010结果：（这里还有32位）000000000000000000000000000101010bits〔num6〕（1L（num63））；｝｝