什么是汉明重量

191. 位1的个数 【简单题】【位运算】

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

输入：00000000000000000000000000001011 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。 输入：00000000000000000000000010000000 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。 输入：11111111111111111111111111111101 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

题目讲解

解法1：位运算

【核心思想】

设置一个位掩码mask=1，每次遍历将mas左移一位，java中用这个符号<<遍历数字的32位，如果某一位是1，则将计数器+1

【举例说明】

我们判断n = 010中1的个数先设置位掩码mask = 1，等同于mask = 001将mask和n做’与’运算，mask & n = 001 & 010 = 0，所以n的最后一位是0将mask左移一位，得到mask = 010，再和n做’与’运算，mask & n = 010 & 010 = 1，所以n的倒数第二位是1将mask左移一位，得到mask = 100，再和n做’与’运算，mask & n = 100 & 010 = 1，所以n的倒数第三位是0计数得到n中1的个数为1

【代码】

public class Solution { public int hammingWeight(int n) { int ans = 0; int mask = 1; for (int i = 0; i < 32; i++) { if ((n & mask) != 0) ans++; mask = mask<<1; } return ans; } }

【备注】

这道题还有一种更简单的方法。首先我们要知道n & (n - 1)代表着把n的最后一个1变成0，为什么？举例说明，令n = 10110，那么n - 1 = 10101，n & (n - 1) = 10110 & 10101 = 11100，确实把最后一个1变成了0。严密的证明过程读者可以自己探索一下

所以，只要重复n & (n - 1)的操作，直到n == 0，那么操作了几次，n中就有几个1

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

微信关注我吧