# 868. Binary Gap

Given a positive integer `N`, find and return the longest distance between two consecutive 1’s in the binary representation of `N`.

If there aren’t two consecutive 1’s, return 0.

Example 1:

``````Input: 22
Output: 2
Explanation:
22 in binary is 0b10110.
In the binary representation of 22, there are three ones, and two consecutive pairs of 1's.
The first consecutive pair of 1's have distance 2.
The second consecutive pair of 1's have distance 1.
The answer is the largest of these two distances, which is 2.
``````

Example 2:

``````Input: 5
Output: 2
Explanation:
5 in binary is 0b101.
``````

Example 3:

``````Input: 6
Output: 1
Explanation:
6 in binary is 0b110.
``````

Example 4:

``````Input: 8
Output: 0
Explanation:
8 in binary is 0b1000.
There aren't any consecutive pairs of 1's in the binary representation of 8, so we return 0.
``````

Note:

• `1 <= N <= 10^9`

``````class Solution {
public:
int binaryGap(int N) {
vector<int> pos;
for (int i = 0; i < 32; ++i) {
if (((N >> i) & 1) != 0) pos.push_back(i);
}
int res = 0, n = pos.size();
for (int i = 1; i < n; ++i) {
res = max(res, pos[i] - pos[i - 1]);
}
return res;
}
};
``````

``````class Solution {
public:
int binaryGap(int N) {
int res = 0, last = -1;
for (int i = 0; i < 32; ++i) {
if (((N >> i) & 1) != 0) {
if (last >= 0) res = max(res, i - last);
last = i;
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/868

https://leetcode.com/problems/binary-gap/

https://leetcode.com/problems/binary-gap/discuss/149945/Simple-Java-(10-ms)

https://leetcode.com/problems/binary-gap/discuss/149835/C%2B%2BJavaPython-Dividing-by-2

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation