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

1970-01-01 00:00 (GMT+8) 阅读时间 0 分钟 面试算法位运算TS/JSPython

这道题是小红书上看来的，只有一句话，用位运算判断一个数是否能被 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 的幂次方的话，还是取模运算比较快。

页面历史

最后编辑于 大约 1 个月前

查看完整历史

5459feb-docs: 北美 Amazon Intern 面试