赞
踩
根基不牢,地动山摇
提及位运算,相信对绝大多数Java程序员是感觉既陌生又熟悉的。陌生是因为你大概率没有去真实的使用过,熟悉是有时在看些开源框架(或者JDK源码)时会时长看到有使用的地方(譬如Jackson/Fastjson这些JSON库都大量的使用了位运算)。
当然,不能“流行”起来是有原因的:不好理解,不符合人类的思维,阅读性差…位运算它在low-level的语言里使用得比较多,但是对于Java这种高级语言它就很少被提及了。虽然我们使用得很少但Java也是支持的,毕竟很多时候使用位运算才是最佳实践。
位运算在日常开发中使用得较少,但是巧妙的使用位运算可以大量减少运行开销,优化算法:一条语句可能对代码没什么影响,但是在高重复,大数据量的情况下将会节省很多开销。
在了解什么是位运算之前,有必要先简单科普下二进制的概念。
二进制是计算技术中广泛采用的一种数制。二进制数据是用0和1两个数码来表示的数。它的基数为2,进位规则是“逢二进一”,借位规则是“借一当二”。0、1是基本算符。因为它只使用0、1两个数字符号,非常简单方便,易于用电子方式实现(比如半导体)
比如请计算如下的计算结果(二进制):
- 求 1011(2进制)+ 11(2进制) 的和?
- 结果为:1110(二进制数)
了解了什么是二进制后,其实八进制、十进制与十六进制都是差不多的,它们之间区别在于数运算时是逢几进一位,借一当作几
关于进制转换这个知识点就老生常谈了,由于现存有非常多的文章讲解它,因为我就无需重复造轮子了,此处我推荐百度经验的一篇文章供以你学习参考:二进制、八进制、十进制、十六进制之间的转换
计算机能识别的只有1和0,也就是二进制,而1和0可以表达出全世界的所有文字和语言符号。
那如何表达文字和符号呢?这就涉及到字符编码了。字符编码强行将每一个字符对应一个十进制数字(请注意字符和数字的区别,比如’0’字符对应的十进制数字是48),再将十进制数字转换成计算机理解的二进制,而计算机读到这些1和0之后就会显示出对应的文字或符号。关于编码的进化史,有兴趣的小伙伴可以点击这里参考,此处我简要给出几点总结:
熟悉Java的同学应该知道在Java7之前是不支持前置直接表示二进制数的,但从7版本之后就可以了:
- public static void main(String[] args) {
- //二进制
- int i = 0B101;
- System.out.println(i); //5
- //八进制
- i = 0101;
- System.out.println(i); //65
- //十进制
- i = 101;
- System.out.println(i); //101
- //十六进制
- i = 0x101;
- System.out.println(i); //257
- }
说明:1、System.out.println()会先自动转为10进制后再输出的;2、Long类型也是有类似的静态方法API的;3、Byte、Short等类型是木有此API的
JDK自1.0开始便提供了非常便捷的进制转换的API,这在我们有需要时非常有用。
- public static void main(String[] args) {
- int i = 192;
- System.out.println("---------------------------------");
- System.out.println("十进制转二进制:" + Integer.toBinaryString(i)); //11000000
- System.out.println("十进制转八进制:" + Integer.toOctalString(i)); //300
- System.out.println("十进制转十六进制:" + Integer.toHexString(i)); //c0
- System.out.println("---------------------------------");
- // 统一利用的为Integer的valueOf()方法,parseInt方法也是ok的
- System.out.println("二进制转十进制:" + Integer.valueOf("11000000", 2).toString()); //192
- System.out.println("八进制转十进制:" + Integer.valueOf("300", 8).toString()); //192
- System.out.println("十六进制转十进制:" + Integer.valueOf("c0", 16).toString()); //192
- System.out.println("---------------------------------");
- }
其实最简单的方式便是:我们看看Long类型的最大值,用2进制表示转换成字符串看看长度就行了
- public static void main(String[] args) {
- long l = 100L;
- //如果不是最大值 前面都是0 输出的时候就不会有那么长了(所以下面使用最大/最小值示例)
- System.out.println(Long.toBinaryString(l)); //1100100
- System.out.println(Long.toBinaryString(l).length()); //7
-
- System.out.println("---------------------------------------");
-
- l = Long.MAX_VALUE; // 2的63次方 - 1
- //正数长度为63为(首位为符号位,0代表正数,省略了所以长度是63)
- //111111111111111111111111111111111111111111111111111111111111111
- System.out.println(Long.toBinaryString(l));
- System.out.println(Long.toBinaryString(l).length()); //63
-
- System.out.println("---------------------------------------");
-
- l = Long.MIN_VALUE; // -2的63次方
- //负数长度为64位(首位为符号位,1代表负数)
- //1000000000000000000000000000000000000000000000000000000000000000
- System.out.println(Long.toBinaryString(l));
- System.out.println(Long.toBinaryString(l).length()); //64
- }
提示:1、在计算机中,负数以其正值的补码形式表达,方法为其绝对值求反加1;2、用同样方法可以看出Integer类型是占用32位(4个字节)
Java语言支持的位运算符还是非常多的,列出如下:
&
:按位与。|
:按位或。~
:按位非。^
:按位异或。<<
:左位移运算符。>>
:右位移运算符。>>>
:无符号右移运算符。除~
以 外,其余均为二元运算符,操作的数据只能是整型(长短均可)/字符型。
操作规则:仅当两个操作数都为1时,输出结果才为1。否则为0
说明:1、本示例(下同)中所有的字面值使用的都是十进制表示的,理解的时候请用二进制思维去理解;2、关于负数之间的位运算本文章统一不做讲述
- public static void main(String[] args) {
- // 2 -> 10
- // 3 -> 11
- // 与后结果:10(二进制数)
- System.out.println(Integer.toBinaryString(2 & 3));
- }
操作规则:仅当两个操作数都为0时,输出的结果才为0。
- public static void main(String[] args) {
- // 2 -> 10
- // 3 -> 11
- // 或后结果:11(二进制数)
- System.out.println(Integer.toBinaryString(2 | 3));
- }
操作规则:全部的0置为1,1置为0。
- public static void main(String[] args) {
- // 2 -> 10(其实是00000000000000000000000000000010 共32位)
- // 非后结果: 11111111111111111111111111111101 共32位
- System.out.println(Integer.toBinaryString(~2));
- }
可以看到取非的结果像是“面目全非”的赶脚,因此使用时需要谨慎。
操作规则:操作数不同时(1遇上0,0遇上1)对应的输出结果才为1,否则为0。
- public static void main(String[] args) {
- // 2 -> 10
- // 3 -> 11
- // 异或后结果:10(二进制数)
- System.out.println(Integer.toBinaryString(2 ^ 3));
- }
操作规则:把一个数的全部位数都向左移动若干位。
- public static void main(String[] args) {
- // 2 -> 10
- // 左移3位结果:10000(二进制数)
- System.out.println(Integer.toBinaryString(2 << 3));
- }
左移用得非常多,也非常好理解。x左移多少位,效果同十进制里直接乘以2的多少次方就行了,但是需要注意值溢出的情况~
操作规则:把一个数的全部位数都向右移动若干位。
- public static void main(String[] args) {
- // 2 -> 10
- // 右移3位结果:0(二进制数)
- // 位数不够全被移没了,所以最终打印0
- System.out.println(Integer.toBinaryString(2 >> 3));
-
- // 100 -> 1100100
- // 右移3位结果:1100
- System.out.println(Integer.toBinaryString(100 >> 3));
- }
右移用得也很多,操作其实就是吧右边的N位直接砍掉即可
注意:并没有
<<<
这个符号的哟~~~
正数做>>>
运算的时候和>>
是一样的。区别在于负数运算
这里指的复合运算指的就是和=号一起来使用,类似于+= -=
等。本来这属于常识不用单独解释,但因有好几个小伙伴问过了,所以在此处顺带的介绍下吧:
- public static void main(String[] args) {
- // 2 -> 10
- // 3 -> 11
- // 与后结果:10(二进制数)
- int i = 2;
- i &= 3; // 此效果同 i = i & 3
- System.out.println(Integer.toBinaryString(i)); //打印:10
- }
位运算不仅有高效的特点,还有一个非常非常的大特点:计算的可逆性。通过这个特点我们可以用来达到隐蔽数据的效果(后面有示例),并且还保证了效率。
在JDK的原码中。有很多初始值都是通过位运算计算的。位运算有很多优良特性,能够在线性增长的数据中起到作用。且对于一些运算,位运算是最直接、最简便的方法。
在十进制数中可以通过和2取余来可以达到效果,对于位运算有一个更为高效的方式:
- public static void main(String[] args) {
- System.out.println(isEvenNum(1)); //false
- System.out.println(isEvenNum(2)); //true
- System.out.println(isEvenNum(3)); //false
- System.out.println(isEvenNum(4)); //true
- System.out.println(isEvenNum(5)); //false
- }
- private static boolean isEvenNum(int n) {
- // 1 -> 1(二进制表示。所以它的前31位都是0哦~~~)
- return (n & 1) != 1;
- }
为何&1能判断基偶性?因为在二进制下偶数的末位肯定是0,so奇数的最低位肯定是1。
而二进制的1它的前31位均为0,所以在和其它数字的前31位与运算后肯定所有位数都是0(无论是1&0还是0&0结果都是0),那么唯一区别就是看最低位和1进行与运算的结果喽:结果为1表示奇数,反则结果为0表示偶数
这是个经典面试题,题目本来很简单,但是加上了不借助第三方变量这个条件后就会难倒一大片了。其实它会有两种方案,这里我都展示出来:
方式一:传统方式
- public static void main(String[] args) {
- int a = 3, b = 5;
- System.out.println(a + "-------" + b);
- a = a + b;
- b = a - b;
- a = a - b;
- System.out.println(a + "-------" + b);
- }
使用这种方式的好处是容易理解,坏处是:a+b,可能会超出int型的最大范围,造成精度丢失导致错误,所以生产环境强烈建议采用下面的方式二。
方式二:位运算方式
- public static void main(String[] args) {
- // 这里使用最大值演示,以证明这样方式是不会溢出的
- int a = Integer.MAX_VALUE, b = Integer.MAX_VALUE - 10;
- System.out.println(a + "-------" + b); // 2147483647-------2147483637
- a = a ^ b;
- b = a ^ b;
- a = a ^ b;
- System.out.println(a + "-------" + b); // 2147483637-------2147483647
- }
它的根本原理就是利用了位运算的可逆性,使用异或运算来操作。
业务系统中数据库设计的尴尬现象:通常 我们的数据表中 可能会包含各种状态属性, 例如 blog表中,我们需要有字段表示其是否公开,是否有设置密码,是否被管理员封锁,是否被置顶等等。 也会遇到在后期运维中,策划要求增加新的功能而造成你需要增加新的字段,这样会造成后期的维护困难,数据库增大,索引增大的情况, 这时使用位运算就可以巧妙的解决。
说明:1、MySql是支持这些位运算符的;2、这种方式不一定适合所有场景,因为它会导致索引失效(不过状态值一般也不需要索引),所以具体问题需具体分析
其实移位运算玩法比较像Linux里的权限控制:权限分为 r 读, w 写, x 执行,其中 它们的权值分别为4,2,1, 所以 如果用户要想拥有这三个权限 就必须 chomd 7 , 即 7=4+2+1 表明 这个用户具有rwx权限,如果只想这个用户具有r,x权限 那么就 chomd 5即可。
生成订单流水号,当然这其实这并不是一个很难的功能,最直接的方式就是日期+主机Id+随机字符串来拼接一个流水号,但是今天有个我认为比较优雅方式来实现。什么叫优雅:可以参考淘宝、京东的订单号,看似有规律,其实没规律:
此流水号构成:日期+Long类型的值 组成的一个一长串数字,形如2020010419492195304210432。很显然前面是日期数据,后面的一长串就蕴含了不少的含义:当前秒数、商家ID(也可以是你其余的业务数据)、机器ID、一串随机码等等
各部分介绍:
Tips:此源码为本人自己编写,自测了多种情况,若各位使用中有更好的建议,欢迎留言
- /**
- * 通过移位算法 生成流水号
- * <p>
- * --> 通用版本(其实各位可以针对具体场景 给出定制化版本 没关系的)
- * (最直接的方式就是日期+主机Id+随机字符串来拼接一个流水号)
- *
- * @author yourBatman
- */
- public class SerialNumberUtil {
-
- //采用long值存储 一共63位
- private static final int BIT_COUNT = 63;
- //各个部分占的最大位数(为了减轻负担,时分秒都放到前面去 不要占用long的位数了 但是毫秒我隐藏起来,方便查问题)
- //毫秒值最大为999(1111100111)占10位
- private static final int SHIFTS_FOR_MILLS = 10;
- //下面是各部分的业务位数(各位根据自己不同的业务需求 自己定制)
- //serviceType占位
- private static final int SHIFTS_FOR_SERVICETYPE = 5;
- //shortParam占位
- private static final int SHIFTS_FOR_SHORTPARAM = 5;
- private static final int SHIFTS_FOR_LONGPARAM = 30;
-
- ///
- //最后的随机数 占满剩余位数
- private static final int SHIFTS_FOR_RANDOMNUM = BIT_COUNT - SHIFTS_FOR_MILLS
- - SHIFTS_FOR_SERVICETYPE - SHIFTS_FOR_SHORTPARAM - SHIFTS_FOR_LONGPARAM;
-
-
- //掩码 用于辅助萃取出数据 此技巧特别巧妙
- private static final long MASK_FOR_MILLS = (1 << SHIFTS_FOR_MILLS) - 1;
- private static final long MASK_FOR_SERVICETYPE = (1 << SHIFTS_FOR_SERVICETYPE) - 1;
- private static final long MASK_FOR_SHORTPARAM = (1 << SHIFTS_FOR_SHORTPARAM) - 1;
- private static final long MASK_FOR_LONGPARAM = (1 << SHIFTS_FOR_LONGPARAM) - 1;
-
- //时间模版
- private static final String DATE_PATTERN = "yyyyMMddHHmmss";
-
- /**
- * 生成流水号 若需要隐藏跟多的参数进来,可以加传参。如订单类型(订单id就没啥必要了)等等
- *
- * @param serviceType 业务类型,比如订单号、消费流水号、操作流水号等等 请保持一个公司内不要重复
- * 最大值:30(11110) 占5位
- * @param shortParam 短参数 不具体定义什么 一般用于表示类型。如这表示订单流水号,这里可以表示订单类型
- * 最大值:30(11110) 占5位
- * @param longParam 长参数,一般用于记录id参数什么的,比如是订单的话,这里可以表示商户ID(商户一般不会非常多吧)
- * 最大值:999999999(101111101011110000011111111) 占30位 表示9.999亿的数据 相信作为id的话,一般都超不过这个数值吧
- * @return 流水号 年月日时分秒+long类型的数字 = string串
- */
- public static String genSerialNum(long serviceType, long shortParam, long longParam) {
- if (serviceType > 30) {
- throw new RuntimeException("the max value of 'serviceType' is 30");
- }
- if (shortParam > 30) {
- throw new RuntimeException("the max value of 'shortParam' is 30");
- }
- if (longParam > 99999999) {
- throw new RuntimeException("the max value of 'longParam' is 99999999");
- }
-
- //放置毫秒值
- long mills = LocalTime.now().getNano() / 1000000; //备注 此处一定要是long类型 否则会按照int的32位去移位
- long millsShift = mills << (BIT_COUNT - SHIFTS_FOR_MILLS);
-
- //放置serviceType
- long serviceTypeShift = serviceType << (BIT_COUNT - SHIFTS_FOR_MILLS - SHIFTS_FOR_SERVICETYPE);
-
- //放置shortParam
- long shortParamShift = shortParam << (BIT_COUNT - SHIFTS_FOR_MILLS - SHIFTS_FOR_SERVICETYPE - SHIFTS_FOR_SHORTPARAM);
-
- //放置longParam
- long longParamShift = longParam << (BIT_COUNT - SHIFTS_FOR_MILLS - SHIFTS_FOR_SERVICETYPE - SHIFTS_FOR_SHORTPARAM - SHIFTS_FOR_LONGPARAM);
-
- //生成一个指定位数(二进制位数)的随机数 最后一个 不需要左移了 因为长度就是自己
- long randomShift = getBinaryRandom(SHIFTS_FOR_RANDOMNUM);
-
- //拼接各个部分
- long finalNum = millsShift | serviceTypeShift | shortParamShift | longParamShift | randomShift;
-
- //最后前面拼接上年月日时分秒 返回出去
- return LocalDateTime.now().format(DateTimeFormatter.ofPattern(DATE_PATTERN)) + finalNum;
- }
-
- /**
- * 拿到指定位数的 首位数字不为0的位数,最终以十进制数返回出来
- *
- * @param count 需要的总位数 总位数不允许超过63
- * @return binary random
- */
- private static long getBinaryRandom(int count) {
- StringBuffer sb = new StringBuffer();
- String str = "01";
-
- //采用ThreadLocalRandom 生成随机数 避免多线程问题
- ThreadLocalRandom r = ThreadLocalRandom.current();
- for (int i = 0; i < count; i++) {
- int num = r.nextInt(str.length());
- char c = str.charAt(num);
- while (c == '0') { //确保第一个是不为0数字 否则一直循环去获取
- if (i != 0) {
- break;
- } else {
- num = r.nextInt(str.length());
- c = str.charAt(num);
- }
- }
- sb.append(c);
- }
- return Long.valueOf(sb.toString(), 2);
- }
-
- //===============================提供便捷获取各个部分的工具方法===================================
-
- /**
- * 从序列号拿到日期 并且格式化为LocalDateTime格式
- *
- * @param serialNumber 流水号
- * @return 日期时间
- */
- public static LocalDateTime getDate(String serialNumber) {
- String dateStr = serialNumber.substring(0, DATE_PATTERN.length());
- return LocalDateTime.parse(dateStr, DateTimeFormatter.ofPattern(DATE_PATTERN));
- }
-
- /**
- * 拿到毫秒数:是多少毫秒
- *
- * @param serialNumber 流水号
- * @return 毫秒数
- */
- public static long getMills(String serialNumber) {
- return getLongSerialNumber(serialNumber) >> (BIT_COUNT - SHIFTS_FOR_MILLS) & MASK_FOR_MILLS;
- }
-
- /**
- * 拿到 serviceType
- *
- * @param serialNumber 流水号
- * @return serviceType
- */
- public static long getServiceType(String serialNumber) {
- return getLongSerialNumber(serialNumber) >> (BIT_COUNT - SHIFTS_FOR_MILLS - SHIFTS_FOR_SERVICETYPE) & MASK_FOR_SERVICETYPE;
- }
-
- /**
- * 拿到 shortParam
- *
- * @param serialNumber 流水号
- * @return shortParam
- */
- public static long getShortParam(String serialNumber) {
- return getLongSerialNumber(serialNumber) >> (BIT_COUNT - SHIFTS_FOR_MILLS - SHIFTS_FOR_SERVICETYPE - SHIFTS_FOR_SHORTPARAM) & MASK_FOR_SHORTPARAM;
- }
-
- /**
- * 拿到 longParam
- *
- * @param serialNumber 流水号
- * @return longParam
- */
- public static long getLongParam(String serialNumber) {
- return getLongSerialNumber(serialNumber) >> (BIT_COUNT - SHIFTS_FOR_MILLS - SHIFTS_FOR_SERVICETYPE - SHIFTS_FOR_SHORTPARAM - SHIFTS_FOR_LONGPARAM) & MASK_FOR_LONGPARAM;
- }
-
-
- //把日期前缀去掉
- private static long getLongSerialNumber(String serialNumber) {
- return Long.parseLong(serialNumber.substring(DATE_PATTERN.length()));
- }
-
- //==================================================================
-
- /**
- * 提供测试的Main方法
- *
- * @param args the input arguments
- */
- public static void main(String[] args) {
- String serialNum = genSerialNum(1, 2, 300);
- System.out.println(serialNum); //20181121173040299068801480344
-
- //拿long型的值
- System.out.println(getLongSerialNumber(serialNum)); //299068801480344
- System.out.println(Long.toBinaryString(getLongSerialNumber(serialNum)));
-
- //拿到日期时间
- System.out.println(getDate(serialNum)); //2018-11-21T17:30:40
-
- //拿毫秒值
- System.out.println((LocalTime.now().getNano() / 1000000));
- System.out.println(getMills(serialNum));
-
- //拿到serviceType
- System.out.println(getServiceType(serialNum)); //1
-
- //拿到shortParam
- System.out.println(getShortParam(serialNum)); //2
-
- //拿到longParam
- System.out.println(getLongParam(serialNum)); //300
- }
- }
到这里Java中的位运算这块就算聊完。在实际工作中,如果只是为了数字的计算(不是运算),是不建议使用位运算符的,毕竟人能读懂比机器能读懂更重要。在一些特殊的场景:比如N多状态的控制、对效率有极致要求的情况下,或许位运算能给与你帮助,所以希望此文能帮助到你,这边是它最大的意义~
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。