二进制数中1的个数

Question

我需要编写一个程序来计算无符号数的二进制表示中 1 的个数，使用递归函数，所以这是我的代码：

#include <stdio.h>
#include <stdlib.h>

int one(unsigned n);

int main()
{
    unsigned n;
    printf("n= "); scanf("%u", &n);
    printf("%d", one(n));

    printf("\n");
    return 0;
}

int one(unsigned n)
{
    if(n==1 || n==0)
        return n;
    else
        return (n&1+one(n>>1));
}

例如，我的代码适用于数字 7，但是如果我输入数字 2，它会打印出其中有 2 个。对于 4，它是 returns 0，我认为对于 2 的所有指数，它最终是 returns 0。我不明白为什么。

Answer 1

&运算符的优先级低于+运算符，这导致else分支或one中的计算产生错误（逻辑上）结果。只需用括号将其括起来以确保它首先执行，您应该没问题：

return (n & 1) + one(n>>1);

Answer 2

主要问题在这里：

    return (n&1+one(n>>1));

加法运算符 + 运算符的优先级高于按位与运算符 &。所以表达式实际上是：

    return (n & ( 1 + one(n >> 1)));

您需要在 n&1 周围添加括号：

    return ((n & 1) + one(n >> 1));

编辑：

作为编程练习，这很好用。在实际代码中，预先计算的查找 table 效率更高。

// Assumes CHAR_BITS == 8

int numbits[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
                   ...
                     4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 };

int count_bits(unsigned n)
{
    int i, count = 0;
    for (i=0; i<sizeof(n); i++) {
        count += numbits[(uint8_t)(n & 0xFF)];
        n >>= 8;
    }
}

Answer 3

在这一行

return (n&1+one(n>>1));

运算符 + 的优先级高于 &。但是，你必须先屏蔽最后一位，然后添加它：

return ((n&1) + one(n>>1));

二进制数中1的个数

Number of 1s in a binary number

c

recursion

bit-manipulation