如何仅用移位、位与、位或等位运算判断数字是否为100的倍数？

当然有可行的方案！咱们可以从100的因数分解入手——100 = 4 × 25，这两个数互质，所以只要一个数同时满足是4的倍数和25的倍数，那它必然是100的倍数。接下来我们用纯位运算（移位、位与、位或等）分别实现这两个判断逻辑：

1. 判断是否为4的倍数 #

4是2的幂（2²），一个数是4的倍数的充要条件是它的二进制最后两位为0。用位运算实现非常直接：

• 用n & 0b11（即n & 0x3）提取最后两位
• 如果结果为0，说明是4的倍数

2. 判断是否为25的倍数（核心难点） #

25不是2的幂，没法直接通过末尾二进制位判断，不过我们可以利用模运算的数学性质，结合位运算模拟计算：

思路推导 #

对于任意整数m，我们可以通过移位把它拆分为：m = 256 × a + b（256是2⁸，右移8位就能得到a，b是m & 0xff）。不过更简便的是利用乘法逆元：25和1024（2¹⁰）互质，我们找到一个数41（因为25×41=1025，1025 mod 1024=1），这意味着：

• 如果m是25的倍数，那么m×41的高10位就是m/25的商
• 用这个商乘以25，如果等于原数m，就说明m是25的倍数

位运算实现细节 #

• 乘法m×41可以用移位+加法模拟：41=32+8+1，所以m×41 = (m<<5) + (m<<3) + m
• 右移10位得到商q
• 乘法q×25也用移位+加法模拟：25=16+8+1，所以q×25=(q<<4)+(q<<3)+q
• 比较q×25和m是否相等，相等则是25的倍数

完整代码示例（C语言） #

#include <stdbool.h>

bool isMultipleOf100(unsigned int n) {
    // 第一步：判断是否为4的倍数
    if ((n & 0x3) != 0) {
        return false;
    }
    
    // 因为是4的倍数，右移2位等价于除以4，转化为判断m是否为25的倍数
    unsigned int m = n >> 2;
    
    // 用位运算模拟 m * 41 (41 = 32 + 8 + 1)
    unsigned int m_times_41 = (m << 5) + (m << 3) + m;
    // 右移10位得到商q
    unsigned int q = m_times_41 >> 10;
    
    // 用位运算模拟 q * 25 (25 = 16 + 8 + 1)
    unsigned int q_times_25 = (q << 4) + (q << 3) + q;
    
    // 判断q*25是否等于m，是则m是25的倍数
    return q_times_25 == m;
}

补充说明 #

• 整个过程完全没有使用取模%或除法/，只用到了移位<</>>、位与&、加法（而加法本身可以通过位运算模拟，若需要极致纯位运算，可以替换为位运算实现的加法逻辑）
• 代码针对无符号整数编写，若要支持有符号整数，只需在开头判断符号（负数的话先取绝对值，再判断）

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