写在文章开头

众所周知位运算执行效率高于常规运算，通过不同的位运算搭配可以让我们写出简洁高效的表达代码的语义，所以本文将基于java主流开源项目的源码中介绍一下各类运算技巧及其使用场景。

我是 SharkChili ，Java 开发者，Java Guide 开源项目维护者。欢迎关注我的公众号：写代码的SharkChili，也欢迎您了解我的开源项目 mini-redis：https://github.com/shark-ctrl/mini-redis (opens new window)。

为方便与读者交流，现已创建读者群。关注上方公众号获取我的联系方式，添加时备注加群即可加入。

详解位运算技巧

移位运算实现高效计算

移位运算从工作的角度来看就是直接将所有位置的数字简单移动x位，这个x就是我们要移动的位数，假设我们二进制数2，对应二进制就是0010，通过移位运算<<1得到的结果就是4，不难看出移位运算移动x位，就相当于乘2x的数学运算，同理右移运算就相当于除法，这里就不多做赘述了：

这种运算技巧笔者在线程池配置中是比较常用，例如我们需要配置一个IO密集型任务的线程池，对应的线程池最大数一般都是配置CPU核心数的2倍，而不同的服务器的CPU核心数不同，我们一般都是通过获取核心数然后进行乘2，此时我们完全就可以通过左移运算符完成这种逻辑运算：

@Bean("ioThreadPool")
    public ThreadPoolExecutor ioThreadPool() {

        ThreadPoolExecutor threadPoolExecutor = new ThreadPoolExecutor(
                Runtime.getRuntime().availableProcessors(),
                //通过位运算计算线程池最大数
                Runtime.getRuntime().availableProcessors()<<1,
                60,
                TimeUnit.SECONDS,
                new ArrayBlockingQueue<>(200),
                ThreadFactoryBuilder.create().setNamePrefix("worker-").build(),
                new ThreadPoolExecutor.CallerRunsPolicy());
        return threadPoolExecutor;
    }

按位与和移位运算结合的效果

按位与运算只有两个bit都为1的情况下才为1，如下所示2和7的按位与运算，只有低2位的bit都是1，所以最终的与运算只保留这一位，最终的结果就是2：

这里笔者给出一个比较经典的例子，假设我们的功能支持在8点到10点才能运行，我们希望能够判断当前时间是否是工作时间，这时候我们可以使用3个字节的byte做到这一点，我们使用24 个bit，自左向右为0~23点。

假设当前时间是8点，那么我们就可以自作向右将第8个bit设置为1，按照也就是自右向左的第16位，由此得出左移的位置为16，即需要左移15位也就是<<15，由此得出不同时间点的移动位数为1<<(23-当前时间)，于是就有了下面这样一个按位与和移位运算的综合示例：

最终我们就有了下面这一段代码：

public static void main(String[] args) {
        //时间二进制转整数
        int timeBit = Integer.parseInt("000000001111100000000000", 2);

        for (int i = 0; i < 23; i++) {
            //当前时间
            int curTimeBit = (1 << (23 - i));
            //按位与
            if ((curTimeBit & timeBit) > 0) {
                log.info("{}:位于工作时间", i);
            }
        }
    }

对应输出结果如下：

22:37:34.599 [main] INFO com.sharkchili.Main - 8:位于工作时间
22:37:34.602 [main] INFO com.sharkchili.Main - 9:位于工作时间
22:37:34.602 [main] INFO com.sharkchili.Main - 10:位于工作时间
22:37:34.602 [main] INFO com.sharkchili.Main - 11:位于工作时间
22:37:34.602 [main] INFO com.sharkchili.Main - 12:位于工作时间

按位或高效统计

在二进制运算之中，按位或运算只要是1个bit上为1，那么运算结果就为1，如下图所示，可以看到2的二进制数和1的二进制数的按位或运算结果就是3

这一技巧在JDK6版本的FutureTask中的任务状态就有着非常经典的用法，当我们需要取消FutureTask执行时就会调用cancel方法，其内部的AQS队列会判断当前任务状态是否为运行完成RAN(值为2)或者已取消CANCELLED(值为4)，如果符合其中一种情况则不允许取消任务。

按照我们常规的写法，最终的写法可能是这样：

//判断是否可以取消任务
private boolean ranOrCancelled(int state) {
			//如果状态为运行完成或者取消则返回false，不允许当前线程打断任务
            if (state == RAN || state == CANCELLED) {
                return true;
            }
            return false;
  }

