10
\$\begingroup\$

My code needs to take two ints and then check those ints to see if their binary representations have any differences. The function convertBits returns the number of differences between the two binary forms of the ints.

For example, you can change 31 to 14 by flipping the 4th and 0th bit:

31:  0 0 0 1 1 1 1 1
14:  0 0 0 0 1 1 1 0
---  ---------------
bit  7 6 5 4 3 2 1 0

Thus 31 and 14 should return 2.

My code works, but it is failing the time test. In short, it needs to be more efficient. I welcome any suggestions as to how to do this.

    import java.util.ArrayList;

    public class BinaryChecker {
        public static void main(String[] args){
             b call = new b();
             System.out.println(call.convertBits(31, 14));
        }

     public static int convertBits(int a, int b){
         int counter = 0;

         String A = Integer.toBinaryString(a);
         String B = Integer.toBinaryString(b);

         System.out.println("The binary value of " + a + " " + "is " +   A +"." + "The binary value of " + b + " " + "is " + B);
         //add to arraylist 1 and 2

         ArrayList<Character> String1 = new ArrayList<Character>();

         ArrayList<Character> String2 = new ArrayList<Character>();
         int size = 0;

         for(int i = 0; i < A.length(); i++){
             char Aa = A.charAt(i);
             String1.add(Aa);
         }
         for(int x = 0; x < B.length(); x++){
             char Bb = B.charAt(x);
             String2.add(Bb);
         }
         //check if String1 is 8 chars long and add 0 to beginning if not
         while (String1.size() != 8){
             String1.add(0, '0');
         }
         while (String2.size() != 8){
             String2.add(0, '0');
         }


         for (int i =0; i < String1.size(); i++){
             char biteA = String1.get(i);
             char biteB = String2.get(i);
             if(biteA != biteB){
                 counter++;
             }
         }


         return counter;
     }
}
\$\endgroup\$
29
\$\begingroup\$

There's no need to roll your own: the library support is there.

public static int convertBits(int a, int b) {
    return Integer.bitCount(a ^ b);
}

For what it's worth, I don't think convertBits is a very descriptive name for the method. I'd suggest something like countBitDifferences.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks, Peter. This worked. Feel pretty stupid, but only way to learn, I guess! Thanks again. \$\endgroup\$ – Archeofuturist Jul 6 '16 at 10:41
  • 7
    \$\begingroup\$ For educational purposes, you might be interested in checking out the source for the bitCount function as well. (And an explanation of how it works) \$\endgroup\$ – Sabre Jul 6 '16 at 14:58
  • 2
    \$\begingroup\$ @Sabre, although in some implementations the JIT may choose to replace that function with a direct CPU instruction. \$\endgroup\$ – Peter Taylor Jul 6 '16 at 15:02
  • \$\begingroup\$ @PeterTaylor Indeed. It's nice to know how it works, but you should always use library functions when available for just that reason ;) \$\endgroup\$ – Sabre Jul 6 '16 at 15:03
  • 3
    \$\begingroup\$ @SteveCox, I would consider the core language to be what is defined in the Java Language Specification, which only includes a small subset of the methods of java.lang.Integer. As far as I'm concerned, Integer.bitCount is part of the standard library. \$\endgroup\$ – Peter Taylor Jul 6 '16 at 16:27
13
\$\begingroup\$

Instead of messing with string I suggest looking up the binary operators (& | ^). They work per bit to AND OR or XOR them.

This means that a^b is a integer where only the bits that differ in a and b are set.

Then you just need to count those for which there is a special function in the Integer class:

public static int convertBits(int a, int b){
     int dif = a^b;
     return Integer.bitCount(dif);

}

This difference is usually called the Hamming distance.

