java中的位运算UML简单学习

Published: by Creative Commons Licence

  • Categories:

位运算

java支持的位运算符:

&:按位与。  
|:按位或。
~:按位非。
^:按位异或。
<<:左位移运算符。
>>:右位移运算符。  
<<<:无符号右移运算符。  

位运算符中,除~以外,其余均为二元运算符.操作数只能为整型和字符型数据.
Java使用补码来表示二进制数,在补码表示中,最高位为符号位,正数的符号位为0,负数为1.
补 码 的 规 定 如 下 :
对正数来说,最高位为0,其余各位代表数值本身(以二进制表示),如+42的补码为00101010。
对负数而言,把该数绝对值的补码按位取反,然后对整个数加1,即得该数的补码。如-1的补码 为11111111111111111111111111111111(00000000000000000000000000000001按位取反 11111111111111111111111111111110+1=11111111111111111111111111111111 )。
为何有那么多0、1,java中int是32位的。

按位与(&)
运算规则:
20180506152562229916803.png

规则总结:只有两个操作数对应位同为1时,结果为1,其余全为0. (或者是只要有一个操作数为0,结果就为0)。
举例:
2018050715256224418178.png

这是按位对比,比如8&9,用十进制的眼光去看简直就瞎了,8&9其实做的运算就是00001000&00001001,然后看到当且仅当两个对应的位置都是1,结果才是1,否则结果为0,那么结果就是00001000,也就是8.
那么,这个运算有什么卵用么?答案是当然有啦,比如,我们现在都是用int去做标志位,比如1代表正常,0代表异常,那如果我们用二进制来做的话,不就很爽了么,0001代表正常0010代表异常,0100代表XXX,是不是想想都有点小激动·····

按位或(|)
运算规则:
20180507152562256840524.png
规则总结:只有两个操作数对应位同为0时,结果为0,其余全为1.(或者是只要有一个操作数为1,结果就为1)。

按位非(~)
运算规则:
20180507152562264856585.png
按位取反,比如~8对吧,那就是00001000按位取反结果是11110111.前面说了,这是有符号数,也就是最高位代表符号位,也就是~8的结果是一个负数,那么人类第一反应是-8,但结果却不是,那这里简单解析一下,负数的二进制表示方式跟正数不一样,负数有一个反码和补码的概念,这么理解呢?就说-8吧,用二进制表示-8是:11111000,-10的二进制是:11110110.
首先-8的绝对值8的二进制是00001000, 求其反码就是11110111,补码(+1)是11111000。那么上面~8的结果11110111是多少呢?我们算一下,先-1得到11110110,然后取反:00001001,得到9,那么~8==9?不是的,是结果的绝对值,因为是负数,所以是-9.这个结果大家可以去验证下~~~

按位异或(^)
运算规则:
20180507152562279290461.png
当运算符两边不同的时候结果为1,两边相同的时候结果为0 这就是传说中的同性相杀,异性相吻。举个例子就是:8^6=1000^0110=1110=14

左位移(«)
逻辑左移==算术左移,右边统一补0.
2018050715256231625969.png
当移动的位数超过数字本身的位数时,那么不就都需要补0操作,实际上不是的,java不可能做那么浪费资源的事情。在真正执行位移前,其对要移动的位数做了一些预处理,比如32处理为0,-1处理为31.

右位移(»)
逻辑右移就是不考虑符号位,右移一位,左边补零即可。
算术右移需要考虑符号位,右移一位,若符号位为1,就在左边补1,;否则,就补0。
所以算术右移也可以进行有符号位的除法,右移,n位就等于除2的n次方
20180507152562325888358.png
低位溢出,符号位不变,并用符号位补溢出的高位。如:-6»2结果为-2。

无符号右移(»>)
低位溢出,高位补0。注意,无符号右移(»>)中的符号位(最高位)也跟着变(跟着移动,而»不会随着移动),无符号的意思是将符号位当作数字位看待。如:-1»>1结果为2147483647。这个数字应该比较熟悉,看两个输出语句就知道是什么了:

