「题解」解决二进制数中1的个数

🐶博主主页：@ᰔᩚ. 一怀明月ꦿ

❤️‍🔥专栏系列：线性代数，C初学者入门训练

🔥座右铭：“不要等到什么都没有了，才下定决心去做”

🚀🚀🚀大家觉不错的话，就恳求大家点点关注，点点小爱心，指点指点🚀🚀🚀

🐰取余取模法

🐰按位与法

🐰n=n&(n-1)法

🐰随记

🐰取余取模法

我们这里求的二进制数的1的个数求的是补码中1的个数

这种方法和十进制取余取模类似的，只是把10换成了2，例如：12345

12345%10=5

12345/10=1234

1234%10=4

1234/10=123

......

二进制也一样，例如：12

12%2=0

12/2=6

6%2=0

6/2=3

3%2=1

1/2=0

1%2=1
#include<stdio.h>
int main()
{int a=-1,count=0,num=0;unsigned int b=a;while(b){num=b%2;b/=2;if(num==1){count++;}}printf("%d\n",count);return 0;
}
这里负数也不用担心，我们把负数的补码转化为无符号数，这样也可以的到负数的补码了。

🐰按位与法

这种方法就是，利用按位与的性质，a&b，a和b相同的数就为相同的数，a和b不同的数则为0，例如，a=1000 0011 b=0110 0001

c=a&b

1000 0011

0110 0001

c=0000 0001

如果我们一个数a&1,且每次按位与完，我们就右移一位>>1，例如，a=12=1100

1100&1: 1100

1

num:0

a>>1: 1100>>1=0110

0110&1: 0110

1

num:0

a>>1: 0110>>1=0011

0011&1: 0011

1

num:1

a>>1: 0011>>1=0001

0001&1:0001
1

num:1

a>>1: 0001>>1=0000

0000&1: 0000

1

num:0

然后统计num为1的次数就可以了
#include<stdio.h>
int main()
{int a=-1,count=0,num=0;for(int i=0;i<32;i++){num=a&1;if(num==1){count++;}a=a>>1;}printf("%d\n",count);return 0;
}

🐰n=n&(n-1)法

只运算一次，n的二进制中最右边的一个1就会消失，例如n=1100

n:   1100

n-1:        1011

n&(n-1): 1000

n: 1000

n-1: 0111

n&(n-1): 0000

然后，统计n经历了几次n&(n-1)后，变为0的
#include<stdio.h>
int main()
{int a=-1,count=0;int num=a;while(num){num=num&(num-1);count++;}printf("%d\n",count);return 0;
}
这三种方法中，n=n&(n-1)法是效率最高的一种方法

我们在判断一个数是否是2的次幂数，也可以用n=n&(n-1)法，因为2的次幂数又个特点，就是二进制只有一个1，例如

2^0: 0001

2^1: 0010

2^2: 0100

2^3: 1000

......
#include<stdio.h>
int main()
{int num=102;num=num&(num-1);if(num==0){printf("是\n");}else{printf("不是\n");}return 0;
}

🐰随记

今天还使用到了一些小的知识点：

1.全局变量不初始化，就是默认为0

2.如果说一个整数和一个无符号整形数比较时，要被转化为两个无符号数比较例如：a=-1,sizeof(a)

if(a>sizeof(a))

这里sizeof(a)=4,sizeof(a)得到是一个无符号数，比较时a得转化为无符号数

a=-1:原码：10000000000000000000000000000001

反码：1111111111111111111111111111111111111111110

补码：1111111111111111111111111111111111111111111

当a转化为无符号数时，1111111111111111111111111111111111111111111这就是原码，这将是一个非常大的数，肯定大于sizeof(a)

3.栈区的使用习惯，先使用高地址，再使用低地址（常规情况下，release就除外了）

4.大端字节序：把一个数据的低字节的数据，存放在高地址处，把高字节的数据，存放在低地址处

小端字节序：把一个数据的低字节的数据，存放在低地址处，把高字节的数据，存放在高地址处