Return the number of bits (N) that will need to be changed in order to convert an integer(X), into another integer(Y).
Constraint: 0 <= X <= Y <= 2**128
Example:
X = 1, Y = 2 => N = 2
X = 2, Y = 3 => N = 1
X = 0, Y = 4 => N = 1
I have written following code, how to improve it?
def bit_diff(n1,n2):
cmn_d = n1 & n2
all_d = n1 | n2
diff = all_d - cmn_d
cnt = 0
while diff:
if diff & 1:
cnt+=1
diff>>=1
return cnt
print bit_diff(1,2)
cmn_d = n1 & n2 all_d = n1 | n2 diff = all_d - cmn_d
There is an operator for that:
diff = n1 ^ n2
Having found the bits that differ, you want to count the set bits of diff, also known as the population count or the Hamming weight. The approach you use is simple and valid, but there are higher performing approaches which parallelise it (see here and following sections).
However, the standard approaches for the fastest parallel implementations without direct hardware support are based on fixed-width integers, and they typically go to 32 bits or 64 bits; since your specification says that you want to support 128-bit integers, you'll have to extrapolate, although it's not that hard.
Style-wise, you could work on your variable naming (realizing that naming is one of the two hardest things in programming).
cmn_d could be common_digits, all_d all_digits and cnt count. This would make it slightly easier to read
Python also has an official style-guide, PEP8, which recommends using spaces around operators, so you would write diff >>= 1 and count += 1.
Performance wise, your code is already quite fast (not that surprising, considering that it does just bit-shifts), so I don't think a different approach is needed here, although the improvement in @PeterTaylors answer is slightly faster:
+----+----+--------+--------------+
| n1 | n2 | Harsha | Peter Taylor |
+----+----+--------+--------------+
| 1 | 2 | 322 ns | 276 ns |
| 2 | 3 | 255 ns | 202 ns |
| 0 | 4 | 389 ns | 326 ns |
+----+----+--------+--------------+
So, unless you need to run this more than a few million times per second on small cases, your implementation should be fine (with the small modification of using n1 ^ n2).
n1 ^ n2 is 128 bits long, to cover that average case.
\$\endgroup\$
– Peter Taylor
Apr 18 '17 at 15:22
Python is slow compared to C, but it'll work:
def bit_diff(n1,n2):
i = n1 ^ n2
c = 0
while i:
i &= i - 1
c += 1
return c
print bit_diff(1,2)
This is faster:
def bit_diff(n1,n2):
i = n1 ^ n2
c = bin(i).count("1")
return c
print (bit_diff(34247483290175849302758**6500,43287543289074382905743**6500))
2506164
[Finished in 1.0s]
You can also use lookup tables if you need to do this faster, Google the terms "Hamming weight" and "popcount". SSE4 includes an instruction POPCNT, if you use C it will be very fast.
