5
\$\begingroup\$

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;
};
\$\endgroup\$
8
\$\begingroup\$

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;
};
\$\endgroup\$
  • \$\begingroup\$ big thanks for the detailed explanation. The solutions seem to be working fine even without the precedence set explicitly. But that would be a better change. \$\endgroup\$ – Rohit Katyal Feb 3 '17 at 17:38
  • \$\begingroup\$ Actually Addition and Subtraction have higher precedence than majority of Bitwise operators. \$\endgroup\$ – Qwerty Jul 11 '17 at 11:17
  • \$\begingroup\$ @Qwerty, good spot - not sure how that happened. Thanks for being extra thorough \$\endgroup\$ – Craig Ayre Jul 11 '17 at 12:08
3
\$\begingroup\$

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;
};
\$\endgroup\$
  • \$\begingroup\$ assumption its a 32 bit integer \$\endgroup\$ – Rohit Katyal Feb 3 '17 at 17:35
  • \$\begingroup\$ it failed for 93 and 73 \$\endgroup\$ – Rohit Katyal Feb 6 '17 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.