Leetcode 1 的位数

通过 位操作 来逐位检查二进制数中的每一位是否为 1，并通过移位操作逐步处理每一位，直到处理完所有位。

&（按位与） 操作符在 Java 中会自动将两个整数转换为它们的二进制表示，然后逐位进行“与”运算。其运算规则是：仅当对应的两位都为 1 时，结果才为 1；否则为 0。

在 Java 中，>>> 是一个 无符号右移操作符，它与普通的右移操作符 >> 的区别在于：它不考虑符号位（正负号），无论被移位的数字是正数还是负数，>>> 都会在高位用 0 来填充。

具体的算法思想：

1. 逐位检查：

   • 通过位与操作 (n & 1) 来判断当前二进制数的最低位是否为 1。n & 1 的作用是只保留二进制数的最后一位，因为 1 的二进制是 0001，所以当 n 的最低位为 1 时，n & 1 的结果为 1，否则为 0。

   例如：对 n = 11（二进制表示为 1011）执行位与操作：

   • 1011 & 0001 = 1 （最低位是 1，结果为 1）。

2. 计数：

   • 每次通过 n & 1 判断最低位是否为 1，如果是 1，则将计数器 count 加 1。

3. 移位操作：

   • 使用 n >>>= 1 来对 n 进行无符号右移。右移的效果是将当前的最低位丢弃，并将次低位变为新的最低位，从而对下一个二进制位进行检查。>>> 是 Java 中的无符号右移操作，即使是负数也不会保留符号位（最高位），而是用 0 补位。

   例如：对 n = 11 （二进制为 1011）执行右移操作：

   • 第一次右移：1011 >>> 1 = 0101
   • 第二次右移：0101 >>> 1 = 0010
   • 第三次右移：0010 >>> 1 = 0001
   • 第四次右移：0001 >>> 1 = 0000

4. 结束条件：

   • 循环的结束条件是 n != 0，即当所有的二进制位都处理完，n 会变为 0，此时停止循环。

算法的时间复杂度：

• 时间复杂度：O(1)，虽然在理论上我们需要对 n 的每一位进行处理（32 位整数需要最多 32 次迭代），但是由于 Java 中 int 类型是固定的 32 位，因此时间复杂度是常数级别的。
• 空间复杂度：O(1)，算法只使用了少量的额外变量来存储计数器和中间结果，因此空间复杂度也是常数。

总结：

这个算法的思想很直接，即通过逐位判断二进制数的每一位是否为 1，并使用移位操作来遍历整个二进制数。每检查一位，我们就将 n 右移一位，直到所有位都被处理完毕。这种算法非常高效，特别适合处理二进制相关的问题。

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0) {
            count += (1 & n);
            n = n >>> 1;
        }
        return count;
    }
}