Return to Answer

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.
• As long as n does not consist of 1s only:
  • Combine n with n shifted to the right by one place.
• The number of repetitions is the length of the largest gap.

Taking 1000010001000 as an example:

1000010001   after 0 steps
1100011001   after 1 step
1110011101   after 2 steps
1111011111   after 3 steps
1111111111   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 >>>= Integer.numberOfTrailingZeros(n);
    int steps = 0;
    while ((n & (n + 1)) != 0) {
        n |= n >>> 1;
        steps++;
    }
    return steps;
}

As said in the above description, this code runs in \$\mathcal O(\text{gap})\$, which is a bit 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.

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.

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 the individual bits but by processing them in parallel. An alternative approach is:

To find the binary gap of n:

• Discard all trailing zeros.
• As long as n does not consist of 1s only:
  • Combine n with n shifted to the right by one place.
• The number of repetitions is the length of the largest gap.

Taking 1000010001000 as an example:

1000010001   after 0 steps
1100011001   after 1 step
1110011101   after 2 steps
1111011111   after 3 steps
1111111111   after 4 steps

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

In Java, this code becomes:

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

As said in the above description, this code runs in \$\mathcal O(\text{gap})\$, which is a bit 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.

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.
• As long as n does not consist of 1s only:
  • Combine n with n shifted to the right by one place.
• The number of repetitions is the length of the largest gap.

Taking 1000010001000 as an example:

1000010001   after 0 steps
1100011001   after 1 step
1110011101   after 2 steps
1111011111   after 3 steps
1111111111   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 >>>= Integer.numberOfTrailingZeros(n);
    int steps = 0;
    while ((n & (n + 1)) != 0) {
        n |= n >>> 1;
        steps++;
    }
    return steps;
}

As said in the above description, this code runs in \$\mathcal O(\text{gap})\$, which is a bit 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.

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 the individual bits but by processing them in parallel. An alternative approach is:

To find the binary gap of n:

• Discard all trailing zeros.
• As long as n does not consist of 1s only:
  • Combine n with n shifted to the right by one place.
• The number of repetitions is the length of the largest gap.

Taking 1000010001000 as an example:

1000010001   after 0 steps
1100011001   after 1 step
1110011101   after 2 steps
1111011111   after 3 steps
1111111111   after 4 steps

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

In Java, this code becomes:

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

As said in the above description, this code runs in \$\mathcal O(\text{gap})\$. It can be made to run in \$\mathcal O(\log_2 \text{gap})\$ by first taking 16 steps at once, then 8, then 4, then 2, then 1. This would make the code a little longer though. For understanding the underlying concept, the above code is better than the optimized version.

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 the individual bits but by processing them in parallel. An alternative approach is:

To find the binary gap of n:

• Discard all trailing zeros.
• As long as n does not consist of 1s only:
  • Combine n with n shifted to the right by one place.
• The number of repetitions is the length of the largest gap.

Taking 1000010001000 as an example:

1000010001   after 0 steps
1100011001   after 1 step
1110011101   after 2 steps
1111011111   after 3 steps
1111111111   after 4 steps

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

In Java, this code becomes:

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

As said in the above description, this code runs in \$\mathcal O(\text{gap})\$, which is a bit 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.