题意

给一个数字，输出其二进制表示下最大连续1的个数

限制：数值不大于500000

方法

按二进制位查询

我们依次检验数值在二进制表示下的1位，2位，3位是否为1

也就是和1<<i做与运算

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)){
        int m = 0; // 最大连续
        int cur = 0; // 当前连续
        for(int i = 0;i < 32;i++){ // 位
            if(n & (1<<i)){ // 二进制与为1
                cur++; // 当前+1
                m = max(m,cur); // 更新最大连续长度
            }else{ // 为0
                cur = 0;
            }
        }
        printf("%d\n",m);
    }
    return 0;
}

复杂度分析

时间复杂度: 与数值二进制表示长度相关,$O(log(n))O(log(n))$

空间复杂度: 只用了常数个数个变量，所以空间复杂度为$O(1)O(1)$

递降查询

每次查询末位，查询后把末位去掉,

以200为例

所以最大连续的1的长度为2, 其实反过来看上面的序列也就是值的二进制从低位到高位

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)){
        int m = 0;
        int cur = 0;
        for(;n;n/=2){ // 每次去掉最后一位
            if(n & 1){ // 判断最低位
                cur++;
                m = max(m,cur);
            }else{
                cur = 0;
            }
        }
        printf("%d\n",m);
    }
    return 0;
}

复杂度分析

时间复杂度: 与数值二进制表示长度相关,$O(log(n))O(log(n))$

空间复杂度: 只用了常数个数个变量，所以空间复杂度为$O(1)O(1)$