题目描述两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。给你两个整数x和y计算并返回它们之间的汉明距离。示例 1输入x 1, y 4输出2解释1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ 上面的箭头指出了对应二进制位不同的位置。示例 2输入x 3, y 1输出1解题思路方法异或 统计 1 的个数核心思路两个位不同 → 异或结果为 1两个位相同 → 异或结果为 0所以汉明距离 (x ^ y) 的二进制中 1 的个数具体过程示例x 1, y 4x 0001 y 0100 x^y 0101 统计 0101 中 1 的个数 2 ✅代码实现写法1逐位统计暴力法class Solution { public: int hammingDistance(int x, int y) { int xorResult x ^ y; int count 0; while (xorResult 0) { count xorResult 1; // 检查最低位 xorResult 1; // 右移一位 } return count; } };写法2n (n - 1)技巧推荐class Solution { public: int hammingDistance(int x, int y) { int xorResult x ^ y; int count 0; while (xorResult 0) { xorResult (xorResult - 1); // 去掉最低位的 1 count; } return count; } };核心n (n - 1)可以去掉最低位的 1循环次数 1 的个数。写法3用 STL 的__builtin_popcountclass Solution { public: int hammingDistance(int x, int y) { return __builtin_popcount(x ^ y); } };优点一行搞定GCC 内置函数速度快。复杂度分析方法时间复杂度空间复杂度逐位统计O(log n)O(1)n (n-1)O(k)k 是 1 的个数O(1)__builtin_popcountO(1)O(1)n 是 x^y 的值k 是 x^y 中 1 的个数。关键细节1. 为什么用异或异或的性质1 ^ 1 0相同0 ^ 0 0相同1 ^ 0 1不同0 ^ 1 1不同异或结果为 1 的位就是两个数不同的位。2.n (n - 1)为什么能去掉最低位的 1n 1010 n - 1 1001 n (n-1) 1000 ← 最低位的 1 被去掉了原理n - 1会把最低位的 1 变成 0后面的 0 变成 1。与n做与运算最低位的 1 就被消掉了。3.__builtin_popcount是什么GCC 内置函数直接返回一个数二进制中 1 的个数。竞赛中常用。三种方法对比方法时间复杂度空间复杂度推荐度逐位统计O(log n)O(1)⭐⭐⭐n (n-1)O(k)O(1)⭐⭐⭐⭐⭐__builtin_popcountO(1)O(1)⭐⭐⭐⭐总结要点说明核心思想异或后统计 1 的个数关键操作x ^ y找不同位n (n-1)去 1时间复杂度O(k)k 是 1 的个数空间复杂度O(1)