LeetCode 面试经典150题 191.位1的个数

Java中的算术右移和逻辑右移的区别

题目：编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中设置位的个数（也被称为汉明重量）。 设置位的个数即二进制中1的个数。

思路：方法一：因为正数的原反补码相同，符号位0，&1取最低位，然后右移，循环到n != 0即可

方法二：n & (n - 1) ，这个代码可以把 n 的二进制中最后一个出现的 1 改写成 0

代码：

class Solution {  // 方法一public int hammingWeight(int n) {int count = 0;  // 记录1出现的次数while (n != 0) {count += n & 1;  // 得到n的最低位n >>= 1;  // n右移一位}return count;}
}

public class Solution {  // 方法二public int hammingWeight(int n) {int res = 0;while (n != 0) {res += 1;n &= n - 1;  // n & (n - 1)可以把n的二进制中最后出现的1改为0}return res;}
}

性能：

时间复杂度o(k)，k为n的二进制长度

空间复杂度o(1)

// you need to treat n as an unsigned value

这句话的含义是 会找一个跟你的无符号数完全相同的有符号数作为输入，你不用考虑只需把输入当作无符号处理即可。