Compute Hamming Distance

Question

How can I make this code snippet better? Those for loops in if don't please me but they are covered with code lines that is dependent to if before and after.

public int hammingDistance(int x, int y) {
    String binx = Integer.toBinaryString(x);
    String biny = Integer.toBinaryString(y);

    int dif = 0;
    StringBuilder sb = new StringBuilder();

    if (binx.length() > biny.length()) {
        dif = binx.length() - biny.length();

        for (int i = 0; i < dif; i++) {
            sb.append(0);      
        }

        biny = sb.toString().concat(biny);
    } else if (biny.length() > binx.length()) {
        dif = biny.length() - binx.length();

        for (int i = 0; i < dif; i++) {
            sb.append(0);      
        }

        binx = sb.toString().concat(binx);
    }

    int dist = 0;

    for (int i = 0; i < binx.length(); i++) {
        if (binx.charAt(i) != biny.charAt(i)) {
            dist++;
        }    
    }

    return dist;
}

Answer 1

You're missing a big simplification. The hamming distance is the count of ones in x^y, so simply perform that xor and count the set bits. There should be no need to convert to string.

Answer 2

I'm agree with @TobySpeight's answer so I only focus on refactoring your if else code:

String binx = Integer.toBinaryString(x);
String biny = Integer.toBinaryString(y);
int dif = 0;
StringBuilder sb = new StringBuilder();
if (binx.length() > biny.length()) {
    dif = binx.length() - biny.length();
    for (int i = 0; i < dif; i++) {
          sb.append(0);      
    }
    biny = sb.toString().concat(biny);
} else if (biny.length() > binx.length()) {
       dif = biny.length() - binx.length();
       for (int i = 0; i < dif; i++) {
            sb.append(0);      
       }
       binx = sb.toString().concat(binx);
}

You can store the two String in one array and use them by index:

String[] bins =  { Integer.toBinaryString(x), Integer.toBinaryString(y) };
int[] lengths =  { bin[0].length(), bin[1].length() };

This can be simplified noting that the same block will be executed in both branchs if the absolute difference between binx and biny is not 0 so you can calculate abs of difference rewriting the block like below:

int dif = lengths[0] - lengths[1];
if (Math.abs(dif) != 0) {
    String s = String.join("", Collections.nCopies(dif, "0"));
    int i = dif > 0 ? 1 : 0;
    bins[i] = s + bins[i];
}

I used String.join and Collections.ncopies methods to obtain a string composed by n '0' chars.

Below the complete code of the method:

public static int hammingDistance(int x, int y) {
    String[] bins =  { Integer.toBinaryString(x), Integer.toBinaryString(y) };
    int[] lengths =  { bins[0].length(), bins[1].length() };

    int dif = lengths[0] - lengths[1];
    if (Math.abs(dif) != 0) {
        String s = String.join("", Collections.nCopies(dif, "0"));
        int i = dif > 0 ? 1 : 0;
        bins[i] = s + bins[i];
    }

    int dist = 0;
    for (int i = 0; i < lengths[0]; ++i) {
        if (bins[0].charAt(i) != bins[1].charAt(i)) {
            ++dist;
        }    
    }

    return dist;
}

Answer 3

I have suggestion for you.

1. I suggest that you extract the length of the binx and biny in two variables, so you can use them instead of recalling the java.lang.String#length each time.

String binx = Integer.toBinaryString(x);
int binxLength = binx.length();
String biny = Integer.toBinaryString(y);
int binyLength = biny.length();

//[...]
if (binxLength > binyLength) {
   //[...]
}
//[...]

2. You can use the method java.lang.String#repeat (java 11+) to repeat the zeros

  sb.append("0".repeat(dif));

3. I suggest that you make a method to repeat the zeros.

private String repeatZeros(int nb) {
   return "0".repeat(nb);
}

4. In my opinion, the dif variable is useless, you can inline it.

sb.append(repeatZeros(binxLength - binyLength));

5. Since you are not concatenating the String in a loop, instead of using the StringBuilder, you can concat them directly.

if (binxLength > binyLength) {
   biny = repeatZeros(binxLength - binyLength) + biny;
} else if (binyLength > binxLength) {
   binx = repeatZeros(binyLength - binxLength) + binx;
}

6. I suggest that you create a method to pad the binary string.

private String padLeftWithZeros(String str, int length) {
   return repeatZeros(length) + str;
}

public int hammingDistance(int x, int y) {
   //[...]
   if (binxLength > binyLength) {
      biny = padLeftWithZeros(biny, (binxLength - binyLength));
   } else if (binyLength > binxLength) {
      binx = padLeftWithZeros(binx, (binyLength - binxLength));
   }
   //[...]
}

6. I suggest that you extract the distance in a method and return the result.

public int hammingDistance(int x, int y) {
   //[...]
   return calculateHammingDistance(binx, binxLength, biny);
}

private int calculateHammingDistance(String binx, int binxLength, String biny) {
   int dist = 0;
   for (int i = 0; i < binxLength; i++) {
      if (binx.charAt(i) != biny.charAt(i)) {
         dist++;
      }
   }

   return dist;
}

Refactored code

public int hammingDistance(int x, int y) {
   String binx = Integer.toBinaryString(x);
   int binxLength = binx.length();
   String biny = Integer.toBinaryString(y);
   int binyLength = biny.length();

   if (binxLength > binyLength) {
      biny = padLeftWithZeros(biny, (binxLength - binyLength));
   } else if (binyLength > binxLength) {
      binx = padLeftWithZeros(binx, (binyLength - binxLength));
   }

   return calculateHammingDistance(binx, binxLength, biny);
}

private String padLeftWithZeros(String str, int length) {
   return repeatZeros(length) + str;
}

private String repeatZeros(int nb) {
   return "0".repeat(nb);
}

private int calculateHammingDistance(String binx, int binxLength, String biny) {
   int dist = 0;
   for (int i = 0; i < binxLength; i++) {
      if (binx.charAt(i) != biny.charAt(i)) {
         dist++;
      }
   }

   return dist;
}