Problem
In Leetcode it states that my runtime is only faster than 38% all of submitted JavaScript solutions. Is there anything I can change to make it more efficient?
/**
* @param {number} x
* @param {number} y
* @return {number}
*/
var hammingDistance = function(x, y) {
var resultStr =( x^y);
let count =0;
while(resultStr>0){
resultStr =(resultStr&resultStr-1) ;
count++;
}
return count;
};
Solution
A few things could be changed here, non of which I mention are optimisation however. Your solution is almost identical to the example on the wiki page where you can see hardware optimisations if supported, though the example does not apply to JavaScript.
Naming
The Str in resultStr seems to imply that it’s a string but that’s not the case. result may be better suited, or val which is a common choice for this.
While count is perfectly fine, distance might make it’s purpose more obvious (especially since “distance” is in the function name).
Parentheses
There’s a bunch of parentheses that aren’t needed, adding spacing around operators makes it easier to follow.
Shorthand operators/spacing
You can take advantage of shorthand operators:
resultStr = resultStr & resultStr - 1 can be simplified to resultStr &= resultStr - 1
Another added benefit is that in this example we don’t have to worry about operator precedence.
ES6
Since you’re using ES6 features such as let you can take advantage additional features such as const and => (arrow functions).
ES6 – const/let
Favour let and const over var. You are already declaring count with let so it would make sense to do the same for resultStr.
If we declare const hammingDistance = ... it means that if we later try and reassign hammingDistance = ... we will get a TypeError.
I recommend using const whenever you don’t need to reassign a variable. Note this does not mean the variable is immutable, just that it cannot be reassigned.
ES6 – arrow functions
I’ve opted to use arrow function notation over traditional syntax here. Your example does not benefit from any of the advantages such as lexical this so feel free to change back to function(x, y) as this is a personal choice.
Solution
Here’s your code with the suggested changes:
const hammingDistance = (x, y) => {
let val = x ^ y;
let distance = 0;
while (val > 0) {
val &= val - 1;
distance++;
}
return distance;
};
For loop solution
If you wanted, you could replace the while loop with a for loop as follows:
const hammingDistance = (x, y) => {
let val = x ^ y;
let distance;
for (distance = 0; val > 0; distance++) {
val &= val - 1;
}
return distance;
};
Your implementation (with bugs fixed as per the other answer) is very efficient for small Hamming distances, but the cost scales as the Hamming distance. To make it more efficient you should make it independent of the Hamming distance by parallelising it. I’m not sure how best to adjust this for JavaScript’s weird type system: are you assuming that the input values are 32-bit integers or 52-bit integers? For 32-bit integers the given code can be directly ported:
const hammingDistance = (x, y) => {
let val = x ^ y;
val -= (val >> 1) & 0x55555555;
val = (val & 0x33333333) + ((val >> 2) & 0x33333333);
val += (val >> 4) & 0xF0F0F0F;
return (val * 0x1010101) >> 24;
};