计算长整数中的置位位数 [英] Counting number of set bits in a long number
问题描述
此问题已在此处得到了回答.
This question has been answered here.
我的查询是,按照方法1起作用,但是它的变化,即方法2无效,而是给出了预期输出值的两倍.我不知道为什么.
My query is, following approach-1 works, however the variation of it, that is approach-2 does not, rather it gives double the value of expected output. I can not find out why.
方法1
public class Solution {
public int numSetBits(long a) {
int count = 0;
long temp = 0;
for(int i = 0 ; i < 64 ; i++) { // 64-bit for long data-type
temp = 1;
temp = temp << i;
temp = a & temp;
if((temp > 0))
count++;
}
return count;
}
}
方法2
public class Solution {
public int numSetBits(long a) {
int count=0;
for(int i=0; i<64; i++) {
if((a & (1 << i))>0) count++;
}
return count;
}
}
推荐答案
第二种方法失败,因为1 << i
的结果是int
,而不是long
.因此,位掩码回绕了,因此a
的低32位被扫描了两次,而a
的高32位被忽略了.
The second approach fails because the result of 1 << i
is an int
, not a long
. So the bit mask wraps around, and so the lower 32 bits of a
get scanned twice, while the higher 32 bits of a
are left uncounted.
因此,当i
达到值32时,(1 << i)
不会是2 32 ,而是2 0 (即1),与当i
为0时.类似地,当i
为33时,(1 << i)
不会是2 33 ,而是2 1 ,...等等.
So, when i
reaches the value 32, (1 << i)
will not be 232, but 20 (i.e. 1), which is the same as when i
was 0. Similarly when i
is 33, (1 << i)
will not be 233, but 21, ...etc.
通过将常数1设为long
来纠正此问题:
Correct this by making the constant 1 a long
:
(1L << i)
这篇关于计算长整数中的置位位数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!