LeetCode: 191 Number of 1 Bits

Here’s a detailed explanation and solution for LeetCode 191: Number of 1 Bits, with explanations provided in both English and Chinese, line by line.

Problem

Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Example:

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string has a total of three '1' bits.

Example:

Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string has a total of one '1' bit.

Example:

Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string has a total of thirty-one '1' bits.

问题

编写一个函数，该函数接收一个无符号整数，并返回其二进制表示中 ‘1’ 位的数量（也称为汉明重量）。

解决方案 1

位操作

Approach 1 / 方法 1

This solution uses bitwise operations to count the number of ‘1’ bits in the integer. The idea is to iterate through all the bits of the integer and count how many are set to ‘1’. We can do this by checking the least significant bit (LSB) and then right-shifting the integer.

该解决方案使用位操作来计算整数中 ‘1’ 位的数量。其思想是遍历整数的所有位，并计算其中有多少位被设置为 ‘1’。我们可以通过检查最低有效位（LSB），然后将整数右移来完成此操作。

Implementation / 实现

python

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            count += n & 1
            n >>= 1
        return count

Explanation / 解释

1. Initialize a Counter / 初始化计数器

   count = 0

   • English: We initialize a counter count to keep track of the number of ‘1’ bits.
   • Chinese: 我们初始化一个计数器 count，用于跟踪 ‘1’ 位的数量。

2. Iterate While n is Not Zero / 在 n 不为零时进行迭代

   while n:

   • English: We enter a loop that continues as long as n is not zero.
   • Chinese: 我们进入一个循环，只要 n 不为零，循环就会继续。

3. Check the Least Significant Bit (LSB) / 检查最低有效位（LSB）

   count += n & 1

   • English: We use the bitwise AND operation n & 1 to check if the least significant bit is ‘1’. If it is, we increment the count.
   • Chinese: 我们使用位与操作 n & 1 来检查最低有效位是否为 ‘1’。如果是，我们将 count 加 1。

4. Right-Shift n by One Bit / 将 n 右移一位

   n >>= 1

   • English: We right-shift n by one bit to check the next bit in the next iteration.
   • Chinese: 我们将 n 右移一位，以便在下一次迭代中检查下一个位。

5. Return the Count / 返回计数

   return count

   • English: After the loop ends, we return the count, which is the number of ‘1’ bits in the binary representation of n.
   • Chinese: 循环结束后，我们返回 count，即 n 的二进制表示中的 ‘1’ 位数量。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(1), since we iterate over the 32 bits of the integer in a fixed number of steps (at most 32 iterations).
• Space Complexity / 空间复杂度: O(1), as we use only a constant amount of extra space.

Key Concept / 关键概念

• Bitwise Operations / 位操作: The bitwise approach is efficient for counting ‘1’ bits by directly manipulating the binary representation of the integer.
• 位操作: 位操作法通过直接操作整数的二进制表示，高效地计算 ‘1’ 位的数量。

解决方案 2

位操作优化（Brian Kernighan 算法）

Approach 2 / 方法 2

This solution is an optimized version of the bitwise approach using Brian Kernighan’s algorithm. The idea is to repeatedly flip the least significant ‘1’ bit of the integer to zero until the number becomes zero. This method reduces the number of operations needed to count the ‘1’ bits.

该解决方案是使用 Brian Kernighan 算法的位操作法的优化版本。其思想是反复将整数的最低有效 ‘1’ 位翻转为零，直到数字变为零。此方法减少了计算 ‘1’ 位所需的操作次数。

Implementation / 实现

python

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count

Explanation / 解释

1. Initialize a Counter / 初始化计数器

   count = 0

   • English: We initialize a counter count to keep track of the number of ‘1’ bits.
   • Chinese: 我们初始化一个计数器 count，用于跟踪 ‘1’ 位的数量。

