C语言实现：查找一个整数中1的个数

一个很基本的想法是，我们先判断整数的最右边一位是不是1。接着把整数右移一位，原来处于右边第二位的数字现在被移到第一位了，再判断是不是1。这样每次移动一位，直到这个整数变成0为止。现在的问题变成怎样判断一个整数的最右边一位是不是1了。很简单，如果它和整数1作与运算。由于1除了最右边一位以外，其他所有位都为0。因此如果与运算的结果为1，表示整数的最右边一位是1，否则是0。

    while(c )
    {
      if(c & 1)
      {
          count++;
      }
      c=c>>1;//c=c/2;
    }

- 使用位&运算符解决：每次把最低位转换为0

按位与运算符&经常用于屏蔽某些二进制位，将某些位置0；

    while(c)
    {

        count++;
        c=c&(c-1);
    }

循环： x = x & ( x - 1 ); count++; 直到x为0为止。该方法的时间复杂度是O(m)
在此，不妨把x的二进制位表示为
x=an-1an-2…a0。
按从低位到高位的顺序，不失一般性，假设x的第i位为第一个为1的二进制位，即：ai=1。此时有：
x =an-1an-2…ai+1100…0 <1>
(x-1) =an-1an-2…ai+1011…1 <2>
很明显，从式1和式2可以得出，在第一次 x & (x-1) 后：
x=an-1an-2…ai+1000…0
之后重复同样操作，直到x的二进制位中没有1为止
从上面可以看出，每执行过一次 x & (x-1) 后，都会将x的二进制位中为1的最低位的值变为0，并记数加1。
目前而言，一个整数最大64bit，所有三种方法执行起来都可以认为是0(1)。
此外仍有
- 使用按位异或^运算符解决问题：
找了半天，原来没有使用^解决问题的也；有空再尝试下，要吃饭了，好饿。
扩展：如何用一个语句判断一个整数是不是2的整数次幂？

PS：n&(n-1)==0;//二进制数只有一位位1，则该数是2的整数次幂.

最后

以上就是怡然八宝粥为你收集整理的C语言实现：查找一个整数中1的个数的全部内容，希望文章能够帮你解决C语言实现：查找一个整数中1的个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。