CODEWITHSUNDEEP
python
Alex Kinman
Alex Kinman

Reputation: 2615

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?

Upvotes: 1

Views: 66

Answers (3)

Ankush K
Ankush K

Reputation: 332

On the line

cnt += num & bit

you are incrementing the value of cnt by 1,2,4,8 values.

While on the line

cnt += (num & bit) > 0

first you are validating the statement, which returns 0 or 1 then you are incrementing value by either 0 or 1.

You can cross check it by printing cnt value in both the codes.

Upvotes: 0

Cyker
Cyker

Reputation: 10954

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);

Upvotes: 1

U13-Forward
U13-Forward

Reputation: 71610

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.

Upvotes: 1

Related Questions