CSAPP bitcount

CSAPP bitcount题目描述:bitCount-returnscountofnumberof1’sinwordExamples:bitCount(5)=2,bitCount(7)=3Legalops:!~&^|+<<>>Maxops:40Rating:4解题思路(思路参考StackOverflow)本题采取…

个人博客

题目描述:

bitCount – returns count of number of 1’s in word
Examples: bitCount(5) = 2, bitCount(7) = 3
Legal ops: ! ~ & ^ | + << >>
Max ops: 40
Rating: 4

 

解题思路(思路参考StackOverflow)

本题采取的是分而治之的思想:

Step1:将二进制数写为两位一组,分别计算当前两位中1的个数,并根据结果生成新的二进制数,举例:01 11->01 10

Step2:和第一步结果相似,不同的是从两位一组变成了四位一组,接下来的过程依次类推

为了方便解释接下来会引入一个具体的数,此处使用的是395

395的二进制表示:0000000110001011

由上述step1操作得到:

0000000110001011 (0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1)//395的二进制表示
0000000101000110 (0+0 0+0 0+0 0+1 1+0 0+0 1+0 1+1) = 00 00 00 01 01 00 01 10

通过step2得:

0000000101000110 ( 00 00   00 01   01 00   01 10 )//step1中的结果
0000000100010011 ( 00+00   00+01   01+00   01+10 ) = 0000 0001 0001 0011

依次类推:

0000000100010011 (   0000 0001       0001 0011   )//step2中获得结果
0000000100000100 (   0000+0001       0001+0011   ) = 00000001 00000100

最后得出结果:

0000000000000101 (       00000001+00000100       ) = 5

 

具体实现如下:

int bitCount(int x)
{
    int count;

    int tmpMask1=(0x55) | (0x55 << 8);
    int mask1 = (tmpMask1) | (tmpMask1 << 16); //得到掩码 01010101...01010101

    int tmpMask2 = (0x33) | (0x33 << 8);
    int mask2 = (tmpMask2) | (tmpMask2 << 16); //得到掩码 00110011...00110011

    int tmpMask3 = (0x0f) | (0x0f << 8);
    int mask3 = (tmpMask3) | (tmpMask3 << 16);//得到掩码  00001111...00001111

    int mask4 = (0xff) | (0xff <<16); //得到掩码  0000 0000 1111 1111 0000 0000 1111 1111

    int mask5 = (0xff) | (0xff << 8);//得到掩码: 0000 0000 0000 0000 1111 1111 1111 1111

    count = (x & mask1) + ((x >> 1) &mask1);
    count = (count & mask2) + ((count >> 2) & mask2);
    count = (count & mask3) + ((count >> 4) & mask3);
    count = (count & mask4) + ((count >> 8) & mask4);
    count = (count & mask5) + ((count >> 16) & mask5);

    return count;
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/38338.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注