Find the binary gap of a number N

Question

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps.

I'd like to know how this would be performance wise, and if there is a better way to do it.

public int solution(int N) {
    int binaryGap = 0;
    String binaryString = Integer.toBinaryString(N);
    char[] characters = binaryString.toCharArray();
    int j = 0;
    Character c;
    for (int i = 0; i < characters.length; i++) {
         c = characters[i];
        if (c.equals('0')) {
            j += 1;
        }

        if (c.equals('1')) {
            if (j > binaryGap ){
                binaryGap = j;
            }
            j = 0;
        }

    }
    System.out.println(binaryGap);
    return binaryGap;

}

Answer 1

Your current code allocates several objects on the heap even though it doesn't need to. A string, a character array and several character objects.

Puzzles like this can often be solved not by inspecting each bit individually but by processing them in parallel. An alternative approach is:

To find the binary gap of n:

• Discard all trailing zeros by replacing them with ones.
• As long as n does not consist of 1s only:
  • Combine n with n shifted to the right by one place, thereby making each gap one bit smaller.
• The number of repetitions is the length of the largest gap.

Taking 1000010001000 as an example:

1000010001000   with trailing zeros
1000010001111   after 0 steps
1100011001111   after 1 step
1110011101111   after 2 steps
1111011111111   after 3 steps
1111111111111   after 4 steps

It took 4 steps, therefore the binary gap is 4.

In Java, this code becomes:

public static int binaryGap(int n) {
    n |= n - 1;
    int steps = 0;
    while ((n & (n + 1)) != 0) {
        n |= n >>> 1;
        steps++;
    }
    return steps;
}

As mentioned in the above description, this code runs in \$\mathcal O(\text{gap})\$, which is a little better than \$\mathcal O(\text{bits})\$.

It might be worth making it run in \$\mathcal O(\log_2 \text{gap})\$ by first taking 16 steps at once, then 8, then 4, then 2, then 1. If that's possible at all. For 32 bits it's entirely possible to compare all results of the optimized version against the simple code shown above. But then I guess the code will become much more complicated.

Answer 2

Tweaks

    Character c;
    for (int i = 0; i < characters.length; i++) {
         c = characters[i];

You can write this more simply as

    for (Character c : characters) {

Then i is Java's problem.

Plus, this is clearer. It says directly what is being done. For each character in the string, do these things.

            j += 1;

You could write this as

            j++;

which is more idiomatic.

        }

        if (c.equals('1')) {

You could replace this with either

        } else if (c == '1') {

or

        } else {

After all, what else would it be? It's a binary string. And obviously you don't have to check that it's not '0'. You just did that.

You don't need to use equals with a character, as it reduces to a primitive type (char). You can do so here, but you don't have to do so.

I'd move the println outside the method. Then you can choose to output or not.

Performance

Very little of that will make any performance difference. What could though would be to stop mucking with strings. It's possible to work directly with the integer.

public static int solution(int N) {
    int binaryGap = 0;

    if (N == 0) {
        return 0;
    }

    // remove trailing zeroes if not counted; credit to Peter Taylor
    while (N % 2 == 0) {
        N /= 2;
    }

    for (int j = 0; N > 0; N /= 2) {
        if (N % 2 == 0) {
            j++;
        } else {
            if (j > binaryGap) {
                binaryGap = j;
            }

            j = 0;
        }
    }

    return binaryGap;
}

This is essentially what the Integer.toBinaryString does to build the string. Doing it like this means that we don't have to do it twice.

You could also use bit operations instead of division and modulus. Ideally the compiler should do that for you if it would be faster. But you could benchmark instead.

There's an argument that you should leave the declaration of j outside the for loop. Since you don't iterate over j. But you also don't use j outside the loop, so the scope is right this way.

Answer 3

There's a small issue with your algorithm, and is that it will calculate the binary gap even if doesn't exist, like with a 6 (110) it will return one instead of zero, my suggestion will be just add a flag like:

public static int solution(int N) {
    int binaryGap = 0;
    boolean found_one = false;

    for (int j = 0; N > 0; N /= 2) {
        if (N % 2 == 0) {
            j++;
        } else {
            if (j > binaryGap && found_one == true){
                binaryGap = j;
            }
            found_one = true;
            j = 0;
        }
    }

    return binaryGap;
}

Answer 4

Firstly, you should make N constant by putting final modifier in front of it in the prototype.

Secondly, Java implements strings using a character array, there is no performance gain in converting the string to an array (binaryString.charAt(i) takes the same amount of time as characters[i]). Also, using the class Character with .equals is actually hurting performance, as creating a class and using .equals takes longer than using the char type and == operator. So, you can slightly increase the space and time complexity of your program. But since it is so basic, you wouldn't notice it with an integer, you'd probably not notice the difference with a BigInteger.

Lastly, one small improvement you can make in the logic of your method is checking how many digits are left in your string. For example, if you have the string 100001001, by the time you get to the second 1, there is no possible way the binary gap could be larger than what you have already found, since there are only 3 digits left, but you found a gap of size 4, in best case the next one could only be 2, no need to continue checking, so just return.