C语言经典算法（三）——求二进制中1的个数的五种方法

一时失言乱红尘 2022-06-03 07:20 175阅读 0赞

今后继续整理算法并写出自己的理解和备注。 C++实现的：二进制中1的个数

1、 二进制中1的个数  
<1> 题目描述:对一个字节的无符号整形变量，求二进制数中1的个数(要求:执行效率尽可能高)  
<2> 方法一:使用模方法  
<3> 方法二:使用位操作运算  
<4> 方法三:时间复杂度是与1的个数有关的算法  
<5> 方法四:分支法  
<6> 方法五:查表法

源码：  
一、二进制中1的个数  
1、使用模方法

#include<iostream>
    using namespace std;
    int Count(unsigned char v)
    {
        int count = 0;
        while(v != 0)
        {
            if(v % 2 == 1)
                count++;//每次除以2 若有余数则count+!
            v /= 2;
        }
        return count;
    }
    void main()
    {
        unsigned char ch = 255;
        int count = Count(ch);
        cout<<"count = "<<count<<endl;
    }

2、 使用位操作运算

#include<iostream>
    using namespace std;
    int Count(unsigned char v)
    {
        int count = 0;
        while(v != 0)
        {
            count += v & 0x01;
            v >>= 1;//每次右移一位，与0000 0001进行与运算，最多只运行8次
        }
        return count;
    }
    void main()
    {
        unsigned char ch = 255;
        int count = Count(ch);
        cout<<"count = "<<count<<endl;
    }

3、 时间复杂度是与1的个数有关的算法

#include<iostream>
    using namespace std;
    int Count(unsigned char v)
    {
        int count = 0;
        while(v != 0)
        {
            v &= (v-1);//相当于与v-1的最后一位与运算，把最后一位1置0，只需要循环count次
            count++;
        }
        return count;
    }
    
    void main()
    {
        unsigned char ch = 255;
        int count = Count(ch);
        cout<<"count = "<<count<<endl;
    }

4、 分支法

#include<iostream>
    using namespace std;
    int Count(unsigned char v)
    {
         int count = 0;
         switch (v)
         {
              case 0x0:
                   count = 0;
                   break;
              case 0x1:
              case 0x2:
              case 0x4:
              case 0x8:
              case 0x10:
              case 0x20:
              case 0x40:
              case 0x80:
                   count = 1;
                   break;
              case 0x3:
              case 0x6:
              case 0xc:
              case 0x18:
              case 0x30:
              case 0x60:
              case 0xc0:
                   count = 2;
                   break;
                   //...
             // [注意] 此处需要把代码补齐
          }
          return count;     
    }
    void main()
    {
        unsigned char ch = 255;
        int count = Count(ch);
        cout<<"count = "<<count<<endl;
    }

看似简单，实际效率可能会低于方法二和三、具体要看a的值，这种方法并不可取，但是提供了一种空间换时间的思路，在程序实现利用公式得出结论。

5、 查表法  
不需要任何的比较就能得出结论，在时间复杂度上可以说是高山仰止了。

#include<iostream>
    using namespace std;
    int countTable[256] =
    {
         0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
            3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3,
            4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,
            3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3,
            4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
            6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4,
            5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3,
            4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4,
            4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6,
            7, 6, 7, 7, 8
    };//按BIT位组合出255个数组
    int Count(unsigned char v)
    {
         return countTable[v];//输出的数直接返回表里1的数字。
    }
    void main()
    {
        unsigned char ch = 255;
        int count = Count(ch);
        cout<<"count = "<<count<<endl;
    }

总结： 方法三直接算出1的个数 比较可行 执行效率高 实际开发需要按照实际情况来有个选择。五种方法都需体会。