java位运算
基本介绍
日常开发中位运算不是很常用,但是巧妙的使用位运算可以大量减少运行开销,优化算法。举个例子,翻转操作比较常见,比如初始值为1,操作一次变为0,再操作一次变为1。可能的做法是使用三目运算符,判断原始值为1还是0,如果是1,设置为0,否则设置为1。但是使用位运算,不用判断原始值,直接改变值就可以:
|
|
当然,一条语句可能对代码没什么影响,但是在高重复,大数据量的情况下将会节省很多开销。
相关概念
java中各种进制的表达方式
-
二进制
由0,1组成。以0b开头。
-
八进制
由0,1,…7组成。以0开头。
-
十进制
由0,1,…9组成。默认整数是十进制。
-
十六进制
由0,1,…9,a,b,c,d,e,f(大小写均可)组成。以0x开头。
原码、反码、补码
计算机中只有有符号数采用补码表示。比如8位有符号数表示范围是-128到127,而无符号数就可以表示0到255。计算机采用补码是为了有符号数中0的表示的唯一性,并且可以把减法转换成加法来运算。除了数字,计算机中还有很多其他的数据,比如说字符等,这些都不用补码表示。
正数的补码与原码相同,负数的补码除符号位外逐位取反,然后末位加一,如:原码10010(这是负数)= 反码11101=补码11110
原码-> 补码: 符号位不变,取反再+1 补码-> 原码: 符号位不变,-1再取反
**注意:**溢出也不能影响符号位原则
java中byte有8位(包括符号位),表示范围从-128到+127,补码表示:
- +127: 0 1111111
- -128: 1 0000000
-127 补码表示是10000001
原码11111111 减1(11111110)取反(10000001),
再减1 就是10000000,转换成原码就是-0, 也就是+0/-0 都表示0,在计算机中没必要使用两个不同形式的8位数表示0,于是规定把10000000当做-128的补码(事实上它也是-128的原码表示)。
|
|
数据类型
其中基本数据类型为:
注意:byte,short,char之间不会相互转换,他们三者在计算时首先转换为int类型。
|
|
有符号 & 无符号
-
有符号和无符号的概念如下
最明显的区别就是二者表示的范围不同: 无符号数中,所有的位都用于直接表示该值的大小。
有符号数中最高位用于表示正负,所以,当为正值时,该数的最大值就会变小。
我们举一个字节的数值对比:
无符号数: 1111 1111 值:255 1* 27 + 1* 26 + 1* 25 + 1* 24 + 1* 23 + 1* 22 + 1* 21 + 1* 20
有符号数: 0111 1111 值:127 1* 26 + 1* 25 + 1* 24 + 1* 23 + 1* 22 + 1* 21 + 1* 20
同样是一个字节,无符号数的最大值是255,而有符号数的最大值是127。 原因是有符号数中的最高位被挪去表示符号了。 并且,我们知道,最高位的权值也是最高的(对于1字节数来说是2的7次方=128),所以仅仅少于一位,最大值一下子减半。
不过,有符号数的长处是它可以表示负数。 因此,虽然它的在最大值缩水了,却在负值的方向出现了伸展。 我们仍一个字节的数值对比: 无符号数: 0 —————– 255 有符号数: -128 ——— 0 ———- 127 同样是一个字节,无符号的最小值是 0 ,而有符号数的最小值是-128。 所以二者能表达的不同的数值的个数都一样是256个。 只不过前者表达的是0到255这256个数,后者表达的是-128到+127这256个数 有
有符号数包括负数,无符号数只有正数而已,在同一数据类型中,由于内存长度是一样的,所以无符号数比有符号数的最大值大1倍。
-
java没有无符号类型,都是有符号类型的数据类型
在实际开发中,可能要与c写的硬件接口,网络接口相互直接数据交互,此时由于java没有无符号的数据类型,导致java与c看似相同的数据类型,其实存储空间确是不同的,这个问题解决方法是java用更高的存储数据类型,如果c用int,你的java就要考虑用Long或者BigInteger了
运算符优先级
位运算基本操作
乘除法是很消耗时间的,只要对数左移一位就是乘以2,右移一位就是除以2,传说用位运算效率提高了60%。
-
位运算是针对整数类型的二进制进行的位移操作
-
在Java中,整数的二进制是以补码的形式存在的
-
字符、short、byte 进行位运算会先转成整型
-
位运算计算完,还是补码的形式,要转成原码,再得出十进制值
-
也支持复合运算, 同
+=
、*=
,位运算也有复合运算, 如<<=
、>>>=
、&=
、^=
等等。eg
-4 * 2
-4 补码 11111111 11111111 11111111 11111100
左移一位 11111111 11111111 11111111 11111000 (这时候还是补码)
如果最高位符号位为0,就不需要继续操作了,因为正数的补码=原码,如果最高位是1,继续往下走
转成反码 11111111 11111111 11111111 11110111 (补码-1)
转成原码 10000000 00000000 00000000 00001000 (忽略符号位取反)
转十进制 -8
移位运算
移位运算符java移位运算符不外乎就这三种:<<
(左移)、>>
(带符号右移)和>>>
(无符号右移)。
位运算
左移 <<
整体左移,右边空出位补零,左边位舍弃 (-4 <<
1 = -8)
正数左移一定位数会变成负数,比如 1 « 31 此时1被位移到了整个int的首位,也就是符号位就会变成负数
右移 >>
整体右移,左边空出位补零或补1(负数补1,整数补0),右边位舍弃 (-4 >>
1 = -2)
无符号右移 >>>
同>>
,但不管正数还是负数都左边位都补0 (-4 >>>
1 = 2147483646)
右移不改变数的正负。对于一个正数,无符号右移不会变成负数(相当于除以1再取整);但是对于一个负数,无符号右移会将负数变成正数;
跟右移运算不同的是,无符号左移和左移是一样的。因此java没有无符号左移运算。(«<和«<=将报错)
因为无右移运算需要考虑符号位的右移,而符号位只存在于二进制表示的最左边,最右边没有。
所以不用区分无符号左移和左移运算。
位运算符
与 &
每一位进行比较,两位都为1,结果为1,否则为0(-4 & 1 = 0)
或 |
或( | )每一位进行比较,两位有一位是1,结果就是1(-4 | 1 = -3)
非 ~
每一位进行比较,按位取反(符号位也要取反)(~ -4 = 3)
异或 ^
每一位进行比较,相同为0,不同为1(-4 ^ 1 = -3)
位运算符的应用
-
推断int型变量a是奇数还是偶数
a & 1 = 0 偶数
a & 1 = 1 奇数
取a二进制的最后一位,如果为1则肯定是奇数,因为其他位都是2的整数次幂
-
取int型变量a的第k位 (k=1,2……sizeof(int))
a » k & 1
先左移K,把k移动到低1位,然后&1得到低一位的值
-
将int型变量a的第k位清0
a = a & ~(1 « k)
-
将int型变量a的第k位置1
a=a | (1 « k)
-
int型变量循环左移k次
a = a « k | a » 16-k (设sizeof(int)=16)
-
int型变量a循环右移k次
a = a » k | a « 16-k (设sizeof(int)=16)
-
整数的平均值
对于两个整数x,y,假设用 (x+y)/2 求平均值。会产生溢出。由于 x+y 可能会大于INT_MAX,可是我们知道它们的平均值是肯定不会溢出的。我们用例如以下算法:
1 2 3 4
int average(int x, int y) //返回X,Y 的平均值 { return (x & y) + ((x ^ y) >> 1); }
(x & y) + ((x ^ y) » 1),把x和y里对应的每一位(指二进制位)都分成三类,每一类分别计算平均值,最后汇总。
第一类
x,y对应位都是1,用x&y计算其平均值
x,y对应位均为1,相加后再除以2还是原来的数,如两个00001111相加后除以2仍得00001111
第二类
x,y中对应位有且只有一位是1,用(x^y)»1计算其平均值
对应位有且只有一位为1,用“异或”运算提取出来,然后»1(右移一位,相当于除以2)
第三类
x,y中对应位均为0,无须计算
汇总
(x & y) + ((x ^ y) » 1)
-
判断一个正整数是否是2的幂
1 2 3
public static boolean isPower(int n){ return n&(n-1) == 0 && n >0; }
如果一个数是2的n次方,那么这个数对应的二进制表示中只有一位是1,其余都是0. 因此判断一个数是否是2的n次方,可以转换为判断这个数对应的二进制表示是否只有一位为1. 如果一个数的二进制表示只有一位是1, 如 num = 00010000, 那么 num-1 的二进制为 num-1 = 00001111 由于num与num-1二进制表示中每一位都不相同,因此num&(num-1)的运算结果为0 可以用来判断一个数是否为2的n次方。
-
不用temp交换两个整数
1 2 3 4 5 6 7 8 9
public static void main(String[] args) { int a = 3, b = 5; System.out.println("before swap:" + "a=" + a + ",b=" + b); // 开始交换位置 a = a ^ b; b = a ^ b; // b=a^b^b=a a = a ^ b; // a=a^b^a=b System.out.println("after swap:" + "a=" + a + ",b=" + b); }
-
计算整数绝对值
1 2 3
private int abs(int i) { return (i ^ (i >> 31)) - (i >> 31); }
-
如果value是正数,右移31位之后就变成了0x00000000,
value和0x00000000异或,仍然是value,
异或之后的value-0x00000000仍然是value,
-
如果value是负数,右移31位就变成了0xffffffff,
value和0xffffffff异或,变成了value连着符号位全部取反,也就是实现了补码取反,
补码取反-0xffffffff也就是补码取反再+1,是就上就对应着value的绝对值
因为这里value和value的绝对值实际上只有最高位,也就是符号位不同, 这样移位就可以将最高位的符号位1变成0,实现绝对值的快速计算。
-
-
取模运算转化成位运算 (在不产生溢出的情况下)
a%$(2^n) $ 等价于 a & ($2^n$ - 1)
来源自
HashMap
中的indexFor
方法:1 2 3 4 5 6
/** * 使用哈希值对链表数组的长度取模,得到值所在的索引位置,里面使用位运算(&)代替普通的(%)运算 */ static int (int h, int length) { return h & (length-1); }
原理:
对于所有 $2^n$ 的数,二进制表示为:
1000…000,1 后面跟 n 个 0
而 $2^n - 1$ 的二进制为:
0111…111,0 后面跟 n 个 1
$X / 2^n$ 是 X » n,那么 X & ($2^n$ - 1) 就是取被移掉的后 n 位,也就是 X % $2^n$。
-
乘法运算转化成位运算 (在不产生溢出的情况下) $a * (2^n)$ 等价于 a « n
-
除法运算转化成位运算 (在不产生溢出的情况下) $a / (2^n)$ 等价于 a» n
-
a % 2
等价于 a & 1
-
x 的 相反数
取反+1: ~x+1
-
使用位掩码表示权限
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
public class NewPermission { // 是否允许查询,二进制第1位,0表示否,1表示是 public static final int ALLOW_SELECT = 1 << 0; // 0001 // 是否允许新增,二进制第2位,0表示否,1表示是 public static final int ALLOW_INSERT = 1 << 1; // 0010 // 是否允许修改,二进制第3位,0表示否,1表示是 public static final int ALLOW_UPDATE = 1 << 2; // 0100 // 是否允许删除,二进制第4位,0表示否,1表示是 public static final int ALLOW_DELETE = 1 << 3; // 1000 // 存储目前的权限状态 private int flag; /** * 重新设置权限 */ public void setPermission(int permission) { flag = permission; } /** * 添加一项或多项权限 */ public void enable(int permission) { flag |= permission; } /** * 删除一项或多项权限 */ public void disable(int permission) { flag &= ~permission; } /** * 是否拥某些权限 */ public boolean isAllow(int permission) { return (flag & permission) == permission; } /** * 是否禁用了某些权限 */ public boolean isNotAllow(int permission) { return (flag & permission) == 0; } /** * 是否仅仅拥有某些权限 */ public boolean isOnlyAllow(int permission) { return flag == permission; } }
可以替代位域的更好的方案 在《Effective Java》一书中,更推荐用EnumSet来代替位域:位域表示法也允许利用位操作,有效的执行像union和intersection这样的集合操作。但位域有着int枚举常量所有的缺点,甚至更多。当位域以数字形式打印时,翻译位域比翻译简单的int枚举常量要困难很多。甚至要遍历位域表示的所有元素也没有很容易的方法。
改成EnumSet的写法是:
1 2 3 4 5 6 7 8 9 10
public class Text { public enum Style { BOLD, ITALIC, UNDERLINE, STRIKETHROUGH } public void applyStyles(Set<Style> styles) { System.out.println(styles); } }
-
老鼠试毒药
有 1000 个一模一样的瓶子,其中有 999 瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在,你只有 10 只小白鼠和一星期的时间,如何检验出哪个瓶子里有毒药?
根据2^10=1024,所以10个老鼠可以确定1000个瓶子具体哪个瓶子有毒。具体实现跟3个老鼠确定8个瓶子原理一样。 000=0 001=1 010=2 011=3 100=4 101=5 110=6 111=7 一位表示一个老鼠,从左到右分别代表老鼠3,老鼠2,老鼠1。0-7表示8个瓶子。也就是分别将1、3、5、7号瓶子的药混起来给老鼠1吃,2、3、6、7号瓶子的药混起来给老鼠2吃,4、5、6、7号瓶子的药混起来给老鼠3吃,哪个老鼠死了,相应的位标为1。如老鼠1死了、老鼠2没死、老鼠3死了,那么就是101=5号瓶子有毒。同样道理10个老鼠可以确定1000个瓶子
-