但是Doug Lea不是这样做的，它用到了更加高效的位运算，接下来笔者就对此进行逐步推理：

1. 由上文可知RAN的值为2，CANCELLED的值为4，对应的是二进制的低二位。
2. 通过或运算，将这两个状态的值拼接起来，构成0110。
3. 我们希望判断当前状态是否符合其中的一种情况，实际上就可以通过按位与运算，只要我们状态的二进制值和0110相与大于0就说明符合其中某种状态

于是最终的位运算代码就变成了这样，可以看到作者先通过按位与拼接所有要判断的状态值，然后通过按位与判断是否符合其中一种情况，如果不为0说明命令某种状态，返回true：

 private boolean ranOrCancelled(int state) {
            return (state & (RAN | CANCELLED)) != 0;
        }

逻辑或简化if-else

逻辑或运算也是一个比较常用的运算符，它的工作原理是碰到一个运算结果为true则直接短路，不再进行后续的逻辑判断。 即if(表达式1||表达式2)，如果表达式1为true，那么直接返回不再进行表达式2的计算。反之如果表达式1为false，则继续进行表达式2的计算：

这其中最经典的使用场景就是ConcurrentSkipListMap的putIfAbsent逻辑，这个方法会判断当前key是否存在，如果不存在才进行put操作：

new ConcurrentSkipListMap<>().putIfAbsent("key", "value");

而putIfAbsent和put方法底层都服用了putVal方法，只不过putIfAbsent的onlyIfAbsent传的是true，而put是false，所以后者遇到相同的key会覆盖value。 于是当HashMap进行put操作时遇到相同key时，就会有这样的逻辑：

1. 如果onlyIfAbsent为false，说明是put操作，直接通过CAS原子操作覆盖掉value，如果失败则继续循环进行CAS操作。
2. 如果onlyIfAbsent为true，则说明则说明是putIfAbsent，不进行修改直接返回当前map中的value。

假设我们现在就需要编写这样一段逻辑，我们的写法可能是这样：

//如果设置空才允许插入则直接返回原值
                        if (onlyIfAbsent) {
                            @SuppressWarnings("unchecked") V vv = (V) v;
                            return vv;
                        } else if (n.casValue(v, value)) {//反之就是put逻辑，直接原子修改然后返回修改后的v的值
                            @SuppressWarnings("unchecked") V vv = (V) v;
                            return vv;
                        }

实际上这种看看第一段逻辑是否为true，若不为true则进行第二段的逻辑完全可以通过本小节所提及的逻辑或运算：

//如果onlyIfAbsent为true则说明只有key为空情况下才可赋值，不执行后续逻辑直接返回map中的vv
//反之进行原子操作然后将修改后的vv返回
 if (onlyIfAbsent || n.casValue(v, value)) {
         @SuppressWarnings("unchecked") V vv = (V)v;
           return vv;
}
                    
                    

同理我们再给出这样一个例子演示一下笔者的重构思路，在著名的java度量框架micrometer中有一个非常实用的timer计时器，其底层有个时间窗口工具，它会并发传入最新的样本值sample和我们当前维护的原子类max进行比对，对应逻辑为：

1. 如果max大于sample，则直接返回
2. 如果max小于sample，则通过cas的方式将其修改为sample，因为可能涉及并发更新原子类，所以失败后就必须重新拉取原子类的最新值进行比对，明确sample依然大于这个值才能进行更新。

于是我们就可以编写出下面这样一段代码：

private void updateMax(AtomicLong max, long sample) {
        long curMax = max.get();
        //传入sample小于当前维护的原子类直接返回
        if (curMax >= sample) {
            return;
        }
        //sample大于当前维护的max则不断cas,若失败则比对再进行cas
        for (; ; ) {
            //cas成功则直接返回
            if (max.compareAndSet(curMax, sample)) {
                break;
            }
            //cas失败则重新获取max,进行比对
            curMax = max.get();
            if (curMax >= sample) {
                break;
            }
        }
    }

我们先来第一步重构吧，review一下这段代码，可以发现代码稍显啰嗦，循环上下都涉及sample的比对，稍加思索，我们就可以发现将循环内部的sample比对逻辑移除，同时直接将循环上方的比对逻辑直接放到循环内部。 这样一来比对逻辑和循环cas并发更新都共享一段比对逻辑：

 private void updateMax(AtomicLong max, long sample) {
        
        
        //sample大于当前维护的max则不断cas,若失败则比对再进行cas
        for (; ; ) {
            long curMax = max.get();
            //传入sample小于当前维护的原子类直接返回
            if (curMax >= sample) {
                break;
            }
            //cas成功则直接返回
            if (max.compareAndSet(curMax, sample)) {
                break;
            }
        }
    }

