第一种:
假如想知道 5 的二进制有几个 1,那么可以把 5 & 1,然后看最低位是 1 还是 0 ,判断完再把
5>>1(">>"右移操作符),然后继续判断,判断32次就好了。(1个整型在内存中的二进制是32个bit位)
& —— 按位与操作符,同时为 1 是 1,有 0 是 0。
00000000000000000000000000000101 —— 5 的二进制
00000000000000000000000000000001 —— 1 的二进制
00000000000000000000000000000001 —— 5 &1 的二进制
00000000000000000000000000000010 —— 5 >> 1 ( 5 右移一个bit位)
00000000000000000000000000000001 —— 1 的二进制
00000000000000000000000000000000 —— 5 &1 的二进制
然后继续以此类推,就不继续举例了,直接上代码。
#include <stdio.h> int find_1(int n) { int count = 0; for(int i = 0; i < 32;
i++) { if( ((n >> i) & 1) == 1 ) // 因为 i 是从 0 开始的,第一次 n >> i 相当于没有移 { count++;
// 统计 1 的个数 } } return count; } int main() { int n = 0; scanf("%d", &n); int
ret = find_1(n); printf("%d\n", ret); return 0; }
第二种:
假如有个数 1234,我想拿到它的每一位我可以 %10、/10 ,因为一个数 %10 的余数是 <10 的,如下:
1234 % 10 = 4
1234 / 10 = 123
123 % 10 = 3
123 / 10 = 12
后面以此类推,我不继续举例。但我们要拿 1 的话是不是 %2、/2 呢?如下举例:
假如 10 这个数,它的二进制数是 00000000000000000000000000001010
10 % 2 = 0 —— 相当于把 10 的二进制的最低位也就是最右边的 0 拿到了
10 / 2 = 5 —— 5 的二进制是 00000000000000000000000000000101 相当于去掉了 10 的二进制最低位也就是最右边
0
5 % 2 = 1 —— 相当于把 5 的二进制的最低位也就是最右边的 1 拿到了
5 / 2 = 2 —— 2 的二进制是 00000000000000000000000000000010 相当于去掉了 5 的二进制最低位也就是最右边 1
2 % 2 = 0 —— 相当于把 2 的二进制的最低位也就是最右边的 0 拿到了
2 / 2 = 1 —— 1 的二进制是 00000000000000000000000000000001 相当于去掉了 2 的二进制最低位也就是最右边 0
后面依次类推,当每次 n%2 = 1 就累计一次,知道 n = 0 为止,下面是代码:
#include <stdio.h> int find_1(int n) { int count = 0; unsigned int m = n; //
这里定义一个无符号整型 m 接收 n,因为如果 n 是负数的话,假如是 -1,while 循环可以进去,但是 -1 % 2 之后不等于 1,直接走到 -1 /
2,那值为 0,直接跳出while循环,所以这里用无符号整型 m 接收 n while(m) // m = 0 跳出循环 { if(m % 2 == 1) {
count++; // 累计 1 的个数 } m = m / 2; } return count; } int main() { int n = 0;
scanf("%d", &n); int ret = find_1(n); printf("%d\n", ret); return 0; }
第三种:有个表达式是 ====> n = n & ( n-1 ) ,假如输入 n = 13 ,13 的二进制 1101
1101 —— n
1100 —— n-1
1100 —— n & n-1 再赋给 n、
1011 —— n-1
1000 —— n & n-1 再赋给 n
0111 —— n-1
0000 —— n & n-1 再赋给 n
每次去掉一个 1,执行几次就有几个 1 ,每次把二进制数的最右边的 1去掉,直到为零停止,代码如下:
#include <stdio.h> int find_1(int n) { int count = 0; while(n) { n = n & (n -
1); count++; } return count; } int main() { int n = 0; scanf("%d", &n); int ret
= find_1(n); printf("%d\n", ret); return 0; }
从算法的时间复杂度来看,第三种最高效,其次是第二种,最后是第一种。