C语言 这是计算二进制数中 0 数的正确方法吗?

Question

#include <stdio.h>
int NumberOfSetBits(int);
int main(int argc, char *argv[]) {
    int size_of_int = sizeof(int);
    int total_bit_size = size_of_int * 8;
    // binary representation of 3 is 0000011 
    // C standard doesn't support binary representation directly
    int n = 3; 
    int count = NumberOfSetBits(n);
    printf("Number of set bits is: %dn", count);
    printf("Number of unset bits is: %d", total_bit_size - count);
}
int NumberOfSetBits(int x)
{
    int count = 0;
    //printf("x is: %dn", x);
    while (x != 0) {
        //printf("%dn", x);
        count += (x & 1);
        x = x >> 1;
    }
    return count;
}

设置位数为：2

未设置位数为：30

int size_of_int = sizeof(int);
int total_bit_size = size_of_int * 8;

^ 这将得到系统上 int 的大小并将其乘以 8，这是每个字节中的位数

编辑：不使用~

/*
    Calculate how many set bits and unset bits are in a binary number aka how many 1s and 0s in a binary number
*/
#include <stdio.h>
unsigned int NumberOfSetBits(unsigned int);
unsigned int NumberOfUnSetBits(unsigned int x);

int main() {
    // binary representation of 3 is 0000011 
    // C standard doesn't support binary representation directly    
    unsigned int n = 3; 
    printf("Number of set bits is: %un", NumberOfSetBits(n));
    printf("Number of unset bits is: %u", NumberOfUnSetBits(n));
    return 0;
}
unsigned int NumberOfSetBits(unsigned int x) {
    // counts the number of 1s
    unsigned int count = 0;
    while (x != 0) {
        count += (x & 1);
        // moves to the next bit
        x = x >> 1;
    }
    return count;
}
unsigned int NumberOfUnSetBits(unsigned int x) {
    // counts the number of 0s
    unsigned int count = 0; 
    while(x != 0) {
        if ((x & 1) == 0) {
            count++;
        }
        // moves to the next bit
        x = x >> 1; 
    }
    return count;
}

输入 3 的返回值

Number of set bits is: 2
Number of unset bits is: 0

未设置位为 0？好像不对？

如果我使用 NumberOfSetBits（~n），它返回 30

Answer 1

在某些系统上遇到了问题，因为您在位计数函数中右移了一个有符号整数，每次对于负整数，该函数可能会将 1 移入 MSB。请改用unsigned int（或仅unsigned

）：

int NumberOfSetBits(unsigned x)
{
    int count = 0;
    //printf("x is: %dn", x);
    while (x != 0) {
        //printf("%dn", x);
        count += (x & 1);
        x >>= 1;
    }
    return count;
}

如果您修复了问题的这一部分，则可以通过以下方式解决另一部分问题：

int nbits = NumberOfSetBits(~n);

其中~以n为单位反转值，因此"设置位计数"计算为零的位。

还有更快的算法来计算设置的位数：参见 Bit Twiddling Hacks。

Answer 2

在不假设 2 的补码或没有填充位的情况下求解 NumberOfSetBits(int x) 版本是一个挑战。

@Jonathan莱夫勒有正确的方法：使用unsigned。 - 只是想我会尝试一个通用的int。

x > 0，OP的代码工作正常

int NumberOfSetBits_Positive(int x) {
  int count = 0;
  while (x != 0) {
    count += (x & 1);
    x = x >> 1;
  }
  return count;
}

使用以下命令查找位宽，而不计算填充位。

BitWidth = NumberOfSetBits_Positive(INT_MAX)  + 1;

有了这个，0 位或 1 位的计数是微不足道的。

int NumberOfClearBits(int x) {
  return NumberOfSetBits_Positive(INT_MAX)  + 1 - NumberOfSetBits(x);
}
int NumberOfSetBits_Negative(int x) {
  return NumberOfSetBits_Positive(INT_MAX)  + 1 - NumberOfSetBits_Positive(~x);
}

剩下的就是找到 x 为 0 时设置的位数。 +0 很简单，答案是 0，但 -0（1 的赞美或符号大小）是 BitWidth 或 1。

int NumberOfSetBits(int x) {
  if (x > 0) return NumberOfSetBits_Positive(x);
  if (x < 0) return NumberOfSetBits_Negative(x);
  // Code's assumption: Only 1 or 2 forms of 0.  
  /// There may be more because of padding.
  int zero = 0;
  // is x has same bit pattern as +0
  if (memcmp(&x, &zero, sizeof x) == 0) return 0;
  // Assume -0
  return NumberOfSetBits_Positive(INT_MAX)  + 1 - NumberOfSetBits_Positive(~x);
}

Answer 3

这是计算二进制数中Zeores数量的正确方法

#include <stdio.h>
unsigned int binaryCount(unsigned int x)
{
    unsigned int nb=0; // will count the number of zeores 
    if(x==0) //for the case zero we need to return 1
        return 1;
    while(x!=0)
    {
        if ((x & 1) == 0) // the condition for getting the most right bit in the number
        {
            nb++;
        }
        x=x>>1; // move to the next bit 
    }
    return nb;
}
int main(int argc, char *argv[])
{
    int x;
    printf("input the number x:");
    scanf("%d",&x);
    printf("the number of 0 in the binary number of %d is %u n",x,binaryCount(x));
    return 0;
}