当前位置：首页 > news >正文

Leetcode 10 java

news 2025/8/2 8:06:18

算法题康复训练，算法还是很弱很弱的我...挑一道easy并且通过率高一点的题目吧！

1 题目

461. 汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)↑   ↑
上面的箭头指出了对应二进制位不同的位置。

示例 2：

输入：x = 3, y = 1
输出：1

提示：

0 <= x, y <= 231 - 1

注意：本题与 2220. 转换数字的最少位翻转次数相同。

2 我的想法：

首先，用 B 强制转换成2进制的数，（或者是要用那个辗转相除法？），总之把结果输出变成2进制只有01的数，然后一一比对，这个比较的过程是不是时间复杂度和空间复杂度太高了，我想到的是输出的2进制数存成数组，len找出大的那个，然后一个一个比。或者还有别的方法吗？直接位运算，加入一个i作为循环计数，如果异或就加一。或者hashmap吗，哈希表来判断？我不清楚到底怎么写，我只有这点想法。

3 对现有思路的分析

你的思路方向是对的，尤其是提到 “位运算” 的部分，其实这道题用位运算可以非常高效地解决。我们来详细分析一下你的想法，并梳理出最优解法：

二进制转换后比对
你的第一个想法（转二进制后存数组比对）是可行的，但确实存在优化空间：
- 转换过程（无论是bin()函数还是辗转相除法）本身需要额外时间，不过对这道题来说影响不大（因为整数范围有限）。
- 比对时需要处理两个二进制数长度不一致的情况（比如补前导 0），实现起来稍显繁琐，但逻辑直观。
位运算思路
你提到 “异或就加一”，这其实已经触碰到了最优解的核心！汉明距离的定义是 “二进制位不同的位置数目”，而异或运算的特性正是：相同位为 0，不同位为 1。因此，x ^ y的结果中，所有 “1” 的位置就是两个数二进制位不同的位置，只需统计这个结果中 “1” 的个数即可。
哈希表的思路
哈希表在此题中意义不大，因为我们需要的是逐位比对，而哈希表更适合键值对查询，反而会增加空间复杂度，不推荐。

最优解法：位运算 + 计数

步骤拆解：

计算异或结果：xor = x ^ y，此时xor的二进制中，“1” 的个数就是汉明距离。
统计 “1” 的个数：循环检查xor的每一位是否为 1，累计计数。
- 可以用xor & 1判断最后一位是否为 1（结果为 1 则计数 + 1），然后右移xor（xor = xor >> 1），直到xor变为 0。

代码示例（Python）

python

运行

def hammingDistance(x: int, y: int) -> int:xor = x ^ y  # 异或得到不同位为1的数count = 0while xor:count += xor & 1  # 检查最后一位是否为1xor = xor >> 1    # 右移一位，处理下一位return count

复杂度分析

时间复杂度：O (log n)，其中 n 是x ^ y的最大值（最多 31 位，因为输入范围是2^31 - 1），循环次数最多为 31 次。
空间复杂度：O (1)，只需要常数个变量，无需额外空间。

总结

你的思路中，“位运算 + 计数” 是最优解，比二进制转换后比对更简洁高效。核心是利用异或运算的特性，将 “统计不同位” 转化为 “统计 1 的个数”，这也是处理二进制位问题的常用技巧。这道题作为 “康复训练” 非常合适，既巩固了位运算的理解，又能掌握简单的计数逻辑～

解题步骤（Java 实现）

异或运算（XOR）
对两个整数 x 和 y 进行异或运算（x ^ y），结果中二进制位为 1 的位置就是 x 和 y 对应位不同的位置。
例如：x=1（二进制 0001），y=4（二进制 0100），x^y=5（二进制 0101），其中有 2 个 1，所以汉明距离是 2。
统计 1 的个数
对异或的结果，循环检查每一位是否为 1，累计计数：
- 用 & 1 操作判断当前最低位是否为 1（结果为 1 则计数加 1）。
- 用右移操作（>> 1）将数字右移一位，处理下一位，直到数字变为 0。

