【技巧】Leetcode 191. 位1的个数【简单】

位1的个数

• 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。

  示例 1：

  
  （图片来源网络，侵删）

  输入：n = 11

  输出：3

  解释：输入的二进制串 1011 中，共有 3 个设置位。

  示例 2：

  输入：n = 128

  输出：1

  解释：输入的二进制串 10000000 中，共有 1 个设置位。

  解题思路

  • 使用位操作，通过不断地将最低位的1清除。

    位操作原理

    • n &= (n - 1); 这个操作实际上是移除了整数 n 的二进制表示中最低位的 1。

      例子

      • 假设 n = 12，其二进制表示为 1100。我们来看 n - 1 和 n & (n - 1) 的结果：
      • n = 12，二进制：1100
      • n - 1 = 11，二进制：1011
      • n & (n - 1)：

        1100

        & 1011

        1000

      • 结果是 1000，即 8。
      • 可以看到，最低位的 1 已经被移除。

        Java实现

        public class HammingWeight {
            public int hammingWeight(int n) {
                int count = 0;
                while (n != 0) {
                    n &= (n - 1);  // 清除最低位的1
                    count++;
                }
                return count;
            }
            // 测试用例
            public static void main(String[] args) {
                HammingWeight solution = new HammingWeight();
                System.out.println(solution.hammingWeight(11)); // 期望输出: 3 (二进制: 1011)
                System.out.println(solution.hammingWeight(128)); // 期望输出: 1 (二进制: 10000000)
            }
        }
        

        时间空间复杂度

        • 时间复杂度：O(k)，其中k是二进制表示中1的个数。
        • 空间复杂度：O(1)，只使用了常数级别的额外空间。