【C语言练习】二进制中1的个数-创新互联
目录
- 题目详情:
- 思路一:
- 思路二:
- 思路三:
拿到二进制的每一位,看它是否等于
1
1
1,再定义一个计数器变量,如果等于
1
1
1,计数器变量就加
1
1
1。最终计数器的值就是
1
1
1 的个数。
现在的问题就变成了—— 如何得到二进制的每一位? 以十进制数字
123
123
123 为例,通过123%10=3
就能得到
3
3
3,不难发现:只要用一个数除以它的进制数,最终的余数就是这个数最低位上的数字,因此如果要得到
2
2
2 首先要让
2
2
2 来到最低位,只要去掉当前最低位上的
3
3
3 ,
2
2
2 就能来到最低位上。如何去掉最低位上的数字呢? 通过123/10=13
就能把最低位上的
3
3
3 去掉。可见:只要用一个数除以它的进制数,就能去掉该数当前的最后一位数字。(这里指的是整数除法)因此我们只要不断地重复上面的两个步骤,就能都得到一个数上的每一位数字。二进制数也同理。思路整理的差不多接下来就该通过代码来实现了。
代码实现:
int NumberOf1(int a)
{int count = 0;//计数器
while (a)
{if (a % 2 == 1)//通过取模得到最低位上的数字
{ count++;
}
a /= 2;//通过整数除法取出掉最低位上的数字
}
return count;
}
int main()
{int a = 0;
scanf("%d", &a);
int num = NumberOf1(a);
printf("%d\n", num);
return 0;
}
上述代码缺陷:
经过测试发现,上述代码可以准确计算出一个正整数二进制位中
1
1
1 的个数,当参数是负数时,计算出来的结果,与我们希望的结果会有很大的差距。以
−
1
-1
−1 为例,理论上
−
1
-1
−1 的补码是32个全
1
1
1 ,因此计算出来的结果应该是32才对,但上面这段代码计算出的结果是
0
0
0 ,为什么呢?结果是
0
0
0 说明if (-1 % 2 == 1)
没成立过,我们可以通过内存窗口来看看-1 % 2
的结果到底是什么,
结果是ff ff ff ff
。内存中存的是补码,所以对应的二进制补码就是
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111,int b
说明b
是一个有符号的的整型,因此前面二进制的最高位是符号位,并且是
1
1
1 ,说明-1%2
的结果是一个负数,自然就不可能等于
1
1
1 了。我们发现:只要是一个负数,对
2
2
2 取模得到的结果就一定是一个负数,就永远也不可能等于
1
1
1,如何解决这个问题呢?
这里我们可以把形参设置成一个无符号的整型变量,此时问题就迎刃而解了。还是以
−
1
-1
−1 为例:
−
1
-1
−1 在内存中的补码是
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111 传参的时候用一个无符号的整型变量a
去接收 ,在这个无符号的整型变量a
的眼里
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111 就不再是什么
−
1
-1
−1 的补码了,a
认为这就是一串普普通通的二进制代码,没有什么所谓的符号位这些乱七八糟的东西。因此再用a%2
得到的结果就不再可能是负数了,我们还是可以通过调试来一探究竟。
上图中,我们把
−
1
-1
−1 赋值给一个无符号的的整型变量a
,然后用a%2
得到的结果是
1
1
1 ,并且也是无符号整型;用a/2
得到
2147483647
2147483647
2147483647 ,这个很容易理解,因为
−
1
-1
−1 的补码
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111 在a
的眼里就是一个平平无奇的二进制序列,没有符号位,这个二进制序列转换成十进制就是:
4
,
294
,
967
,
295
4,294,967,295
4,294,967,295,除以
2
2
2 就得到
2147483647
2147483647
2147483647
代码修改:
int NumberOf1(unsigned int a)//把形参改成无符号整型,就对负数也适用了
{int count = 0;
while (a)
{if (a % 2 == 1)
{ count++;
}
a /= 2;
}
return count;
}
int main()
{int a = 0;
scanf("%d", &a);
int num = NumberOf1(a);
printf("%d\n", num);
return 0;
}
上面的代码,在传 − 1 -1 −1 的时候,计算出来的结果就是我们所期待的 32 32 32 了。到这里,思路一就结束了。接下来看另一种思路。
思路二: 思路二的大体方向和思路一 一样,得到二进制序列的每一位,然后看其是否等于
1
1
1 。只不过思路二的实现方法与思路一不同,会比思路一容易一些,都是初学者不容易想出来。接下来就来整理一下思路二吧,首先我们还是希望得到二进制的每一位,此时我们可以借助按位与(&
)这个操作符来实现,还记得按位与的计算过程嘛?对应的两个二进制位都为
1
1
1 的时候出
1
1
1 ,其他全部出
0
0
0 ,因此,可以让待求得二进制序列按位与上
1
1
1 ,
1
1
1 的二进制序列为
00000000000000000000000000000001
00000000000000000000000000000001
00000000000000000000000000000001 ,此时待求的二进制序列的最低位如果是
1
1
1 ,那1&1
得到的结果就是
1
1
1 ,如果待求的二进制序列的最低位是
0
0
0 ,那0&1
得到的结果就是
0
0
0,我们发现任何一个二进制只要与上
1
1
1 都会得到它自身。此时我们得到了二进制序列的最低位,那它的第二位、第三位、第四位……呢?别忘了,我们还有一个移位操作符,我们可以利用移位操作符,让二进制序列往右移动,使得每一个二进制位都能与上
1
1
1 ,这样我们就能拿到二进制序列的每一位了。大体思路捋的差不多了,接下来该上代码了。
int NumberOf1(int a)
{int i = 0;
int count = 0;
for (i = 0; i< 32; i++)//最多只需右移31个二进制位
{if (((a >>i) & 1) == 1)//只有当1 & 1结果才是1,让a的二进制位一直右移
{ count++;
}
}
return count;
}
int main()
{int a = 0;
scanf("%d", &a);
int num = NumberOf1(a);
printf("%d\n", num);
return 0;
}
思路二也无需考虑什么正负数,因为移位操作符和位操作符都是直接针对二进制位来计算的,看完思路二我就只想说妙。但是别急,接下来的思路三才算得上是“王炸”
思路三: 这里直接上方法,记住下面这个式子:n=n&(n-1)
。举个例子,以十进制的
11
11
11 为例,
11
11
11 的二进制是
1011
1011
1011 ,此时n=1011;
,n-1=1010;
,n&(n-1)=1010
此时n
就变成了:
1010
1010
1010 ,对比前面的n
我们发现二进制序列最右边的
1
1
1 变成了
0
0
0 ,接着往下,n=1010;
,n-1=1001;
,n&(n-1)=1000
此时n
就变成了
1000
1000
1000 对比第二个n
二进制序列最右边的
1
1
1 又变成了
0
0
0,再往下看,n=1000;
,n-1=0111;
,n&(n-1)=0000
此时n
就变成了
0000
0000
0000 。不难发现:n
从最初的
1011
1011
1011 ,变成了现在的
0000
0000
0000 是把n=n&(n-1)
这个式子执行了
3
3
3 次,什么?3??这不就是
1011
1011
1011 这个二进制序列里面
1
1
1 的个数嘛,其实这并非偶然,因为n=n&(n-1)
这个式子每执行一次,就会把当前n
这个二进制序列里面最右边的
1
1
1 去除掉,直到整个二进制序列变成
0
0
0 ,分析的差不多了,接下来上代码!
int NumberOf1(int n)
{int count = 0;
while (n)//能变成全0的时候,就不用再执行下面的式子了
{n = n & (n - 1);
count++;//记录上面这个式子一共执行了多少次
}
return count;
}
int main()
{int n = 0;
scanf("%d", &n);
int num = NumberOf1(n);
printf("%d\n", num);
return 0;
}
哈哈,没骗你吧,思路三才是最终的“王炸”
好了,这道题的分享就到这里啦,如果你有更好的思路或者方法,欢迎在评论区或者私信,给我留言,拜拜咯!
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网页名称:【C语言练习】二进制中1的个数-创新互联
路径分享:http://pwwzsj.com/article/heejs.html