您的位置 首页 java

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

源码分享说明

  • 本人非常热衷于源码研究,同时也非常愿意将自己在源码方面研究的心得进行分享,如果读者也想对源码进行研究,可以关注我分享的文章。
  • 在进行源码解析的过程中,将会选择庖丁解牛式剖析,将会解析清楚每一行核心代码,让读者能够真正透彻理解,这样无论是在以后的面试中还是独立开发中间件都会有很大好处。

序言

  • 这个系列主要分享 Java 集合类源码,由于Java集合中每一个容器类都是基于特定的数据结构实现。其实我本人也是直接就分享源码,但是如果读者本身的基础不是很好,导致最终分享的效果不是很好,只能退而求其次,通过基础系列补充对应的数据结构方面的基础,当然在数据结构内容的选取方面,只会选取跟Java集合类相关的东西,数据结构基础越扎实,阅读源码的效果就越好。
  • 数据在计算机中是以补码的形式存在,并且一般都是基于整数,Java集合类中会有大量的位运算,常见的 位运算 有取反,与,或,异或,左移,右移这六种,考虑到读者对这方面的知识可能不是很熟悉,所以特地分享这一篇技术文章,首先从概念上进行阐述,为了更好的巩固这些东西,精心选取了几个示例进行讲解,相信能够对读者有些帮助。

1.数据表示形式

我们都知道在数字有 原码 反码 ,补码, 移码 这4中表示形式,但是为了让符号位能够跟数据位参与一样的运算规则,在计算机中使用补码的形式表示数据,同时在Java集合中,参与位运算都是整数,所以着重讲解 整数补码 操作。

把符号”数字化”的数称为 机器数 ,而把带”+”或”-“符号的数称为 真值

原码: 符号位为0表示整数,符号位为1表示负数,数值位即真值的绝对值,故原码表示又称为带符号的绝对值表示。

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

例如:[+14]原 = 0,1110;[-14]原 = 1,1110;

反码:

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

例如:[+14]反 = 0,1110;[-14]反 = 1,0001;

补码:

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

例如:[+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,就可以把数据存进去。

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

如果我们需要使用位图表示数据【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));
    }
}  

文章来源:智云一二三科技

文章标题:位运算–java集合源码体系研究之基础,让你面试胖揍面试官

文章地址:https://www.zhihuclub.com/183391.shtml

关于作者: 智云科技

热门文章

网站地图