Biggest Binary Gap Solution

Question

Inspired by this question I've come up with a solution of my own. The task is to find longest sequence of zeroes surrounded by ones in a binary representations of an integer (e.g. 1041 == 0b10000010001, thus the answer is 5). The task also requires the complexity of \$O(log(N))\$. As far as I understand it means that it means linear complexity in terms of digits, whose number is \$log(N)\$. Am I correct in this conclusion?

private int biggestBinaryGap(int n) {
    while (endsWithZero(n))
        n >>= 1;
    return biggestBinaryGapRec(n >> 1);
}

private int biggestBinaryGapRec(int n) {
    if (n == 0)
        return 0;

    int gap = 0;
    for (; endsWithZero(n); n >>= 1, gap++);
    return Math.max(gap, biggestBinaryGapRec(n >> 1));

}

private boolean endsWithZero(int n) {
    return n > 0 && (n & 1) == 0;
}

Answer 1

Working at a bit-wise level for this problem is a superior option than converting it to a string like the linked question (your inspiration) did.

There may be some really tricky magic that can be done with complicated AND/OR/XOR/NOT operations to identify the gaps in a more efficient way, but your solution of "walking" the bits is adequate from an algorithmic perspective.

Note, in your code you have special handling for negative values, but that's not needed if you use the >>> operator for right shifting. Read up on the difference between signed and unsigned right shifts: http://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.19

The recursion bothers me, though. The overhead for creating a stack frame for each level of recursion, calling the function, etc. seems overkill for something that would be "trivial" with a while-loop.

public static int maxGap(int n) {
    // get rid of right-hand zeros
    while (n != 0 && (n & 1) == 0) {
        n >>>= 1;
    }

    int max = 0;
    int gap = 0;
    while (n != 0) {
        if ((n & 1) == 0) {
            gap++;
            max = Math.max(gap, max);
        } else {
            gap = 0;
        }
        n >>>= 1;
    }
    return max;
}

Now, that runs in \$O(log(n))\$ time where n is the integer being tested.... but, can it be a bit quicker?

I don't think the time complexity can be significantly improved (i.e. I can't see an \$O(1)\$ solution, but I can see some grunt performance improvements out there... assuming that Integer.numberOfTrailingZeros() function is better than O(N) performance:

public static int maxGapX(int n) {
    if (n == 0) {
        return 0;
    }
    int rbits = Integer.numberOfTrailingZeros(n);
    int max = 0;

    // shift off any initial right-most zeros in the init step.
    // then treat any subsequent 1's as the end of a span of zeros.
    for (n >>>= (rbits + 1); n != 0; n >>>= (rbits + 1)) {
        rbits = Integer.numberOfTrailingZeros(n);
        max = Math.max(max, rbits);
    }
    return max;
}

I put this up in an ideone here: https://ideone.com/hllRUa