编程之美Ex1——求二进制中1的个数

又被阿里机考虐了一次，决定改变策略开始刷题T^T

一个字节（8bit）的无符号整型，求其二进制中的“1”的个数，算法执行效率尽可能高。

最先想到的移位操作，末尾位&00000001，然后右移，算法复杂度为O（log（v））

 #include "stdafx.h"

 #include <iostream>

 using namespace std;

 int Count(int v);

 int main()

 {

     int v = ;

     int num = Count(v);

     cout<<num<<endl;

     return ;

 }

 int Count(int v)

 {

     int num = ;

     while(v)

     {

         num += v &0x01;

         v >>= ;

     }

     return num;

 }

还有一种算法复杂度为O（1）的，就是利用查表法，空间来换取时间，经典的理念。

http://blog.csdn.net/justpub/article/details/2292823

但是，看了上述博客后，发现弊端，这个操作需要访问内存，运行时间比法一长很多。

【扩展】：给定两个正整数（二进制表示）A和B，问把A变成B需要改变多少位，也就是说，两者的二进制表示中有多少位不同？

取一个C = A^B，C中1的个数就是A和B不同的位数。

巴特西

编程之美Ex1——求二进制中1的个数

最新文章

热门文章