Java 代码实现

public class HammingDistance {public int hammingDistance(int x, int y) {// 步骤1：计算x和y的异或结果int xor = x ^ y;int count = 0;// 步骤2：统计xor中1的个数while (xor != 0) {// 检查当前最低位是否为1（如果为1，count加1）count += xor & 1;// 右移一位，处理下一位xor = xor >> 1;}return count;}// 测试示例public static void main(String[] args) {HammingDistance solution = new HammingDistance();// 示例1：x=1, y=4，预期输出2System.out.println(solution.hammingDistance(1, 4)); // 输出2// 示例2：x=3, y=1，预期输出1System.out.println(solution.hammingDistance(3, 1)); // 输出1}
}

代码解析

异或运算：x ^ y 得到的结果中，每一位的 1 都代表 x 和 y 在该位置的二进制位不同。
统计 1 的个数：
- xor & 1：如果 xor 的最低位是 1，结果为 1，否则为 0，通过 count += 累计 1 的数量。
- xor = xor >> 1：将 xor 右移一位，相当于丢弃最低位，继续处理下一位。
- 循环直到 xor 变为 0，此时所有位都已处理完毕。

复杂度分析

时间复杂度：O (log n)，其中 n 是 x 和 y 的最大值（最多 31 位，因为输入范围是 2^31 - 1），循环最多执行 31 次。
空间复杂度：O (1)，只需要常数个变量存储中间结果，没有额外空间开销。

这种实现方式充分利用了位运算的特性，代码简洁高效，非常适合这道题的场景。如果有任何疑问，可以再结合示例一步步调试理解～

4 内置位计数功能

大多数编程语言都内置了计算二进制表达中 1 的数量的函数。

在工程中，我们应该直接使用内置函数。

。。啊咧啊咧，我发现我根本不知道计算机内部会内置二进制转换函数的事情。

温柔的ai老师：其实不用太担心，很多编程语言确实内置了二进制转换的工具

（比如 Java的 Integer.toBinaryString()），但这道题的最优解恰恰不需要显式转换二进制 —— 位运算本身就直接在二进制层面操作，效率更高，也更能体现对二进制逻辑的理解。

举个例子，Java 里如果用 Integer.toBinaryString(x) 确实能把整数转成二进制字符串，但之后还需要处理两个字符串的长度对齐（补前导 0）、逐位比较等操作，反而比位运算繁琐。比如：

java

运行

// 用二进制字符串转换的方式（不推荐，仅作对比）
public static int hammingDistanceByString(int x, int y) {String xBin = Integer.toBinaryString(x);String yBin = Integer.toBinaryString(y);int maxLen = Math.max(xBin.length(), yBin.length());// 补前导0，让两个字符串长度一致xBin = String.format("%" + maxLen + "s", xBin).replace(' ', '0');yBin = String.format("%" + maxLen + "s", yBin).replace(' ', '0');int count = 0;for (int i = 0; i < maxLen; i++) {if (xBin.charAt(i) != yBin.charAt(i)) {count++;}}return count;
}

这段代码能实现功能，但对比之前的位运算解法，明显更啰嗦，而且字符串操作的效率也低于纯位运算。

所以你看，不知道内置转换函数反而可能让你更专注于位运算这种更本质的解法 —— 这其实是好事呀！位运算在算法题里非常常用（比如处理二进制、状态压缩等），掌握这种思路对后续刷题很有帮助～

介绍一下内置位计数功能：

在很多编程语言中，都提供了直接统计二进制中 1 的个数的内置函数，这些函数通常经过高度优化，效率非常高。对于 Java 来说，也有专门的位计数工具，我们来具体了解一下：

Java 中的位计数内置功能

Java 的 Integer 类（处理 int 类型）和 Long 类（处理 long 类型）提供了多个用于统计二进制中 1 的个数的方法：

Integer.bitCount(int i)
最常用的方法，直接返回参数 i 的二进制表示中 1 的个数。

示例：

java

运行
```
int num = 5; // 二进制 101
System.out.println(Integer.bitCount(num)); // 输出 2
```
Integer.numberOfTrailingZeros(int i)
返回二进制表示中从最低位开始连续的 0 的个数（可辅助位运算）。

示例：

java

运行
```
int num = 8; // 二进制 1000
System.out.println(Integer.numberOfTrailingZeros(num)); // 输出 3（末尾有3个0）
```
Integer.highestOneBit(int i)
返回二进制表示中最高位的 1 所对应的值（其他位为 0）。

示例：

java

运行
```
int num = 5; // 二进制 101
System.out.println(Integer.highestOneBit(num)); // 输出 4（即 100）
```

用内置函数简化汉明距离代码

利用 Integer.bitCount()，汉明距离的代码可以简化为一行：

public class HammingDistanceBuiltIn {public static int hammingDistance(int x, int y) {// 异或后直接统计1的个数，一步到位return Integer.bitCount(x ^ y);}public static void main(String[] args) {System.out.println(hammingDistance(1, 4)); // 输出 2System.out.println(hammingDistance(3, 1)); // 输出 1}
}

为什么内置函数更高效？

Integer.bitCount() 并非用 Java 代码循环实现，而是底层通过CPU 指令（如 x86 的POPCNT指令）直接计算，执行效率远高于手动循环判断每一位，尤其在处理大量数据时优势明显。

总结

手动循环统计 1 的个数（&1 + 右移）是基础思路，帮助理解原理；
内置的 Integer.bitCount() 是工程实践中的最优选择，代码简洁且效率极高；
掌握这些工具函数能让你在刷题时更高效，尤其在处理位运算相关题目时（如统计位 1 的个数、比特位操作等）。

后续遇到类似 “统计二进制中 1 的个数” 的问题，直接想到 bitCount() 就好啦～

5 两个 int 类型的数进行异或（XOR）运算时

我的想法：

如果把两个int类型的数直接比较一下异或，底层逻辑应该就是在比较二进制位数的不同对不对？

是的，你的理解非常准确！两个 int 类型的数进行异或（XOR）运算时，底层确实是在逐位比较它们的二进制位，并根据 “相同为 0，不同为 1” 的规则生成结果。

具体来说，对于两个整数 x 和 y：

异或运算会将 x 和 y 的二进制表示按位对齐（32 位，因为 Java 中 int 是 32 位有符号整数）
对每一对对应位置的二进制位进行比较：
- 如果两位相同（都是 0 或都是 1），结果位为 0
- 如果两位不同（一个 0 一个 1），结果位为 1
最终得到的 32 位二进制数就是 x^y 的结果

例如：
x = 1 → 二进制：00000000 00000000 00000000 00000001
y = 4 → 二进制：00000000 00000000 00000000 00000100
x^y → 二进制：00000000 00000000 00000000 00000101（结果为 5）

可以看到，异或结果中为 1 的位，正好对应 x 和 y 二进制位不同的位置，这也是为什么我们可以通过统计异或结果中 1 的个数来计算汉明距离。

这种位级别的操作是计算机底层最基本的运算之一，由 CPU 直接支持，效率非常高，这也是位运算在算法中常用的原因。

6 答案

java

class Solution {public int hammingDistance(int x, int y) {int s = x ^ y, ret = 0;while (s != 0) {ret += s & 1;s >>= 1;}return ret;}
}

class Solution {public int hammingDistance(int x, int y) {return Integer.bitCount(x ^ y);}
}

class Solution {public int hammingDistance(int x, int y) {int s = x ^ y, ret = 0;while (s != 0) {s &= s - 1;ret++;}return ret;}
}

7 Brian Kernighan 算法（最后一个答案）

Brian Kernighan 算法是一种高效统计二进制中 1 的个数的方法，尤其适合优化位运算相关问题。我们来详细理解它的原理和用法：

核心原理

Brian Kernighan 算法的关键结论是：对于任意整数 s，s & (s - 1) 的结果等价于将 s 二进制中最右侧的 1 变为 0。

举个例子：

若 s = 6（二进制 110），则 s - 1 = 5（二进制 101）
s & (s - 1) = 110 & 101 = 100（最右侧的 1 被消除）

每执行一次 s &= s - 1，就会消除 s 中最右侧的一个 1。因此，循环执行该操作直到 s = 0，循环的次数就是 s 中 1 的总个数。

用该算法解决汉明距离问题

结合汉明距离的定义（统计两个数二进制位不同的个数），步骤如下：

计算 x 和 y 的异或结果 s = x ^ y（此时 s 中 1 的位置就是不同的位）
用 Brian Kernighan 算法统计 s 中 1 的个数，即为汉明距离

Java 代码实现

public class HammingDistanceBrianKernighan {public int hammingDistance(int x, int y) {int s = x ^ y; // 异或得到不同位为1的数int count = 0;// 循环消除最右侧的1，直到s变为0while (s != 0) {s &= s - 1; // 消除最右侧的1count++;    // 每消除一个1，计数加1}return count;}public static void main(String[] args) {HammingDistanceBrianKernighan solution = new HammingDistanceBrianKernighan();System.out.println(solution.hammingDistance(1, 4)); // 输出2System.out.println(solution.hammingDistance(3, 1)); // 输出1}
}

优势分析

对比普通的循环移位法（每次检查最后一位）：

效率更高：循环次数等于二进制中 1 的实际个数（而非固定的 32 次）。例如，若 s 只有 3 个 1，只需循环 3 次。
逻辑巧妙：利用位运算的特性直接操作二进制位，避免了多余的移位判断。

总结

Brian Kernighan 算法是位运算中的经典技巧，特别适合需要统计二进制中 1 的个数的场景。对于汉明距离问题，它比普通循环法更高效，且代码简洁，是值得掌握的优化方法。

这种思路也可以推广到其他类似问题，比如「统计一个数的二进制中 1 的个数」「判断一个数是否为 2 的幂（二进制只有一个 1）」等。

8 s &= s - 1是什么意思?

s &= s - 1 是 Java 中的复合赋值运算符，等价于 s = s & (s - 1)，其中 & 是按位与运算。这个表达式的核心作用是消除 s 的二进制表示中最右侧的那个 1，我们通过具体例子来理解：

步骤 1：理解 `s - 1` 的二进制变化

当一个数 s 减去 1 时，其二进制会发生特定变化：

从最右侧的 1 开始，该位置变为 0
该位置右侧的所有 0 都会变成 1
左侧的位保持不变

例如：

若 s = 6（二进制 110），则 s - 1 = 5（二进制 101）
- 最右侧的 1（第 2 位）变成 0
- 右侧的 0（第 1 位）变成 1
若 s = 8（二进制 1000），则 s - 1 = 7（二进制 0111）
- 最右侧的 1（第 4 位）变成 0
- 右侧的 3 个 0 都变成 1

步骤 2：理解 `s & (s - 1)` 的结果

按位与运算（&）的规则是：对应位都为 1 时结果为 1，否则为 0。
当计算 s & (s - 1) 时：

原 s 中最右侧的 1，在 s - 1 中对应位置是 0 → 结果为 0（该 1 被消除）
该 1 右侧的位：s 中是 0，s - 1 中是 1 → 结果为 0
该 1 左侧的位：s 和 s - 1 完全相同 → 结果不变

例如：

s = 6（110），s - 1 = 5（101）
s & (s - 1) = 110 & 101 = 100（最右侧的 1 被消除）
s = 10（1010），s - 1 = 9（1001）
s & (s - 1) = 1010 & 1001 = 1000（最右侧的 1 被消除）