飞道的博客

聊聊Java中的位运算：与、或、非、异或、左移、右移、无符号右移【小家Java】

2020-04-01 15:16 403人阅读  评论(0)

根基不牢，地动山摇

专栏介绍：【享学Jackson】专栏介绍和全部目录大纲

目录

前言

提及位运算，相信对绝大多数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之后就会显示出对应的文字或符号。关于编码的进化史，有兴趣的小伙伴可以点击 这里 参考，此处我简要给出几点总结：

  • 一般对英文字符而言，一个字节表示一个字符，但是对汉字而言，由于低位的编码已经被使用(早期计算机并不支持中文，因此为了扩展支持，唯一的办法就是采用更多的字节数)只好向高位扩展。
  • 字符集编码的范围 utf-8>gbk>iso-8859-1(latin1)>ascll。ascll编码是美国标准信息交换码的英文缩写，包含了常用的字符，如阿拉伯数字，英文字母和一些打印符号共255个。
  • unicode编码包含很多种格式，utf-8是其中最常用的一种。utf-8名称的来自于该编码使用8位一个字节表示一个字符。对于一个汉字而言，它需要3个字节表示一个汉字，但大中华地区人民表示不服，搞一套gbk编码格式，用两个字节表示一个汉字。

Java中的二进制

熟悉Java的同学应该知道在Java7之前是不支持前置直接表示二进制数的，但从7版本之后就可以了：

  • 二进制：前置0b/0B
  • 八进制：前置0
  • 十进制：默认的，无需前置
  • 十六进制：前置0x/0X
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的

Java中便捷的进制转换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是64位的？

其实最简单的方式便是：我们看看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中的位运算

Java语言支持的位运算符还是非常多的，列出如下：

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

除～以 外，其余均为二元运算符，操作的数据只能是整型（长短均可）/字符型。

&：按位与

操作规则：仅当两个操作数都为1时，输出结果才为1，否则为0（相同为1，不同为0）

说明：1、本示例（下同）中所有的字面值使用的都是十进制表示的，理解的时候请用二进制思维去理解；2、关于负数之间的位运算本文章统一不做讲述

public static void main(String[] args) {
    // 2 -> 10
    // 3 -> 11
    // 与后结果：10（二进制数）
    System.out.println(Integer.toBinaryString(2 & 3));
}

|：按位或

操作规则：仅当两个操作数都为0时，输出的结果才为0。（仅需一个是1便是1）

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。（相同为0，不同为1）

public static void main(String[] args) {
    // 2 -> 10
    // 3 -> 11
    // 异或后结果：01（二进制数）
    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+随机字符串来拼接一个流水号，但是今天有个我认为比较优雅方式来实现。什么叫优雅：可以参考淘宝、京东的订单号，看似有规律，其实没规律：

  • 不想把相关信息直接暴露出去。
  • 通过流水号可以快速得到相关业务信息，快速定位问题（这点非常重要）。
  • 使用AtomicInteger可提高并发量，降低了冲突
原理介绍

此流水号构成：日期+Long类型的值 组成的一个一长串数字，形如2020010419492195304210432。很显然前面是日期数据，后面的一长串就蕴含了不少的含义：当前秒数、商家ID（也可以是你其余的业务数据）、机器ID、一串随机码等等

各部分介绍：

  1. 第一部分为当前时间的毫秒值。最大999，所以占10位
  2. 第二部分为：serviceType表示业务类型。比如订单号、操作流水号、消费流水号等等。最大值定为30，足够用了吧。占5位
  3. 第三部分为：shortParam，表示用户自定义的短参数。可以放置比如订单类型、操作类型等等类别参数。最大值定为30，肯定也是足够用了的。占5位
  4. 第四部分为：longParam，同上。用户一般可防止id参数，如用户id、商家id等等，最大支持9.9999亿。绝大多数足够用了，占30位
  5. 第五部分：剩余的位数交给随机数，随机生成一个数，占满剩余位数。一般至少有15位剩余，所以能支持2的15次方的并发，也是足够用了的
  6. 最后，在上面的long值前面加上日期时间（年月日时分秒）
上源码

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多状态的控制、对效率有极致要求的情况下，或许位运算能给与你帮助，所以希望此文能帮助到你，这边是它最大的意义~

当然，若你有些自己的想法或者对本文感兴趣，可以私信我 or 左边扫码加我好友来一起探讨和交流学习，共同进步。

声明

原创不易，码字不易，多谢你的点赞、收藏、关注。把本文分享到你的朋友圈是被允许的，但拒绝抄袭。你也可左边扫码加入我的 Java高工、架构师 系列群大家庭学习和交流。


转载：https://blog.csdn.net/f641385712/article/details/103824846
查看评论
* 以上用户言论只代表其个人观点，不代表本网站的观点或立场