代码之家 › 专栏 › 技术社区 › Denyk

在C语言中,计算二进制数的区间长度最有效的方法是什么?[重复]

algorithm c

Denyk · 技术社区 · 7 年前

我想写一个名为 bitCount() 在文件中: bitcount.c 返回其无符号整数参数的二进制表示形式中的位数。

以下是我目前掌握的情况:

#include <stdio.h>

int bitCount (unsigned int n);

int main () {
    printf ("# 1-bits in base 2 representation of %u = %d, should be 0\n",
        0, bitCount (0));
    printf ("# 1-bits in base 2 representation of %u = %d, should be 1\n",
        1, bitCount (1));
    printf ("# 1-bits in base 2 representation of %u = %d, should be 16\n",
        2863311530u, bitCount (2863311530u));
    printf ("# 1-bits in base 2 representation of %u = %d, should be 1\n",
        536870912, bitCount (536870912));
    printf ("# 1-bits in base 2 representation of %u = %d, should be 32\n",
        4294967295u, bitCount (4294967295u));
    return 0;
}

int bitCount (unsigned int n) {
    /* your code here */
}

好的,当我运行这个时,我得到:

# 1-bits in base 2 representation of 0 = 1, should be 0
# 1-bits in base 2 representation of 1 = 56, should be 1
# 1-bits in base 2 representation of 2863311530 = 57, should be 16
# 1-bits in base 2 representation of 536870912 = 67, should be 1
# 1-bits in base 2 representation of 4294967295 = 65, should be 32

RUN SUCCESSFUL (total time: 14ms)

它不会返回正确的位数。

在C语言中,返回无符号整数参数二进制表示形式的位数的最佳方法是什么?

0 回复 | 直到 11 年前

Mark Ransom 11 年前

这里有一个不需要迭代的解决方案。它利用了这样一个事实,即二进制中的位相加完全独立于位的位置,并且总和永远不会超过2位。 00+00=00 , 00+01=01 , 01+00=01 , 01+01=10 .第一次加法会同时添加16个不同的1位值,第二次加法会添加8个2位值,然后每个值都会添加一半的值,直到只剩下一个值。

int bitCount(unsigned int n)
{
    n = ((0xaaaaaaaa & n) >> 1) + (0x55555555 & n);
    n = ((0xcccccccc & n) >> 2) + (0x33333333 & n);
    n = ((0xf0f0f0f0 & n) >> 4) + (0x0f0f0f0f & n);
    n = ((0xff00ff00 & n) >> 8) + (0x00ff00ff & n);
    n = ((0xffff0000 & n) >> 16) + (0x0000ffff & n);
    return n;
}

这是硬编码为32位整数,如果您的大小不同,则需要调整。

ogzd 13 年前

 int bitCount(unsigned int n) {

    int counter = 0;
    while(n) {
        counter += n % 2;
        n >>= 1;
    }
    return counter;
 }

Community Mohan Dere 9 年前

事实证明,有一些非常复杂的方法来计算答案 here .

下面的impl(我早就学会了)只是在每次迭代中循环去掉最低有效位。

int bitCount(unsigned int n) {

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