个人博客
题目描述:
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