Why do these two loops return different results?
I have a loop for calculating the total hamming distance between two strings.
For the input:
nums = [4,14,2]
One version of the loop:
n, ans = len(nums), 0
for i in range(32):
bit, cnt = 1<<i, 0
for num in nums:
cnt += num & bit
ans += cnt * (n-cnt)
return ans
Gives the wrong result: -84
While an almost identical loop:
n, ans = len(nums), 0
for i in range(32):
bit, cnt = 1<<i, 0
for num in nums:
cnt += (num & bit) > 0
ans += cnt * (n-cnt)
return ans
Gives the correct answer 6. I can figure out why?
What does the '> 0' in the second loop do? I tried to understand it's effect using a simple test:
>>> i = -5
>>> i += 1
>>> i
-4
>>> i = -5
>>> i += 1 > 0
>>> i
-4
and the '> 0' doesn't seem to do anything. Why are the two loops different?
num & bit
is not the same as num & bit > 0
;
num & bit
is a number (int
), while num & bit > 0
is a boolean (bool
);
in python, a True
boolean is 1
when used as a number;
>>> i = -5
>>> i += 2
>>> i
-3
>>> i = -5
>>> i += 2 > 0
>>> i
-4
as a rule of thumb, dont test with 1
or 0
; test with a random number (2
is also bad but easy to read here);
It's because some of the num&bit
are bigger than 0, so (i.e there was one 8
in my run):
>>> a=8
>>> a>0
True
>>> int(a>0)
1
It's not 8
!!!
So that's why.