题目的主要信息：

• 求一个int类型数字对应的二进制数字中1的最大连续数
• 进阶要求：时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，空间复杂度：$O(1)O(1)$

方法一：连除法

具体做法：

将十进制转换成二进制的方法可以用连除取余法，那我们不断连除2，每次都取余2得到最后一位的二进制数，然后检查该二进制数是否为1，如果是1则统计计数，如果不为1说明连续中断了，比较获取最大值，并更新统计计数为0.

#include<iostream>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        int count = 0; //记录每次统计的连续1的个数
        int max_count = 0; //记录最大连续1的个数
        while(n){
            if(n % 2 == 1) //最后一位为1
                count++;
            else{ //遇到不为1
                max_count = max(max_count, count); //更新最大值
                count = 0; //从0开始
            }
            n /= 2; //去掉最后一位
        }
        max_count = max(max_count, count); //最后一次更新最大值
        cout << max_count << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，连除取余一共$lo{g}_{2}nlog\_2n$次
• 空间复杂度：$O(1)O(1)$，无额外空间

方法二：位运算

具体做法：

当一个数和自己左移一位进行位与运算，相当于和自己错开一位进行的位与运算，如果有连续的1，经过错位位与之后会少一个1，如果没有连续的1，错位位与之后就是0。那么我们可以通过这种不断与自己的左移一位位与，直到为0，什么时候结束就说明最大有多少连续的1。

#include<iostream>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        int count = 0;
        for(; n != 0; count++) //统计能够运算多少次
            n &= n << 1; //与自己左移一位后比较
        cout << count << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，平均复杂度低于上述方法一，因为不用遍历0位的情况，但是最坏复杂度还是$O(lo{g}_{2}n)O(log\_2n)$
• 空间复杂度：$O(1)O(1)$，无额外空间