Find the binary gap of a number N

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  binaryGap ){
                binaryGap = j;
            }
            j = 0;
        }

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

}

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.

StackExchange Code Review Q#159650, answer score: 13