3
\$\begingroup\$

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of 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.

Can I get feedback on my code? This is for the Binary Gap problem. I got 100% in correctness, but I would like to know how I can make it better performance wise. Also, I am not even sure about its complexity and how to make it better.

class Solution {
    public int solution(int N) {
        // write your code in Java SE 8
        int max = 0;
        boolean flag = false;
        int temp = 0;

        //converting number into binary and at the same time checking for max binary gap
        while (N != 0) {

            if (N%2 == 1) {
                flag = true;
                if (temp > max) {
                    max = temp;
                }
                temp = 0;
            }
            else {
                if (flag) {
                    temp++;
                }   
            }

            N = N/2;
        }

        return max;
    }
}
\$\endgroup\$
2
\$\begingroup\$

Counting bits

When the main task involves bits, it's good to look for opportunities for bit shifting operations. For example, you can check if the last bit is 1 with:

if ((num & 1) == 1) {

And you can shift the bits to the right by 1 with:

num >>= 1;

These are more natural in this context than num % 2 == 1 and num /= 2. And often might perform better too.

Avoid flag variables

When possible, it's good to avoid flag variables.

You are using flag to indicate if you've ever seen a 1-bit. For each 0-bit, you check if the flag is set. This is inefficient.

There is a way to avoid this flag. You can first shift until the first 1-bit. That is, skip all the trailing zeros.

int work = N;
while (work > 0 && (work & 1) == 0) {
  work >>= 1;
}

At this point we have reached a 1, or the end. It's safe to shift one more time, in case the last bit is 1.

work >>= 1;

After this, we can start counting zeros, and reset the count every time we see a 1. There's no more need for a flag.

Naming

temp is not a great name for a variable that counts zeros. How about zeros instead?

Alternative implementation

Putting the above tips together (and a bit more), this is a bit simpler and shorter:

  public int solution(int N) {
    int work = N;
    while (work > 0 && (work & 1) == 0) {
      work >>= 1;
    }
    work >>= 1;

    int max = 0;
    int zeros = 0;

    while (work > 0) {
      if ((work & 1) == 0) {
        zeros++;
      } else {
        max = Math.max(max, zeros);
        zeros = 0;
      }
      work >>= 1;
    }
    return max;
  }
\$\endgroup\$
  • \$\begingroup\$ Thankyou @janos for such a thorough explanation. However, I am a little bit confused. I don't understand why you're using the first while loop. I understand the second part though. You shift the bits and check if the current bit is 0 or not, if yes add 1, if no then reset zeros and set max value, exactly what I was doing, but of course in a more efficient way. My question is what's the use of first while loop and why are we shifting bits there? \$\endgroup\$ – a-ina Jun 22 '17 at 11:05
  • \$\begingroup\$ @a-ina The first while loop is to strip the trailing zeros. They are useless, for example in 10010000000000000 the correct answer is 2. It is thanks to the first while loop that we don't need a flag anymore in the second whileloop. \$\endgroup\$ – Stop ongoing harm to Monica Jun 22 '17 at 11:29
1
\$\begingroup\$

Java provides an (intrinsic) method that returns the count of trailing zeros. This method can be used to largely reduce the count of checks by processing all consecutive 0s/1s at once instead of processing the provided number bit by bit.

import static java.lang.Integer.numberOfTrailingZeros;
import static java.lang.Math.max;
...
public static int solution(int n) {
    int max = 0;
    while ((n >>>= numberOfTrailingZeros(~(n | n - 1))) != 0)
        max = max(numberOfTrailingZeros(n), max);
    return max;
}

n >>>= numberOfTrailingZeros(~(n | n - 1)) removes all trailing zeros and all following 1s. (Rightpropagates the lowest bit and inverses -> i.e. ...00101100 becomes ...11010000, thus n would be shifted by 4 and become ...0010)

Approximated performance over 1<<20 random values (used System#nanoTime and not JMH, thus results not completely reliable, but the tendency is visible):

a-ina : 158 ns/op
janos : 114 ns/op
nevay :  24 ns/op
\$\endgroup\$
0
\$\begingroup\$

A minor addition to janos' answer.

I would add a little check to return fast for n < 5. Since 5 is the first number that actually has a "binary gap" (5 = 101).

public int solution(int N) {
    if(N < 5) {
        return 0;
    }

    int work = N;
    while ((work & 1) == 0) { 
      work >>= 1;
    }

I also simpified the first while since we are now sure that it contains a 1 bit.

EDIT: rossum pointed out why this doesn't do that much without first removing trailing zeros. So I looked up what else we can do. Java has a Integer.bitCout(number) that we could us.

So replace the N<5 with Integer.bitCount(N)<2 to make sure there are at least 2 bits set. This saves a lot of looping when N = 2^x.

\$\endgroup\$
  • 1
    \$\begingroup\$ You might want to put the test for < 5 after removing trailing zeros. That will catch 11000000 and similar. \$\endgroup\$ – rossum Jun 23 '17 at 14:28

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.