Binary Gap

Problem

Given a positive integer n, find and return the longest distance between any two adjacent 1’s in the binary representation of n. If there are no two adjacent 1’s, return 0.

Two 1’s are adjacent if there are only 0’s separating them (possibly no 0’s). The distance between two 1’s is the absolute difference between their bit positions. For example, the two 1’s in "1001" have a distance of 3.

Constraints

• 1 <= n <= 105

Solution

The problem Binary Gap can be solved by converting the given number to bits and calculating the distance between 1’s.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    int binaryGap(int n)
    {
        int ret = 0;
        for (int left = INT_MAX, right = 0; n > 0; right++)
        {
            if (n & 1)
            {
                ret = max(ret, right - left);
                left = right;
            }
            n >>= 1;
        }

        return ret;
    }
};