5
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ I guess you could define n in terms of the bitcount and still look at an average O(logn) by searching for 0-intervals using devide and conquer (assuming a full n-bit integer zero-test is O(1)) - you'd need to check all intervals.. so worst case still O(n) (101010.. -> n/2 intervals)? \$\endgroup\$ – BeyelerStudios Feb 16 '17 at 13:59
6
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.