System.out.println(Integer.toBinaryString(-1>>>1));

System.out.println(Integer.toBinaryString(Integer.MAX_VALUE));

输出结果为:

1111111111111111111111111111111

1111111111111111111111111111111

-1»>1竟然得到了int所能表示的最大整数,精彩。
20180507152562340236059.png
除了使用-1»>1能得到Integer.MAX_VALUE,以下的也能得到同样的结果:

//maxInt

System.out.println(~(1 << 31));

System.out.println((1 << -1)-1);

System.out.println(~(1 << -1));

使用位运算往往能很巧妙的实现某些算法完成一些复杂的功能。

常见位移操作使用方法

m*2^n
可以使用m«n求得结果,如:

System.out.println("2^3=" + (1<<3));//2^3=8

System.out.println("3*2^3=" + (3<<3));//3*2^3=24

计算结果是不是很正确呢?如果非要说2«-1为什么不等于0.5,前面说过,位运算的操作数只能是整型和字符型。在求int所能表示的最小值时,可以使用

//minInt

System.out.println(1 << 31);

System.out.println(1 << -1);

可以发现左移31位和-1位所得的结果是一样的,同理,左移30位和左移-2所得的结果也是一样的。移动一个负数位,是不是等同于右移该负数的绝对值位呢?输出一下就能发现不是的。java中int所能表示的最大数值是31位,加上符号位共32位。在这里可以有这样的位移法则:
法则一:任何数左移(右移)32的倍数位等于该数本身。
法则二:在位移运算m«n的计算中,若n为正数,则实际移动的位数为n%32,若n为负数,则实际移动的位数为(32+n%32),右移,同理。
左移是乘以2的幂,对应着右移则是除以2的幂.

判断一个数n的奇偶性

n&1 == 1?”奇数”:”偶数”

为什么与1能判断奇偶?所谓的二进制就是满2进1,那么好了,偶数的最低位肯定是0(恰好满2,对不对?),同理,奇数的最低位肯定是1.int类型的1,前31位都是0,无论是1&0还是0&0结果都是0,那么有区别的就是1的最低位上的1了,若n的二进制最低位是1(奇数)与上1,结果为1,反则结果为0.

不用临时变量交换两个数
在int[]数组首尾互换中,是不看到过这样的代码:

public static int[] reverse(int[] nums){  
    int i = 0;  
    int j = nums.length-1;  
    while(j>i){  
        nums[i]= nums[i]^nums[j];  
        nums[j] = nums[j]^nums[i];  
        nums[i] = nums[i]^nums[j];  
        j--;  
        i++;  
    }  
    return nums;  
}  

连续三次使用异或,并没有临时变量就完成了两个数字交换,怎么实现的呢?
20180507152562382297877.png
上面的计算主要遵循了一个计算公式:b^(a^b)=a。
我们可以对以上公式做如下的推导:
任何数异或本身结果为0.且有定理a^b=b^a。异或是一个无顺序的运算符,则b^a^b=b^b^a,结果为0^a。

再次列出异或的计算表:
20180507152562388476823.png
可以发现,异或0具有保持的特点,而异或1具有翻转的特点。使用这些特点可以进行取数的操作。

那么0^a,使用异或0具有保持的特点,最终结果就是a。

其实java中的异或运算法则完全遵守数学中的计算法则:

  1. a ^ a =0
  2. a ^ b =b ^ a
  3. a ^b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
  4. d = a ^b ^ c 可以推出 a = d ^ b ^ c.
  5. a ^ b ^a = b.

取绝对值
(a^(a»31))-(a»31)
先整理一下使用位运算取绝对值的思路:若a为正数,则不变,需要用异或0保持的特点;若a为负数,则其补码为源码翻转每一位后+1,先求其源码,补码-1后再翻转每一位,此时需要使用异或1具有翻转的特点。

