leetcode-868-Binary Gap

chenjx85

发布于 2018-08-01 15:41:13

3750

发布于 2018-08-01 15:41:13

题目描述：

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

要完成的函数：

int binaryGap(int N)

说明：

1、这道题给定一个整数N，要求在N的二进制表示中找到两个连续的1（中间可以包含0），比如22的二进制表示10110中，第一位的1和第三位的1是两个连续的1，第三位的1和第四位的1是两个连续的1。

要求找到两个连续的1的最长距离，返回该距离。

2、这道题很容易，由于整数N在计算机中就是以二进制存储的，所以我们进行位操作，读取出1的位置进行计算。

代码如下：（附详解）

    int binaryGap(int N) 
    {
        int i,j,count=0,res=0;
        while(N)//读取出第一个1的位置（从后面读起），存储在i中
        {
            count++;//count表示当前处理的是哪一位
            if(N&1==1)
            {
                i=count;
                N>>=1;
                break;
            }
            N>>=1;//N不断右移
        }
        while(N)//读取所有1的位置
        {
            count++;
            if(N&1==1)
            {
                j=count;//把新的1的位置记录在j中
                res=max(res,j-i);//更新res值，存储最长的距离
                i=j;//更新i值到当前位置
            }
            N>>=1;//N不断右移
        }
        return res;
    }

上述代码实测4ms，beats 99.64% of cpp submissions。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-07-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度