题目描述

给定一个正整数 N，找到并返回 N 的二进制表示中两个连续的 1 之间的最长距离。

如果没有两个连续的 1，返回 0 。

样例

输入：22
输出：2
解释：
22 的二进制是 0b10110。
在 22 的二进制表示中，有三个 1，组成两对连续的 1。
第一对连续的 1 中，两个 1 之间的距离为 2。
第二对连续的 1 中，两个 1 之间的距离为 1。
答案取两个距离之中最大的，也就是 2。

输入：5
输出：2
解释：
5 的二进制是 0b101。

输入：6
输出：1
解释：
6 的二进制是 0b110。

输入：8
输出：0
解释：
8 的二进制是 0b1000。
在 8 的二进制表示中没有连续的 1，所以返回 0。

注意

• 1 <= N <= 10^9

算法

(模拟) $O(\log n)$

• 直接将 N 变成二进制表示，如果当前位为 1，且上一个 1 存在，则更新答案即可。

时间复杂度

• 仅需要将 N 分解为二进制，故时间复杂度为 $O(\log n)$。

空间复杂度

• 由于可以直接开变量记录上一个 1 的位置，所以只需要常数的空间。

C++ 代码

class Solution {
public:
    int binaryGap(int N) {
        int ans = 0, last = -1, c = 0;
        for (; N; N >>= 1, c++) {
            if (N & 1) {
                if (last != -1)
                    ans = max(ans, c - last);
                last = c;
            }
        }
        return ans;
    }
};