要计算一个二进制数的位数或统计其中1的个数,可以采用以下方法:
一、计算二进制数的位数
整数部分位数
通过连续除以2并记录余数,直到商为0,余数的个数即为二进制位数。例如将23转换为二进制:
```
23 ÷ 2 得余数序列:1,1,1,0,1
```
余数序列长度为5,因此23的二进制表示为`10111`(5位)。
小数部分位数
从左到右用二进制每位乘以2的负次幂求和。例如将0.625转换为二进制:
```
0.625 * 2 = 1.25 取整1
0.25 * 2 = 0.5 取整0
0.5 * 2 = 1.0 取整1
```
结果为`0.101`(3位小数)。
二、统计二进制数中1的个数
逐位检查法
通过连续与运算消除最右侧的1,统计消除次数。例如统计1010中1的个数:
```
1010 & (1010 - 1) = 1010 & 1001 = 1000(1次消除)
1000 & (1000 - 1) = 1000 & 0111 = 0100(1次消除)
0100 & (0100 - 1) = 0100 & 0011 = 0000(1次消除)
总计3次消除,因此有3个1。
位运算优化
使用右移运算符和按位与运算符快速统计。例如:
```c
int count = 0;
while (num != 0) {
count += num & 1; // 检查最低位是否为1
num >>= 1;// 右移一位
}
```
或者使用`n & (n - 1)`技巧:
```c
int count = 0;
while (num != 0) {
num &= (num - 1); // 消除最低位的1
count++;// 统计1的个数
}
```
以上方法的时间复杂度为O(k),其中k是二进制中1的个数。
三、注意事项
二进制位数仅适用于整数部分,小数部分需单独处理。
统计1的个数时,需区分整数和小数部分的二进制表示。
通过上述方法,可以灵活地计算二进制数的位数或统计其中1的个数,适用于不同场景的需求。