欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

三种方法判断一个数二进制序列中1的个数

程序员文章站 2022-07-15 09:47:13
...

第一种方法,也是比较容易想到的,就是模2除2法。模2运算得到这个数二进制序列中的最低位,除2去掉这个数二进制序列中的最低位。当这个数进行模2运算的结果为1时,那么它的最低位就是1,然后再进行除2运算,将倒数第二位的数置为最末位,如此循环,当这个数为0时,也就判断完了每一位是否为1。同时应该注意,这个方法只能判断正数,不能判断负数,因为负数进行模2运算的结果只能是0,这是这个方法的一大缺陷。下面是具体实现代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>

//模2除2法,该方法不能判断负数,因为负数模2的结果总是0
int count_one_bits(int n)
{
    int count = 0;
    while (n)
    {
        if (n % 2 == 1)//模2可以得到最低位的数,如果模2的结果是1,则将count++
        {
            count++;
        }
        n = n / 2;//除2可以去掉最末位的数
    }
    return count;
}
int main()
{
    int i = 0;
    int num = 0;
    scanf("%d", &num);
    int ret = count_one_bits(num);//将实参num传递到函数中
    printf("%d\n", ret);
    system("pause");
    return 0;
}

第二种方法,是将这个数与1进行按位与,如果结果是1,那么这个数的最末位就是1,判断完最末位,再将这个数进行右移运算,判断倒数第二位,如此循环32次,就判断出了这个数二进制序列中有多少个数字1。这个方法弥补了模2除2法只能判断正数的缺陷。下面是具体实现代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>

int count_one_bits(int n)
{
    int count = 0;
    int i = 0;
    for (i = 0; i < 32; i++)
    {
        if ((n >> i) & 1 == 1)//一个数与1按位与结果如果是1则这个数的最末位就是1
        {
            count++;
        }
    }
    return count;
}

int main()
{
    int num = 0;
    scanf("%d", &num);
    int ret = count_one_bits(num);//将实参num传入函数
    printf("%d\n", ret);
    system("pause");
    return 0;
}

第三种方法,也是最优化的一种方法,即将要判断的数和这个数减一的数进行按位与再赋给这个数,然后如此循环,直到这个数为0,这样就可以判断除这个数二进制序列中具体有多少个数字1。 具体实现代码如下:

 #define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>

int count_one_bits(int n)
{
    int count = 0;
    while (n)
    {
        n = n & (n - 1);
        count++;
    }
    return count;
}

int main()
{
    int num = 0;
    scanf("%d", &num);
    int ret = count_one_bits(num);//将实参num传递到函数
    printf("%d\n", ret);
    system("pause");
    return 0;
}