338 比特位计数 461 汉明距离

题目

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10
示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

• 法一：动态规划

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> resu(n+1,0);//结果数组
        for(int i=1;i<=n;i++)
        {
        	//i的二进制表示中，最低位由i%2决定，其余位中1的个数与i/2中的个数一致
            resu[i]=resu[i/2]+i%2;
        }
        return resu;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

• 思路
  • 数字i的二进制表示中1的个数可以由两部分组成。第一部分是数字i/2中1的个数，表示i中除了个位以外的数字中1的个数。第二部分是i的个位，i对2取余，如果为1则个数为1，如果为0则个数为0

题目

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
示例 2：

输入：x = 3, y = 1
输出：1

class Solution {
public:
    int hammingDistance(int x, int y) {
        int resu=x^y;//异或操作
        int cnt=0;//计数器
        //计算二进制表示中1的个数
        while(resu!=0)
        {
            cnt+=resu%2;
            resu/=2;
        }
        return cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 思路
  • 汉明距离就是两个数的二进制表示中对应位不同的个数
  • 对两个数字x和y做异或操作，得到的数字的二进制表示中1的个数就是汉明距离。因为与操作实质上是按位异或，两个数字不同则值为1，相同则为0.