BinaryGap challenge

Question

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;
    }
}

Answer 1

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;
  }

Answer 2

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