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

简介: 🐰取余取模法🐰按位与法🐰n=n&(n-1)法 🐰随记

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

目录

🐰取余取模法

🐰按位与法

🐰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

1. #include<stdio.h>
2. int main()
3. {
4. int a=-1,count=0,num=0;
5. unsigned int b=a;
6. while(b)
7.     {
8.         num=b%2;
9.         b/=2;
10. if(num==1)
11.         {
12.             count++;
13.         }
14.     }
15. printf("%d\n",count);
16. return 0;
17. }

这里负数也不用担心,我们把负数的补码转化为无符号数,这样也可以的到负数的补码了。

🐰按位与法

这种方法就是,利用按位与的性质,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的次数就可以了

1. #include<stdio.h>
2. int main()
3. {
4. int a=-1,count=0,num=0;
5. for(int i=0;i<32;i++)
6.     {
7.         num=a&1;
8. if(num==1)
9.         {
10.             count++;
11.         }
12.         a=a>>1;
13.     }
14. printf("%d\n",count);
15. return 0;
16. }

🐰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的

1. #include<stdio.h>
2. int main()
3. {
4. int a=-1,count=0;
5. int num=a;
6. while(num)
7.     {
8.         num=num&(num-1);
9.         count++;
10.     }
11. printf("%d\n",count);
12. return 0;
13. }

这三种方法中,n=n&(n-1)法 是效率最高的一种方法

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

2^0:        0001

2^1:         0010

2^2:        0100

2^3:        1000

......

1. #include<stdio.h>
2. int main()
3. {
4. int num=102;
5.     num=num&(num-1);
6. if(num==0)
7.     {
8. printf("是\n");
9.     }
10. else
11.     {
12. printf("不是\n");
13.     }
14. return 0;
15. }

🐰随记

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

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.大端字节序:把一个数据的低字节的数据,存放在高地址处,把高字节的数据,存放在低地址处

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

🌸🌸🌸如果大家还有不懂或者建议都可以发在评论区,我们共同探讨,共同学习,共同进步。谢谢大家! 🌸🌸🌸  

相关文章
|
6月前
力扣421. 数组中两个数的最大异或值(字典树)
力扣421. 数组中两个数的最大异或值(字典树)
|
6月前
《剑指offer》——二进制中1的个数
《剑指offer》——二进制中1的个数
【剑指offer】-二进制中1的个数-11/67
【剑指offer】-二进制中1的个数-11/67
|
机器学习/深度学习 C++
剑指offer 14. 二进制中1的个数
剑指offer 14. 二进制中1的个数
58 0
剑指Offer - 面试题15:二进制中1的个数
剑指Offer - 面试题15:二进制中1的个数
71 0
剑指offer_位运算---二进制中1的个数
剑指offer_位运算---二进制中1的个数
50 0
【剑指offer】二进制中1的个数&&2的幂
【剑指offer】二进制中1的个数&&2的幂
【剑指offer】二进制中1的个数&&2的幂
LeetCode 1689. 十-二进制数的最少数目
如果一个十进制数字不含任何前导零,且每一位上的数字不是 0 就是 1 ,那么该数字就是一个 十-二进制数 。
95 0
LeetCode 1290. 二进制链表转整数
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
104 0
AcWing 26. 二进制中1的个数
AcWing 26. 二进制中1的个数
108 0
AcWing 26. 二进制中1的个数