\$\endgroup\$
  • 6
    \$\begingroup\$ True, hammingDistance is a better suggestion for the method name than mine. \$\endgroup\$ – Peter Taylor Jul 6 '16 at 10:43
  • \$\begingroup\$ I believe you meant int diff in your code. \$\endgroup\$ – Element118 Jul 7 '16 at 8:54
  • \$\begingroup\$ @Element118 or bitCount(dif); \$\endgroup\$ – ratchet freak Jul 7 '16 at 10:03
1
\$\begingroup\$

Proper formatting

It's for example common practice to add a space between ){ -> ) {. Also have a look at Java Style Guides.

Naming convention

Use lowerCamelCase for variables. String1 -> string1.

Furthermore usually you don't want to suffix strings with digits. Usually there're better solutions.

Know and use the tools the language provides

Use System.out.format instead of messy concatenation:

System.out.format("The binary value of %d is %s.", number, numberBits);

Use Enhanced For-Loops if you don't need the index

for (char bit : numberBits)

Use Split instead of doing it yourself but actually you don't even want to use any of that because you can just iterate over the string directly.

String[] bits = numberBits.Split("|");

Don't add unnecessary complexity

while (String1.size() != 8) {
  String1.add(0, '0');
}

Here you add zeros just so you have the guarantee that you have a list of size 8 but actually there's no need for that. Furthermore in Java an integer has 32 bits if the integer passed as input uses more than 8 bits you end up with an endless loop science your check is bad. To avoid mistakes like this in general you can use an operator such as <=.

So in case you're still wondering how you could solve the problem of not having a string length guarantee from above. Here's a possibility:

int bitCount = 0;
int size = Math.min(string1.size(), string2.size());
for (int i = 0; i < size; ++i) {
  if(string1.charAt(i) != string2.charAt(i)) {
    ++bitCount;
  }
}

So now you know that you counted all the bits that differ except the ones left which are in one of the two strings. So you can call something like this on both strings:

for (int i = size; i < string1.size(); ++i) {
  if (string1[i] != '0') ++bitCount;
}

or use even just use StringUtils.countMatches here. You do this because you know that every set bit differs. (remember to eliminate duplicate code)

Eliminate duplicate code

Well by telling you to remove all the code that was duplicate this should be already by done now.

Use the right solution for the right problem

As mentioned by others there's obviously Integer.bitCount which you can use together with a simple xor but if you wanted to roll your own which you shouldn't you could do so by implementing a well know algorithm such as the Hamming weight instead of doing weird string analysis.

Here's an example implementation I just wrote that should work:

public static int bitCount(int x) {
  final int m1 = 0x55555555;
  final int m2 = 0x33333333;
  final int m4 = 0x0f0f0f0f;
  final int h01 = 0x01010101;
  x -= (x >>> 1) & m1;
  x = (x & m2) + ((x >>> 2) & m2);
  x = (x + (x >>> 4)) & m4;
  return (x * h01) >>> 24;
}
\$\endgroup\$
0
\$\begingroup\$

Here is a simple version that shows how to count the bit differenses through bit manipulation.

EDIT:

static int BitDiffCount(int a, int b)
{
  var a_xor_b = a ^ b;
  int diffs = 0;

  for (int i = 0; i < 32; i++)
  {
    diffs += a_xor_b & 1;
    a_xor_b >>= 1;
  }
  return diffs;
}
\$\endgroup\$
  • \$\begingroup\$ If you're performing a bit-wise operation it seems odd to work with arithmetic operators and comparators. They don't express your intentions as good and they're error-prone since Java's integers are signed. You should use a_xor_b != 0, diffs += a_xor_b & 1, and a_xor_b >>>= 1 instead. >, %, and / don't do what you intend when a ^ b happens to have the sign bit set (I'm not saying “negative” because that would be a misleading interpretation). They're also slower. \$\endgroup\$ – David Foerster Jul 11 '16 at 9:13
  • \$\begingroup\$ @DavidFoerster: I see what you mean. I was a little to quick, as I only thought of positive values. I'll mark the answer the be deleted. \$\endgroup\$ – Henrik Hansen Jul 11 '16 at 9:45

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.