Finding binary gap in Java

Question

I want to know the performance of my code for following problem description.

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.

public static int getBinaryGap(int N) {
 if (N < 5) {
 return 0;
 }
 String binaryRep = Integer.toBinaryString(N);
 int currentGap = 0;
 int finalGap = 0;
 for (int i = 0; i+1 < binaryRep.length(); i++) {
 if (currentGap == 0) {
 if (binaryRep.charAt(i) == '1' && binaryRep.charAt(i + 1) == '0') {
 currentGap++;
 }
 } else {
 if (binaryRep.charAt(i + 1) == '0') {
 currentGap++;
 }
 if (binaryRep.charAt(i + 1) == '1') {
 finalGap = finalGap<currentGap ? currentGap:finalGap;
 currentGap = 0;
 }
 }
 }
 return finalGap;
}

Answer 1

Java conventions

In Java variables are written in "lowerCamelCase", starting with a lowercase letter, so please use getBinaryGap(int n). See also Oracle code conventions

String conversion

The performance can be increased because you use a conversion to String, while you can solve it using bit-fiddling only.

Complexity

You code has one loop, with all constant time operations. Integer.toBinaryString(int n) has cost that is linear with n. The total performance will be O(n), that is OK.

Bit flipping

Following your logic, but all as bit-test:

public static int getBinaryGapBitFiddling(int n) {
 if (n < 5) {
 return 0;
 }
 int currentGap = 0;
 int finalGap = 0;
 int currentBit;
 for (int i=0 ; (currentBit = (1<<i))< n; i++)
 {
 int nextBit = currentBit << 1;
 if (currentGap == 0) {
 if ( ((currentBit & n) > 0 ) && ((nextBit & n ) == 0 )) {
 currentGap++;
 }
 } else {
 if ((nextBit & n ) == 0) {
 currentGap++;
 }
 if ((nextBit & n ) > 0) {
 finalGap = finalGap<currentGap ? currentGap:finalGap;
 currentGap = 0;
 }
 }
 }
 return finalGap;
}

More optimizations

You could probably use bitmasks for faster scanning as well. For example 10 and 01 are the start and end of a run.

• George Koehler: (currentBit = (1<<i))< n can cause an infinite loop because 1<<i may overflow.
• Rob Audenaerde: Yes to be really sure use a long for the bits. Because the input is int this will be OK. And probably (on 64 architecture) just as fast. Or add a >= 0 check, because after overflow it will be negative.
• George Koehler: With n = 1761283695, your code gets stuck an infinite loop, but the original code succeeds.