Chinaunix首页 | 论坛 | 博客
  • 博客访问: 801643
  • 博文数量: 104
  • 博客积分: 915
  • 博客等级: 下士
  • 技术积分: 2171
  • 用 户 组: 普通用户
  • 注册时间: 2012-05-24 21:34
文章分类

全部博文(104)

文章存档

2018年(4)

2015年(14)

2014年(9)

2013年(56)

2012年(21)

分类: LINUX

2013-05-29 21:59:44

                                        

摘自《编程之美


Q:对于1个字节(8bit)无符号整型变量,求其二进制表示中“1”的个数

解法一:除2取余(对于二进制操作,除以一个2,原来的数字会减少一个0。如果除的过程中由余数,就表示当前位置有一个1)
代码如下:

int Count(BYTE v)
{
int num = 0;
while(v)
{
if(v%2 == 1)
num++;
v = v/2;
}
return num;
}
解法二:位移操作(对于二进制向右移位操作同样可以达到解法一的目的,但是比除、余操作效率高)
代码如下:
int Count(BYTE v)
{
int num = 0;
while(v)
{
num += v & 0x01;
v >>= 1;
}
return num;
}
解法三:只考虑有1的情况(清除最低位的1)
代码如下:
int Count(BYTE v)
{
int num = 0;
while(v)
{
v &= (v-1);
num++;
}
return num;
}
解法四:分支操作(看似直接,但是执行效率可能会低于解法二、三)空间换时间
代码如下:
int Count(BYTE v)
{
int num = 0;
switch(v)
{
case 0x0:
num = 0;
break;
case 0x1:
case 0x2:
case 0x4:
case 0x8:
case 0x10:
case 0x20:
case 0x40:
case 0x80:
num = 1;
break;
case 0x3:
case 0x6:
case 0xc:
case 0x18:
case 0x30:
case 0x60:
case 0xc0:
num = 2;
break;
//...
}
return num;
}
解法五:查表法空间换时间
把0~255中“1”的个数直接存储在数组中,v作为数组下标,countTable[v]就是v中“1”的个数。算法时间复杂度仅为O(1)
代码如下:
          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
};
int Count(BYTE v)
{
return countTbale[v];
}


以下摘自博客http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html

对于32位的DWORD,可以动态建表或静态建表

1)动态建表
由于表示在程序运行时动态创建的,所以速度上肯定会慢一些,把这个版本放在这里,有两个原因
        1.填表的方法,这个方法的确很巧妙。

        2.类型转换,这里不能使用传统的强制转换,而是先取地址再转换成对应的指针类型。

代码如下:
       int BitCount(unsigned int n)

       {

    // 建表
    unsigned char BitsSetTable256[256] = {0} ;


    // 初始化表
    for (int i = 0; i < 256; i++)
    {
        BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
    }


    unsigned int c = 0 ;

    // 查表

    unsigned char * p = (unsigned char *) &n ;


    c = BitsSetTable256[p[0]] + BitsSetTable256[p[1]] +
            BitsSetTable256[p[2]] +
BitsSetTable256[p[3]];
    return c ;
}

先说一下填表的原理,根据奇偶性来分析,对于任意一个正整数n


1.如果它是偶数,那么n的二进制中1的个数与n/2中1的个数是相同的,比如4和2的二进制中都有一个1,6和3的二进制中都有两个1。
为啥?因为n是由n/2左移一位而来,而移位并不会增加1的个数。


2.如果n是奇数,那么n的二进制中1的个数是n/2中1的个数+1,比如7的二进制中有三个1,7/2 = 3的二进制中有两个1。
为啥?因为当n是奇数时,n相当于n/2左移一位再加1。


再说一下查表的原理


对于任意一个32位无符号整数,将其分割为4部分,每部分8bit,对于这四个部分分别求出1的个数,再累加起来即可。而8bit对应2^8 = 256种01组合方式,这也是为什么表的大小为256的原因。


注意类型转换的时候,先取到n的地址,然后转换为unsigned char*,这样一个unsigned int(4 bytes)对应四个unsigned char(1 bytes),分别取出来计算即可。举个例子吧,以87654321(十六进制)为例,先写成二进制形式-8bit一组,共四组,以不同颜色区分,这四组中1的个数分别为4,4,3,2,所以一共是13个1,如下面所示。


10000111 01100101 01000011 00100001 = 4 + 4 + 3 + 2 = 13
2)静态建表
首先构造一个包含256个元素的表table,table[i]即i中1的个数,这里的i是[0-255]之间任意一个值。然后对于任意一个32bit无符号整数n,我们将其拆分成四个8bit,然后分别求出每个8bit中1的个数,再累加求和即可,这里用移位的方法,每次右移8位,并与0xff相与,取得最低位的8bit,累加后继续移位,如此往复,直到n为0。所以对于任意一个32位整数,需要查表4次。以十进制数2882400018为例,其对应的二进制数为10101011110011011110111100010010,对应的四次查表过程如下:红色表示当前8bit,绿色表示右移后高位补零。


第一次(n & 0xff) 10101011110011011110111100010010


第二次((n >> 8) & 0xff) 00000000101010111100110111101111


第三次((n >> 16) & 0xff)00000000000000001010101111001101


第四次((n >> 24) & 0xff)00000000000000000000000010101011
代码如下:
int BitCount7(unsigned int n)
{
        unsigned int table[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
    };
    return      table[n & 0xff] +
                    table[(n >> 8) & 0xff] +
                    table[(n >> 16) & 0xff] +
                    table[(n >> 24) & 0xff] ;
}
阅读(2625) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~