leetcode刷题,求hamming weight

最近看到一个不错的刷题网站leetCode,于是就去刷题啦,提高一下水平。题目真的是,很有代表性啊,我喜欢!

写一个函数,求出一个无符号整数里面位为1的个数(也就是Hamming Weight算法),例如32位整数11,用二进制表示为00000000000000000000000000001011,因此函数返回值为3

原文如下

Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.

对于我这种对位操作只局限于理论上的少年,可把我难住了。

开始我用的是

count += n&0x01;
n = n>>1

结果,当n为2147483648(10000000000000000000000000000000),n>>1直接变成负数,我用的语言是php和javascript,整数是有符号的,当n>>1之后,最高位的符号位变成了0,直接成了负数了!所以这个行不通了

然后看了discussion之后,发现有一个很巧妙的方法

for(; n!=0; n=n&(n-1)){
    count++;
}

这个作用是从低位依次将1置0,然后只要n不为0,就一直循环操作下去,最终的结果n肯定会为0。

当然还有hamming算法啦,这个没研究过……
想去刷题的点这里!,以后就不重复啦

赞赏

微信赞赏支付宝赞赏

《leetcode刷题,求hamming weight》有1条评论

发表评论

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