2. Iterate While n is Not Zero / 在 n 不为零时进行迭代

   while n:

   • English: We enter a loop that continues as long as n is not zero.
   • Chinese: 我们进入一个循环，只要 n 不为零，循环就会继续。

3. Flip the Least Significant ‘1’ Bit to Zero / 将最低有效 ‘1’ 位翻转为零

   n &= n - 1

   • English: The operation n &= n - 1 flips the lowest ‘1’ bit of n to zero. This operation effectively reduces the number of ‘1’ bits in n by one.
   • Chinese: 操作 n &= n - 1 将 n 的最低有效 ‘1’ 位翻转为零。此操作有效地减少了 n 中的 ‘1’ 位数量。

4. Increment the Counter / 增加计数器

   count += 1

   • English: After each flip, we increment the count by 1.
   • Chinese: 每次翻转后，我们将 count 增加 1。

5. Return the Count / 返回计数

   return count

   • English: After the loop ends, we return the count, which is the number of ‘1’ bits in the binary representation of n.
   • Chinese: 循环结束后，我们返回 count，即 n 的二进制表示中的 ‘1’ 位数量。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(k), where k is the number of ‘1’ bits in the integer. In the worst case, this is O(32) for a 32-bit integer.
• Space Complexity / 空间复杂度: O(1), as we use only a constant amount of extra space.

Key Concept / 关键概念

• Brian Kernighan’s Algorithm / Brian Kernighan 算法: This algorithm efficiently counts the number of ‘1’ bits by reducing the integer bit by bit, making it more efficient than a straightforward bitwise approach.
• Brian Kernighan 算法: 该算法通过逐位减少整数，高效地计算 ‘1’ 位的数量，使其比直接的位操作方法更高效。

Comparison / 比较

1. Efficiency / 效率:

   • Basic Bitwise Approach / 基本位操作法: Simple and effective, but may involve unnecessary iterations if there are many ‘0’ bits.
   • Brian Kernighan’s Algorithm / Brian Kernighan 算法: More efficient as it only processes the ‘1’ bits, skipping the ‘0’ bits.

2. Use Case / 使用场景:

   • Basic Bitwise / 基本位操作: Suitable for general cases where simplicity is preferred.
   • Brian Kernighan / **

Brian Kernighan 算法**: Preferred when optimizing for performance, especially with numbers having fewer ‘1’ bits.

Summary / 总结

• English: Both the basic bitwise and Brian Kernighan’s approaches are valid for counting ‘1’ bits in an integer. The basic bitwise approach is simple, while the Brian Kernighan method is more efficient.
• Chinese: 基本位操作法和 Brian Kernighan 算法都可以有效地计算整数中的 ‘1’ 位数量。基本位操作方法简单，而 Brian Kernighan 方法更高效。

Tips / 提示

• English: Use Brian Kernighan’s algorithm for a more efficient solution, especially when dealing with large numbers or performance-critical applications.
• Chinese: 使用 Brian Kernighan 算法来获得更高效的解决方案，特别是在处理大数字或对性能要求严格的应用时。

Solution Template for Similar Questions / 提示

• English: Consider both the basic bitwise and optimized approaches for bit manipulation problems, depending on the specific requirements of the problem.
• Chinese: 对于位操作问题，根据问题的具体要求，考虑基本位操作和优化方法。

5 More Similar Questions / 推荐5问题

1. LeetCode 338. Counting Bits
2. LeetCode 190. Reverse Bits
3. LeetCode 201. Bitwise AND of Numbers Range
4. LeetCode 231. Power of Two
5. LeetCode 461. Hamming Distance

Recommended Resources / 推荐资源

• English: Practice bitwise operations and Brian Kernighan’s algorithm to master counting ‘1’ bits and other bit manipulation techniques.
• Chinese: 通过练习位操作和 Brian Kernighan 算法，掌握 ‘1’ 位计算和其他位操作技巧。

Number of 1 Bits – Leetcode 191 – Python by NeetCode