题目描述

给定一个正整数 n，找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离 。如果不存在两个相邻的 1，返回 0 。

如果只有 0 将两个 1 分隔开（可能不存在 0 ），则认为这两个 1 彼此 相邻 。两个 1 之间的距离是它们的二进制表示中位置的绝对差。例如，“1001” 中的两个 1 的距离为 3 。

示例

输入：n = 22
输出：2
解释：
22 的二进制是 “10110” 。
在 22 的二进制表示中，有三个 1，组成两对相邻的 1 。
第一对相邻的 1 中，两个 1 之间的距离为 2 。
第二对相邻的 1 中，两个 1 之间的距离为 1 。
答案取两个距离之中最大的，也就是 2 。

源代码

class Solution {
public:
    int binaryGap(int n) {
    	//建立一个数组存放二进制n的0和1
        int arr[100]={0};
        int i=0,count=0;//count为二进制n中1的个数
        while(n){
            if(n&1)  //如果二进制n的最后一位是1
            {
                arr[i]++;
                count++;   
            }
            i++;
            n=n>>1;    //二进制n向右移一位
        }
        if(count<=1) return 0;
        int sum=0; //sum表示最大间距
        for(int j=0;j<i;j++)
        {
            if(arr[j]==1)
            {
                for(int k=j+1;k<i;k++)
                {
                    if(arr[k]==1)
                    {
                        if(k-j>sum) sum=k-j;
                        break;
                    }
                }
            }
        }
        return sum;
    }
};