【Day_11 0506】求最大连续bit数

求最大连续bit数

题目来源

牛客网：求最大连续bit数

题目描述

求一个int类型数字对应的二进制数字中1的最大连续数，例如3的二进制为00000011，最大连续2个1

数据范围：数据组数：1≤t≤5 ，1≤n≤500000
进阶：时间复杂度：O(logn) ，空间复杂度：O(1)

输入描述

输入一个int类型数字

输出描述

输出转成二进制之后连续1的个数

示例1

输入

200

输出

2

说明

200的二进制表示是11001000，最多有2个连续的1。

思路分析

• 求二进制的1，优先使用按位与的方法
• 和1按位与判断最低位是否为1，若为1则给计数器count自增，并与之前的最大值max比较，取两者较大的赋值给max，每次count自增后都要更新max的值，保证max始终保存的是最大值
• 如果中间出现一位不是1，那么连续便中断了，将计数器count置为0
• 每次相与后右移一位，判断下一位，直到输入的数为0

代码展示

#include <iostream>
#include <vector>
using namespace std;

int main() {
    
    int n = 0;
    while (cin >> n)
    {
    
        int count = 0;
        int max = 0;
        while (n)
        {
    
            //和1相与，判断最低位是否为1
            if ((n & 1) == 1)
            {
    
                count++;
                if (count > max)
                {
    
                    max = count;
                }
            }
            //连续中断，count赋值为0
            else
            {
    
                count = 0;
            }
            //每次将n右移一位
            n >>= 1;
        }
        cout << max;
    }
}