868.二进制间距

链接：868.二进制间距
难度：Easy
标签：位运算
简介：给定一个正整数 n，找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离 。如果不存在两个相邻的 1，返回 0 。

题解 1 - cpp

• 编辑时间：2022-03-22
• 内存消耗：5.9MB
• 编程语言：cpp
• 解法介绍：找 1，统计中间 0 的个数。

class Solution {
   public:
    int binaryGap(int n) {
        if (n == 0) return 0;
        int start = 0, ans = 0;
        while (start < 32 && (n & 1 << start) == 0) start++;
        for (int i = start + 1, prev = start; i < 32; i++) {
            // 统计存在11的情况
            if ((n & 1 << i) != 0) {
                if (i == prev + 1) {
                    ans = 1;
                    break;
                }
                prev = i;
            }
        }
        while (start < 32) {
            // 找1
            while (start < 32 && (n & 1 << start) != 0) start++;
            if (start == 32) break;
            int cnt = 0;
            // 找0
            while (start < 32 && (n & 1 << start) == 0) start++, cnt++;
            if (start == 32) break;
            ans = max(ans, cnt + 1);
        }
        return ans;
    }
};

题解 2 - cpp

• 编辑时间：2022-03-22
• 内存消耗：5.8MB
• 编程语言：cpp
• 解法介绍：一次遍历，找当前 1 前面的 1。

class Solution {
   public:
    int binaryGap(int n) {
        int ans = 0, prev = -1;
        for (int i = 0; i < 32; i++) {
            if ((n & 1 << i) == 0) continue;
            if (prev != -1) ans = max(ans, i - prev);
            prev = i;
        }
        return ans;
    }
};

题解 3 - cpp

• 编辑时间：2022-04-24
• 内存消耗：5.3MB
• 编程语言：cpp
• 解法介绍：遍历。

int binaryGap(int n) {
    int prev = -1, ans = 0;
    for (int i = 0; n; i++, n >>= 1) {
        int bit = n & 1;
        if (bit == 0) continue;
        if (prev != -1) ans = fmax(ans, i - prev);
        prev = i;
    }
    return ans;
}