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: %d\n", count);
    printf("Number of unset bits is: %d", total_bit_size - count);
}

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

Number of set bits is: 2

Number of unset bits is: 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: %u\n", 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: %d\n", x);
    while (x != 0) {
        //printf("%d\n", x);
        count += (x & 1);
        x >>= 1;
    }
    return count;
}

如果你解决了问题的那一部分，你可以通过以下方式解决另一部分:

int nbits = NumberOfSetBits(~n);

其中 ~ 按位反转 n 中的值，因此“设置位计数”计算为零的位。

还有计算比特集数量的更快算法:参见 Bit Twiddling Hacks .