编写一个程序来计算C语言中设置的位数。

Question

我尝试在C语言中计算整数值中设置的位数。但是对于某些值，它显示了正确的位设置计数，而对于某些值则没有。

以下是程序代码：

int main()
{
    int a = 512, i = 0, j = 1, count = 0, k = 0;

    for (i = 0; i < 31; i++)
    {
        if (k = a & j)
        {
            count++;
            j = j << 1;
        }
    }
    printf("the total bit set count is %d", count);
}

512的位值计数输出显示为零，如果使用的值是511，则计数显示为9。

请帮我纠正程序。

- skesh

---

一个 int 不一定有32位。而且通常情况下，对于位移操作，最好使用无符号整数。 - too honest for this site

int cnt; uint32_t k; k = ...; for (cnt = 0; k; k >>= 1) if (k & 1) cnt++; 还有更好的算法，可以自行研究（需要1-2分钟）。 - too honest for this site

你尝试过使用基本的调试方法来调试你的程序吗？（例如在程序的关键位置插入一些printf语句） - Jabberwocky

编译器警告是有充分理由存在的。在提问之前，请启用它们并处理所有报告！ - too honest for this site

在添加了else语句后修改程序后，它开始正常工作。 if(a&j) { count++; j=j<<1; } else j=j<<1; - skesh

Answer 1

斯坦福大学有一个页面介绍了实现常见位操作的不同方法。他们列出了5种不同的算法来计算设置的位数，并提供了C语言示例。

https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

其中最简单的实现方式如下：

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v

for (c = 0; v; v >>= 1)
{
  c += v & 1;
}

- Andrew Williamson

---

仅供参考，将链接作为答案发布是不被赞同的，因为无法保证链接明天是否存在，这使得答案对于之后的任何人都没有价值。请提供示例并解释它们，或将链接作为评论发布。 - David C. Rankin

更新答案以反映此事。 - Andrew Williamson

Answer 2

如果您正在使用gcc/clang编译器，您可以使用内置函数__builtin_popcount。

unsigned int user_input = 100
int count = __builtin_popcount(n); // count == 3

如果我不需要跨平台，我会使用此函数，因为它高度优化。

- Idok

Answer 3

通常情况下，您会在无符号整数中计算位数。原因是您通常会检查寄存器或掩码中设置的位，例如。有符号整数使用二进制补码表示，如果您确实想要计算有符号整数中设置的位数，我无法想出为什么（如果您确实想要这样做，我会很感兴趣）。

请注意，在C语言中，如果数字为负数，则对有符号整数进行右移或左移操作是实现定义的行为。根据C标准第6.5.7节：

... E1 << E2 的结果是将 E1 左移 E2 位；... 如果 E1 具有有符号类型且具有非负值，并且 E1 << E2 可以在结果类型中表示，则该值就是结果值；否则，行为是未定义的。

E1 >> E2 的结果是将 E1 右移 E2 位；... 如果 E1 具有有符号类型且具有负值，则结果值是实现定义的...

如果你想要计算任意大小的无符号整数中的1的个数，你可以使用这个例子：this example。

#include <stdio.h>

int main(void) {
   unsigned int value = 1234;
   unsigned int ones = 0;
   while(value > 0) {
      ones += value & 0x1;
      value >>= 1;
   }
   printf("#Ones = %u", ones);
}

使用此示例，value 可以是无符号字符、无符号长整型，或任何无符号整数类型...

注意：不要对有符号值或浮点数/双精度数进行位移。

- Jimbo

---

我已经尝试过这个程序来学习在C语言中变量的位运算和位排列。 - skesh

Answer 4

你可以使用除法符号 / 和取模符号 % 来检查整数中设置的位。

int main()
{
    int a = 512, count = 0;

    while(a != 0)
    {
        if(a % 2 == 1)
        {
            count++;
        }
        a /= 2;
    }
    printf("The total bit set is %d", count);
}

- Haris

---

我也尝试了这种方法，它也很好用。谢谢。 - skesh

除非编译器真的很好并且优化了知道a永远不会是负数的情况，否则代码将对a％2进行余数调用，结果为0,1或-1，然后与1进行比较。在这种情况下，if（a％2）可以产生更简单的代码，甚至是if（a＆1）。但我怀疑您正在强调代码清晰度而不是性能。注意：如果a起始为负数，则结果为0。 - chux - Reinstate Monica

Answer 5

你有几个错误：

for(i=0;i<32;i++) // <<< this should be 32, not 31
{
    if(k=a&j)
    {
        count++;
    }
    j=j<<1;       // <<< this needs to be outside the if block
}

请注意，不要使用硬编码的值 32 来表示 int 类型中的位数，最好像这样做：

for(i=0;i<sizeof(int)*CHAR_BIT;i++)

这样，如果 int 的大小为 16 位或 64 位，代码仍然可以正常工作。

- Paul R

---

请问您能解释一下CHAR_BIT值是什么吗？ - skesh

CHAR_BIT是在limits.h中定义的常量，它定义了每个字节（或每个char）的位数。通常为8。它可以防止在代码中硬编码该值。上面的sizeof(int)*CHAR_BIT是4 * 8 = 32。 - David C. Rankin

虽然通常不是问题，但 j=j<<1 的倒数第二次移位是一个令人担忧的未定义行为。 - chux - Reinstate Monica

@chux：你能再详细说一下吗？我没有看到任何UB问题，但是我可能忽略了一些显而易见的事情？ - Paul R

如果E1具有带符号类型和非负值，并且E1×2E2可以在结果类型中表示，则该值为结果值；否则，行为未定义。C11 §6.5.7 4是一种说法，即将位移至符号位是UB。int j = 0x40000000; ... j = j << 1是可能的问题。 - chux - Reinstate Monica

有趣 - 我不知道那个 - 我本来想提到，在进行位操作时使用无符号类型通常是一个好主意，但其他人已经在另一个答案/评论中涵盖了这一点，所以我没有再重复它。 - Paul R

Answer 6

您正在检查a&j的值，如果a&j为0，则除了重试之外不做任何其他操作。

您的j位移需要在if-then之外。

- hymie

Answer 7

尽管这不是纯粹的C语言，但您可以使用内嵌汇编来调用x86指令POPCNT。

// GCC syntax
unsigned a = 1234;
unsigned int count;
__asm__( 
    "  POPCNT %0, %1\n"
    :"=r" (count)
    :"r" (a)
);
return count;

根据这个基准测试，像idok的答案中调用__builtin_popcount与上述代码一样快，它们都比任何其他C实现都要快得多。您还可以查看链接的存储库以获取其他解决方案。

- balping

---

这严格来说并不是C语言……也不能说是松散地说 :) - chqrlie

Answer 8

#include<stdio.h>
#include<conio.h>

int rem, binary = 0;
unsigned int

countSetBits (unsigned int n){

    unsigned int count = 0;

    while (n){
        count += n & 1;
        n >>= 1;
    }

    printf ("\n\t Number of  1's  in the binary number is : %d",count);
}

int dec_bin (int n){

    int i=1;

    while (n != 0){
        rem = n % 2;
        n = n / 2;
        binary = binary + (rem * i);
        i = i * 10;
    }

    printf("\n\t The converted Binary Equivalent is : %d",binary);
}

int main(){  
    int i = 0;

    printf ("\n\t Enter the Decimal Nummber: ");

    scanf ("%d", &i);

    int n= i;
    dec_bin(n);
    countSetBits (i);
    return 0;
}

- Supriya Singh