欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-08 15:29:58
...

今后继续整理算法并写出自己的理解和备注。 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的个数 比较可行 执行效率高 实际开发需要按照实际情况来有个选择。五种方法都需体会。