返回统计数量 res。
public class Solution { public int hammingWeight(int n) { int res = 0; while(n != 0) { res += n & 1; // 遍历 n >>>= 1; // 无符号右移 } return res; } } 方法 2:位操作的小技巧算法
我们可以把前面的算法进行优化。我们不再检查数字的每一个位,而是不断把数字最后一个 1 反转,并把答案加一。当数字变成 0 的时候偶,我们就知道它没有 1 的位了,此时返回答案。
这里关键的想法是对于任意数字 n ,将 n 和 n - 1 做与运算,会把最后一个 1 的位变成 0 。为什么?考虑 n 和 n - 1 的二进制表示。
巧用 \(n \& (n - 1)\)
\((n - 1)\) 解析: 二进制数字 n 最右边的 1 变成 0 ,此 1 右边的 0 都变成 1 。
\(n \& (n - 1)\) 解析: 二进制数字 n 最右边的 1 变成 0 ,其余不变。
图片 1. 将 n 和 n-1 做与运算会将最低位的 1 变成 0
在二进制表示中,数字 n 中最低位的 1 总是对应 n - 1 中的 0 。因此,将 n 和 n - 1 与运算总是能把 n 中最低位的 1 变成 0 ,并保持其他位不变。
使用这个小技巧,代码变得非常简单。
Java
public int hammingWeight(int n) { int sum = 0; while (n != 0) { sum++; n &= (n - 1); } return sum; }复杂度分析
时间复杂度:\(O(1)\)。运行时间与 n 中位为 1 的有关。在最坏情况下,n 中所有位都是 1 。对于 32 位整数,运行时间是 \(O(1)\) 的。
空间复杂度:\(O(1)\)。没有使用额外空间。
只出现一次的数字给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1] 输出: 1示例 2:
输入: [4,1,2,1,2] 输出: 4 答案方法一:位运算
如果不考虑时间复杂度和空间复杂度的限制,这道题有很多种解法,可能的解法有如下几种。