结合这段逻辑，我们发现这段逻辑本质上就是：

1. 比对sample小于max直接结束，反之进入步骤2
2. cas更新，若成功则结束循环，反之继续循环回到步骤1

这本质上就是通过短路运算符精简这段逻辑，确保比对逻辑可以复用的情况下，通过短路运算符保证将两端逻辑合并到一个if分支上，以简化代码：

private void updateMax(AtomicLong max, long sample) {


        for (; ; ) {
            long curMax = max.get();
            //若sample小于max则直接短路结束循环,反之cas尝试更新max的值
            if (curMax >= sample || max.compareAndSet(curMax, sample)) {
                break;
            }

        }
    }

逻辑与运算短路特性的运用

和逻辑或有所不同，逻辑与运算必须两者都为true才能返回true，这意味着即使第一个表达式为true，第二个表达式依然会参与运算。反之如果第一个表达式为false，第二个表达式就没有计算的必要了：

这其中比较经典的用法就是FutureTask源码中cancel方法的运用，它的逻辑是FutureTask状态必须为NEW的情况下，才能进行CAS状态修改，按照常规的写法，我们可能会这样写：

//如果状态为new
        if (state==NEW){
            //使用CAS将状态修改为中断态，如果失败则返回false
            if (!UNSAFE.compareAndSwapInt(this, stateOffset, NEW,
                    mayInterruptIfRunning ? INTERRUPTING : CANCELLED)){
                return false;
            }
        }

这明显这种if条件1为true，就执行条件2并查看条件2执行结果的逻辑进行后续逻辑处理的我们完全可以通过逻辑与运算替代：

 if (!(state == NEW &&
                UNSAFE.compareAndSwapInt(this, stateOffset, NEW,
                        mayInterruptIfRunning ? INTERRUPTING : CANCELLED)))
            return false;

Netty中按位与实现复杂均衡算法

为了保证线程的公平调度，我们通常会采用轮询算法，假设我们有8个线程，按照轮询算法一次调用顺序为：线程0、线程1 ........线程7，然后才从线程0开始：

按照正常的写法，我们可以通过原子类进行递增，然后和线程数进行取模运算即可获取到当前事件通过那个线程执行：

假设我们的计算的值来到16，按照取模算法它对应的索引为0，此时新来一个事件需要线程处理，于是原子类原子自增1得到17，通过取模运算最终得到索引1：

对应的源码实现实现如下：

//原子子类记录当前索引值
private final AtomicLong idx = new AtomicLong();

 @Override
        public EventExecutor next() {
        	//idx自增和线程长度进行取模
            return executors[(int) Math.abs(idx.getAndIncrement() % executors.length)];
        }

取模运算的性能表现明显是没有位运算出色的，所以Netty提出了一种更加高效的方案，即当线程数为2的次幂时，通过原子类自增和线程数-1进行按位与运算。 举个例子，假设当前索引值还是16，也就是的4次方，换算成2进制就是10000，然后2的次幂减去1即可得到小于2的次幂且低位全为1的二进制1111，这样一来我们idx无论怎么变化和这个减去1后的结果都会得到1个小于2的次幂，这个值永远小于等于线程索引。 所以索引16&15=0，当自增到17时得到的结果也很上文一样为1：

最终我们就得到了这样一个负载均衡算法：

 @Override
        public EventExecutor next() {
            return executors[idx.getAndIncrement() & executors.length - 1];
        }

小结

本文针对日常的如下几种情况:

1. 逻辑判断
2. 状态标识确认
3. 多if-else分支

通过逻辑梳理和层层递进推导得出一条条简洁暴露的位运算表达式使得代码逻辑和执行更加高效且具备张力，希望对你有帮助。

我是 SharkChili ，Java 开发者，Java Guide 开源项目维护者。欢迎关注我的公众号：写代码的SharkChili，也欢迎您了解我的开源项目 mini-redis：https://github.com/shark-ctrl/mini-redis (opens new window)。

为方便与读者交流，现已创建读者群。关注上方公众号获取我的联系方式，添加时备注加群即可加入。