取模算法优化

在需要循环使用一定范围内的数的时候，常常会用到取模，例如环形队列。本文说一个在cpu层面的性能优化方法，大幅度提高计算效率，但只是适用于特定条件下。

优化方案： 采用**&**运算，但是模数必须是2的次幂，例如2、4、8、16、32等。

**数学原理：**当模数 n 是 2 的幂（如 n = 2^k），对任意整数 x 的取模运算 x % n 可以用位与运算 x & (n-1) 替代。

性能对比：

取模运算（%）	位与运算（&）
是 CPU 的原生操作，执行速度极快，通常只需一个时钟周期。	涉及除法操作，CPU 执行除法通常需要多个时钟周期。

实测性能： 在 Java 中，位与运算的性能通常比取模运算快 5-10 倍，尤其在高频调用场景下（如锁索引计算）。

应用场景案例（分段锁）：

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 分段锁
 */
public class SegmentLock {

    private final int mask;
    private final Lock[] locks;
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    public SegmentLock(int concurrency) {
        //格式化为2的次幂
        int size = formatSize(concurrency);
        mask = size - 1;
        locks = new Lock[size];
        for (int i = 0; i < size; i++) {
            locks[i] = new ReentrantLock();
        }
    }

    /**
     * 阻塞获取锁，可被打断
     * @param lockId 锁ID
     * @throws InterruptedException 线程被中断异常
     */
    public void lockInterruptible(int lockId) throws InterruptedException {
        Lock lock = locks[lockId & mask];
        lock.lockInterruptibly();
    }

    public void lockInterruptibleSafe(int lockId) {
        try {
            lockInterruptible(lockId);
        }catch (InterruptedException ignore) {
        }
    }

    /**
     * 释放锁
     * @param lockId 锁ID
     */
    public void unlock(int lockId) {
        Lock lock = locks[lockId & mask];
        lock.unlock();
    }
    /**
     * 将大小格式化为 2的N次
     * @param cap 初始大小
     * @return 格式化后的大小，2的N次
     */
    private  int formatSize(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
}