任何正数右移31后只剩符号位0,最终结果为0,任何负数右移31后也只剩符号位1,溢出的31位截断,空出的31位补符号位1,最终结果为-1.右移31操作可以取得任何整数的符号位。

那么综合上面的步骤,可得到公式。a»31取得a的符号,若a为正数,a»31等于0,a^0=a,不变;若a为负数,a»31等于-1 ,a^-1翻转每一位.

小结

在日常的java开发中位运算使用的不是很常见,但是面试或考试中会有涉及的地方,虽然不是决定项,但却是加分项,说明对计算机语言有最起码的了解。而且在高级算法中,位运算往往能优化算法运行效率,减少运行时间。再比如,有一张全是选择题或是勾选题(类似判断)的试卷,你是使用每个选项一条记录的形式保存答案还是使用一个二进制对应的整数来保存答案?就像是英语考试中的答题卡:
20180507152562400238728.png
每个题目有4个选项,每个选项有两个状态:选、不选(1、0),那么此时是不是可以使用4位二进制数来表示某题的答案呢?


UML类图

在UML类图中,常见的有以下几种关系: 泛化(Generalization), 实现(Realization),关联(Association),聚合(Aggregation),组合(Composition),依赖(Dependency).

泛化(Generalization)
【泛化关系】:是一种继承关系,表示一般与特殊的关系,它指定了子类如何特化父类的所有特征和行为。例如:老虎是动物的一种,即有老虎的特性也有动物的共性。
【箭头指向】:带三角箭头的实线,箭头指向父类
20180507152562434358541.png

实现(Realization)
【实现关系】:是一种类与接口的关系,表示类是接口所有特征和行为的实现.
【箭头指向】:带三角箭头的虚线,箭头指向接口
20180507152562441087095.png

关联(Association)
【关联关系】:是一种拥有的关系,它使一个类知道另一个类的属性和方法;如:老师与学生,丈夫与妻子关联可以是双向的,也可以是单向的。双向的关联可以有两个箭头或者没有箭头,单向的关联有一个箭头。
【代码体现】:成员变量
【箭头及指向】:带普通箭头的实心线,指向被拥有者
20180507152562443853659.png

上图中,老师与学生是双向关联,老师有多名学生,学生也可能有多名老师。但学生与某课程间的关系为单向关联,一名学生可能要上多门课程,课程是个抽象的东西他不拥有学生。

下图为自身关联:
20180507152562445763579.png

聚合(Aggregation)
【聚合关系】:是整体与部分的关系,且部分可以离开整体而单独存在。如车和轮胎是整体和部分的关系,轮胎离开车仍然可以存在。
聚合关系是关联关系的一种,是强的关联关系;关联和聚合在语法上无法区分,必须考察具体的逻辑关系。
【代码体现】:成员变量
【箭头及指向】:带空心菱形的实心线,菱形指向整体
20180507152562448662896.png

组合(Composition)
【组合关系】:是整体与部分的关系,但部分不能离开整体而单独存在。如公司和部门是整体和部分的关系,没有公司就不存在部门。
组合关系是关联关系的一种,是比聚合关系还要强的关系,它要求普通的聚合关系中代表整体的对象负责代表部分的对象的生命周期。
【代码体现】:成员变量
【箭头及指向】:带实心菱形的实线,菱形指向整体
20180507152562451680676.png

依赖(Dependency)
【依赖关系】:是一种使用的关系,即一个类的实现需要另一个类的协助,所以要尽量不使用双向的互相依赖.
【代码表现】:局部变量、方法的参数或者对静态方法的调用
【箭头及指向】:带箭头的虚线,指向被使用者
20180507152562454559268.png

总结
泛化 = 实现 > 组合 > 聚合 > 关联 > 依赖

下面这张UML图,比较形象地展示了各种类图关系:
20180507152562458068361.png

参考

java的位运算解析(&/|/~/^/»/«/»>
Java位运算原理及使用讲解
逻辑左移、算术左移、逻辑右移、算术右移区别
UML类图几种关系的总结
看懂UML类图和时序图