一、问题描述
给定一个数n
,求该数转换成二进制后包含的1
的个数。
二、代码实现
非常老也是非常经典的一个面试题,第一次面试的时候就遇到了,这里只要把n
和n-1
循环按位与就可以了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <stdio.h> int main(){ int n, cnt; while(scanf("%d", &n) != EOF){ cnt = 0; while (n){ cnt ++; n = n & (n - 1); } printf("%d\n", cnt); } return 0; } |
三、变形
题目非常老,经常会被变形。例如把该过程封装成一个函数,然后传入参数,求输出值。
1 2 3 4 5 6 7 8 9 10 11 12 13 |
int f(int x) { int cnt = 0; while (x) { cnt++; x = x & (x - 1); } return cnt; } int main() { printf("%d\n", f(9999)); return 0; } |
这里输出的就是9999的二进制中1的个数8。
评论