如何针对4、9、20等多除数优化模运算代码？

当然有可行方案，但得分情况讨论——不是所有除数都能像2那样用简单的按位与&直接替代，但针对不同类型的除数，有对应的位运算优化思路：

1. 除数是2的幂次（比如4、8、16这类） #

和判断偶数的逻辑完全一致，这类除数可以直接用**按位与&**优化模运算。
比如除数是4（2²），判断i是否被4整除，等价于i & 3 == 0——因为4的二进制是100，4-1=3的二进制是11，按位与后得到的结果就是i模4的余数，余数为0则说明能被整除。
同理，除数是8的话，用i & 7 == 0即可判断整除。

代码示例：

// 替代原来的if(i%4==0)
if((i & 3) == 0) {
    System.out.println("divisible by 4");
} else {
    System.out.println("not divisible by 4");
}

2. 除数是非2的幂次（比如9、20、56这类） #

这类除数没法用简单的按位与直接替代，但可以用乘法+移位的方式优化——利用CPU执行乘法、移位指令比除法/模运算更快的特性，提前计算对应除数的常数，把模运算转化为乘法和移位操作。

核心原理 #

对于除数d，我们可以找到一个足够大的常数M和移位量s，使得(M * i) >> s的结果等于i / d的商，然后通过i - 商 * d得到模d的余数；如果只是判断是否整除，只要验证余数是否为0即可。

举几个实际例子：

• 除数9：可以用M = 0x1C71C71D，s = 35，计算商的方式是(i * M) >> 35，再用i - 商 * 9得到模9的结果。
• 除数20：20=4*5，先通过i & 3 ==0判断是否被4整除，再对5做乘法移位优化（比如M=0xCCCCCCCD，s=34计算商），两者都满足则能被20整除。
• 除数56：56=8*7，先通过i &7 ==0判断被8整除，再对7用乘法移位优化（M=0x24924925，s=32计算商），双重验证即可。

代码示例（判断是否被9整除）：

public static boolean isDivisibleBy9(int i) {
    long M = 0x1C71C71DL;
    int quotient = (int) ((i * M) >> 35);
    return (i - quotient * 9) == 0;
}

注意事项 #

• 乘法移位的优化方式需要针对不同的除数、不同的整数类型（有符号/无符号、32位/64位）预计算对应的常数和移位量，这些常数可以通过数学推导得到。
• 部分小除数也有特殊的位运算技巧，比如判断被3整除可以计算二进制各位的和再模3，但这类方法的性能不一定比乘法移位好，需要结合实际场景测试。

内容的提问来源于stack exchange，提问作者user19551207