求二进制中1的个数

比眉伴天荒 2024-04-19 13:55 62阅读 0赞

最关键内容：

判断某一位置是否是1的一个方法（可以跳过0，所以比全部位置循环一遍效率高），v&=(v-1);

例如： 01 000 000 &（01 000 000 - 00 000 001）= 01 000 000 &00 111 111 = 0。

int bit\_count(unsigned int n)  
\{  
    int count;  
    for(count = 0; n; n &= n - 1)  
    \{  
        count++;  
    \}  
    return count;  
\}

‍

原题是：“对于一个字节(8bit)的无符号整型变量，求其二进制表示中1的个数，要求算法的执行效率尽可能的高”

（1）第一种方法是通过对这个数字N求余数，如果求余后有余，那么表示当前位置有一个1，否则便没有。然后N=N/2

（2）第二种方法其实思想和第一种方法差不多，只不过N=N/2 改用移位来运算：N>>=1;然后用N 同1进行“与”运算，来判断末尾是否为1，如果N的二进制形式末尾有1，则“与”结果为1，否则为0. 方法(1)和(2)的时间复杂度都为O(log2N),因为N是以2的指数速度递减的。

（3）第三种方式，比较巧妙。

（4）效率最高应该是第五种方法，呵呵，他比较变态的将“0-255”的每个数二进制形式的“1”的个数保存成了一个数组，然后直接返回个数，时间复杂度为O(1).

但是如果对于一个字节的无符号整形变量还好，只有256个数字，但是如果对于32位的整形，这明显就不可取了。

扩展问题：“给定两个正整数（二进制形式表示）A和B,问把A变成B需要改变成多少位(bit)?也就是说，整数A和B的二进制表示中有多少位是不同的?”

要解此题，引入A和B的异或运算再合适不过了，如果**对于两个操作数按位异或，可以使得两个操作数中相同的“位”置为0，不同的“位”置为1.**

所以对于两个二进制如果异或，他们之间不相同的位置将会被标记出来(即置为1)。

方法1，最基本的用除法/2和%2来运算

\#include "stdafx.h"  
\#include<iostream>  
using namespace std;

int \_tmain(int argc, \_TCHAR\* argv\[\])  
\{

BYTE c;  
int a;  
cin>>a;  
    c=(BYTE)a;  
int cnt=0;  
while(c)  
\{  
   if(c%2==1)  
   \{  
    cnt++;  
   \}  
   c/=2;  
\}  
cout<<cnt<<endl;

::system("pause");  
return 0;  
\}

方法2，使用位操作

‍\#include "stdafx.h"  
\#include<iostream>

using namespace std;

int \_tmain(int argc, \_TCHAR\* argv\[\])  
\{

BYTE c;  
int a;  
cin>>a;  
    c=(BYTE)a; //注意直接scanf("%d",&c);会内存错误，原因是将一个整形放入char型中越界了  
int cnt=0;  
while(c)  
\{  
   if(c&0x01)  
   \{  
    cnt++;  
   \}  
   c>>=1;  
\}  
cout<<cnt<<endl;

::system("pause");  
return 0;  
\}

方法3，判断某一位置是否是1的一个方法，v&=(v-1);

最经典：

‍

位操作比除、余操作的效率高了很多。但是，即使采用位操作，时间复杂度仍为O（log2v），log2v为二进制数的位数。那么，还能不能再降低一些复杂度呢？如果有办法让算法的复杂度只与"1"的个数有关，复杂度不就能进一步降低了吗？

同样用10 100 001来举例。如果只考虑和1的个数相关，那么，我们是否能够在每次判断中，仅与1来进行判断呢？

为了简化这个问题，我们考虑只有一个1的情况。例如：01 000 000。

如何判断给定的二进制数里面有且仅有一个1呢？可以通过判断这个数是否是2的整数次幂来实现。另外，如果只和这一个"1"进行判断，如何设计操作呢？我们知道的是，如果进行这个操作，结果为0或为1，就可以得到结论。

如果希望操作后的结果为0，01 000 000可以和00 111 111进行"与"操作。

这样，要进行的操作就是 01 000 000 &（01 000 000 - 00 000 001）= 01 000 000 &00 111 111 = 0。

因此就有了解法三的代码：

‍

‍    循环中直接计算1的数量（即后面的方法3）  
     如何只数'1'的个数？如果一个数字至少包含一个'1'位，那么这个数字减1将从最低位开始依次向高位借位，直到遇到第一个不为'0'的位。依次借位使得经过的位由原来的'0'变为'1'，而第一个遇到的那个'1'位则被借位变为'0'。  
     36 d = 100100 b  
     36-1 d = 100011 b  
     如果最低位本来就是'1'，那么没有发生借位。  
     现在把这2个数字做按位与：n & (n-1)的结果是什么？  
     2个数字在原先最低为'1'的位以下（包括这个位）的部分都不同，所以结果是保留了其他的'1'位。  
     36 & (36-1) d = 100000 b  
     这个结果刚好去掉了最低的一个'1'位  
int bit\_count(unsigned int n)  
\{  
    int count;  
    for(count = 0; n; n &= n - 1)  
    \{  
        count++;  
    \}  
    return count;  
\}

由于直接跳过'0'位，这个方法比上面的要略微快一些。

‍\#include "stdafx.h"  
\#include<iostream>  
using namespace std;

int \_tmain(int argc, \_TCHAR\* argv\[\])  
\{

BYTE c;  
int a;  
cin>>a;  
    c=(BYTE)a; //注意直接scanf("%d",&c);会内存错误，原因是将一个整形放入char型中越界了  
int cnt=0;  
while(c)  
\{  
   c&=(c-1);  
   cnt++;  
\}  
cout<<cnt<<endl;

::system("pause");  
return 0;  
\}

方法4，打表

根据以下程序打表：

\#include "stdafx.h"  
\#include<iostream>  
\#include<stdio.h>  
using namespace std;  
//打表  
int table\[\]=  
\{  
0,1,1,2,1,2, 2,3,1,2

\};  
int \_tmain(int argc, \_TCHAR\* argv\[\])  
\{  
::freopen("data.txt","w",stdout);

int k=0;  
for(int i=0;i<256;i++)  
\{  
   int t=i;//注意必须重新保存i来进行更新，因为后面代码更新了i  
   k++;  
   int cnt=0;  
   while(t)  
   \{  
    if(t%2==1)  
    \{  
     cnt++;  
    \}  
    t/=2;  
   \}  
   cout<<cnt<<",";  
   if(k%10==0)  
    cout<<endl;  
\}

/\*  
BYTE c;  
int a;  
cin>>a;  
    c=(BYTE)a; //注意直接scanf("%d",&c);会内存错误，原因是将一个整形放入char型中越界了  
cout<<table\[c\]<<endl;  
\*/  
//::system("pause");  
return 0;  
\}

真正的程序代码，这应该是最快的代码了，因为是打表所以有O（1）。

‍\#include "stdafx.h"  
\#include<iostream>  
\#include<stdio.h>  
\#include<Windows.h>  
using namespace std;  
//打表  
int table\[\]=  
\{  
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  
\};  
int \_tmain(int argc, \_TCHAR\* argv\[\])  
\{   
BYTE c;//BYTE类型必须导入\#include<Windows.h>  
int a;  
cin>>a;  
c=(BYTE)a; //注意直接scanf("%d",&c);会内存错误，原因是将一个整形放入char型中越界了  
cout<<table\[c\]<<endl;

::system("pause");  
return 0;  
\}

转载于:https://my.oschina.net/alphajay/blog/28709