有更好的方法吗？

// Definition: Count number of 1's and 0's from integer with bitwise operation
//
// 2^32 = 4,294,967,296
// unsigned int 32 bit

#include<stdio.h>

int CountOnesFromInteger(unsigned int);

int main()
{
    unsigned int inputValue;
    short unsigned int onesOfValue;
    printf("Please Enter value (between 0 to 4,294,967,295) : ");
    scanf("%u",&inputValue);
    onesOfValue = CountOnesFromInteger(inputValue);

    printf("\nThe Number has \"%d\" 1's and \"%d\" 0's",onesOfValue,32-onesOfValue);
}

int CountOnesFromInteger(unsigned int value)
{
    unsigned short int i, count = 0;
    for(i = 0; i < 32 ; i++)
    {
        if (value % 2 != 0)
        {
            count++;
        }
        value = value >> 1;
    }
    return count;
}


评论

考虑到标题对按位运算符的引用，我很惊讶地看到if（value％2！= 0）而不是if（value＆1）。

#1 楼

是的，有更好的方法：

int CountOnesFromInteger(unsigned int value) {
    int count;
    for (count = 0; value != 0; count++, value &= value-1);
    return count;
}


代码依赖于以下事实：表达式x &= x-1;从所设置的x中删除最右边的位。我们会一直这样做，直到不再移除1。该技术在K＆R中进行了描述。

这种方法是优越的，因为它不依赖于整数的大小-完全可移植-并且以相当有效的方式测试每一位（与value != 0进行比较） 。

另外，您可能希望将32中的main()替换为sizeof(int)*CHAR_BIT，以使您的代码不依赖于使用32位的整数：

#include <stdio.h>
#include <limits.h>

int CountOnesFromInteger(unsigned int);

int main()
{
    unsigned int inputValue;
    short unsigned int onesOfValue;
    printf("Please Enter value (between 0 to 4,294,967,295) : ");
    scanf("%u",&inputValue);
    onesOfValue = CountOnesFromInteger(inputValue);

    printf("\nThe Number has \"%d\" 1's and \"%zu\" 0's",onesOfValue,sizeof(int)*CHAR_BIT-onesOfValue);
    return 0;
}


评论

\ $ \ begingroup \ $
我认为，不必测试每一位并不是事实（不是测试所有位就不可能解决这个问题）； ！= 0表达式只是测试所有位的有效方法（通过并行执行）。
\ $ \ endgroup \ $
–弗里希·拉贝（Frerich Raabe）
13年12月27日在22:40
\ $ \ begingroup \ $
同样，循环也会在时间上与不精确的声音数量成比例地运行-循环的迭代次数不取决于声音的数量，而仅取决于最重要的声音的位置。 。
\ $ \ endgroup \ $
–弗里希·拉贝（Frerich Raabe）
13年12月27日在22:45
\ $ \ begingroup \ $
@FrerichRaabe感谢您的注意。我编辑了答案。
\ $ \ endgroup \ $
–菲利普·贡萨尔维斯（FilipeGonçalves）
13年12月28日在12:05

#2 楼

我会选择非标准函数，因为C用位操作糟透了：

#include <stdio.h>

#ifdef __GNUC__
int popcount(int x) {
  return __builtin_popcount(x);
}
#else
#error Unimplemented popcount
#endif


int main(void)
{
  int x;
  scanf("%d", &x);

  printf("%d\n", popcount(x));

  return 0;
}


这将转换为有效的处理器指令（如果可用）或有效的库实现

参考文献：
http://en.wikipedia.org/wiki/Hamming_weight

https://stackoverflow.com/questions/15736602 / fastest-way-to-count-number-of-1s-in-a-register-arm-assembly

http://wm.ite.pl/articles/sse-popcount.html

http://gcc.gnu.org/onlinedocs/gcc-4.8.2/gcc/Other-Builtins.html#Other-Builtins

评论

\ $ \ begingroup \ $
为什么说C用位操作糟透了？
\ $ \ endgroup \ $
– 200_success
13年12月28日在17:59
\ $ \ begingroup \ $
为了兼容，我将定义int CountOnesfromInteger（无符号int值）{#ifdef __GNUC__ return __builtin_popcount（value）; #else / *您自己的实现* / #endif}`。
\ $ \ endgroup \ $
– 200_success
2013年12月28日18:01


#3 楼

从StackOverflow答案：

int CountOnesFromInteger(uint32_t i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}


这是一般情况下最著名的实现。说明（请参阅popcount_3）是它适用于2位，4位和8位的组。

@FilipeGonçalves发布的解决方案最适用于稀疏位集。

评论

\ $ \ begingroup \ $
是的！对于感兴趣的读者，沃伦（Warren）的《黑客的喜悦》（Hacker's Delight）中有整整一章。
\ $ \ endgroup \ $
–user34350
2014年1月3日，7：34

#4 楼

@Filipe达到了我想介绍的要点。但是可以做一些小的改进。


卸下!= 0以获得最大的C感。

if (value % 2)



如果没有将任何参数放入main()中，则应将其声明为void。您声明要返回return。让我们在程序结束时返回int表示成功。

int main(void)


评论

\ $ \ begingroup \ $
我相信main也应该返回一些内容（返回0；仅对C ++ IIRC隐式）。
\ $ \ endgroup \ $
–弗里希·拉贝（Frerich Raabe）
2013年12月27日22:41
\ $ \ begingroup \ $
@FrerichRaabe好的，我已经对其进行了编辑。
\ $ \ endgroup \ $
–syb0rg
2013年12月27日22:43
\ $ \ begingroup \ $
@FrerichRaabe：从C99标准开始，要求编译器生成return 0的等效项，或者如果main末尾未提供return则返回EXIT_SUCCESS。
\ $ \ endgroup \ $
–爱德华
15年8月20日在16:16