北美 Amazon Intern 面试题：能被 4 整除的数（位运算）

2025-03-18 22:18 (GMT+8) 阅读时间 2 分钟 面试算法位运算TypeScriptPython

这道题是小红书上看来的，只有一句话，用位运算判断一个数是否能被 4 整除。

解题思路

要判断一个数能不能被 4 整除，我们可以找找规律：

• $4_{10}={100}_2$
• $8_{10}={1000}_2$
• ${12}_{10}={1100}_2$
• ${16}_{10}={10000}_2$
• …

观察到所有数字的末尾都是 00，也就是当且仅当一个数的最后两位是 00 时，这个数才能被 4 整除。

因此只要将一个数的二进制表现与 11_2 进行按位与运算，如果结果为 0，则这个数能被 4 整除，否则不能。

代码实现

TypeScript

function solution(n: number): boolean {
  return (n & 3) === 0;
  // 或者
  // return (n & 0b11) === 0;
}

Python

def solution(n: int) -> bool:
    return (n & 3) == 0

类似的，判断能不能被 2 整除就是 (n & 1) === 0，判断能不能被 8 整除就是 (n & 7) === 0。但是这个技巧只能用在判断 2 的幂次方上，如果要判断非 2 的幂次方的话，还是取模运算比较快。