二进制问题
要点
- 二进制码：利用位运算，每次将数字与1进行与运算，如果结果为1，则表示该位为1，计数器加1，然后将数字右移一位，继续与1进行与运算，直到数字为0为止。
- 反码：将二进制码取反得到反码，注意 符号位不参与 翻转。
- 补码：正数的二进制码与补码相同，负数的绝对值的二进制码取反（符号位不翻转）加一得到补码
- 需要注意INT_MIN，因为INT_MIN在32位整型中没有对应的正数，取反加一后将溢出，所以需要将由负数转换成的正数以无符号整数的形式保存
例题1 二进制表示中1的个数
题目描述
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
示例
1
2
3
| 输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
|
解题思路
- 利用位运算，每次将数字与1进行与运算，如果结果为1，则表示该位为1，计数器加1，然后将数字右移一位，继续与1进行与运算，直到数字为0为止。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while (n) {
if (n & 1) {
count++;
}
n >>= 1;
}
return count;
}
}
|
例题2 二进制中1的个数
题目描述
输入一个 32 位整数，输出该数二进制表示中 1 的个数。
注意：
负数在计算机中用其绝对值的补码来表示。
示例
1
2
3
| 输入：-2
输出：31
解释：-2在计算机里会被表示成11111111111111111111111111111110, 一共有31个1。
|
解题思路
- 对负数，先转换成正数
- 计算正数二进制中一的个数和位置
- 将负数二进制码取反加一得到补码
- 计算补码中1的个数
- 需要注意INT_MIN，因为INT_MIN在32位整型中没有对应的正数，取反加一后将溢出，所以需要将由负数转换成的正数以无符号整数的形式保存
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
public:
int NumberOf1(int n) {
if(n == 0) return 0;
bool negative = false;
int ans = 0;
unsigned int num = 0;
if(n < 0) {
negative = true;
num = -n;
} else {
num = n;
}
vector<bool> bi(32, false);
for(int i=0; i<32; i++) {
if(num == 0) break;
if(num%2 == 1) bi[i] = true;
num /= 2;
}
if(negative) {
for(int i=0; i<32; i++) {
bi[i] = bi[i] == false;
}
int index = 0;
while(index<32 && bi[index]) {
bi[index] = false;
index++;
}
if(index < 32) bi[index] = true;
}
for(int i=0; i<32; i++) {
if(bi[i]) ans++;
}
return ans;
}
};
|
