Bit operation, no loop


  • 0
    Y

    http://blog.sina.com.cn/s/blog_5219378b0100kdhg.html

    整个程序是一个分治的思想。第一次我们把每相邻的两位加起来,得到每两位里1的个数,比如前两位10就表示原数的前两位有2个1。第二次我们继续两两相加,10+01=11,00+10=10,得到的结果是00110010,它表示原数前4位有3个1,末4位有2个1。最后一次我们把0011和0010加起来,得到的就是整个二进制中1的个数。程序中巧妙地使用取位和右移,比如第二行中$33333333的二进制为00110011001100....,用它和x做and运算就相当于以2为单位间隔取数。shr的作用就是让加法运算的相同数位对齐。

     class Solution {
        public:
            int hammingWeight(uint32_t n) {
                  n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
        		n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
        		n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
        		n = (n & 0x00FF00FF) + ((n >> 8) & 0x00FF00FF);
        		n = (n & 0x0000FFFF) + ((n >> 16) & 0x0000FFFF);
        		return n;
            }
        };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.