题解 | #求最大连续bit数#

求最大连续bit数

求最大连续bit数

/*
2022年09月21日 11:43:09
利用flag标记前一位是否为1
count统计的是当前区间内连续1的个数
每一次统计后存进vector中
当前位不是1的时候，count置0
最后输出vector最大的count
*/
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    bool flag = false; // 标记当前bit位是1
    int count = 0; // 统计连续的1
    vector<int> v(32); // 记录当前最大的count
    for(int i = 0; i <　32; ++i){
        if(n & (1<<i)){ // 当前位是1
            if(flag){ // 前一位也是1
                ++count;
                v[i] = count;
            }
            else{
            flag = true; // 标记当前位是1
            count = 1;
            v[i] = count;
            }
        }
        else{ // 当前位不是1
            flag = false;
            count = 0;
            v[i] = count;
        }
    }
    int maxCount = 0;
    for(auto e : v)
        maxCount = max(maxCount, e);
    cout << maxCount << endl;
    return 0;
}

/*
2022年09月21日 11:43:09
模2除2就可以不断判断最后一位是否为1
统计连续的1个数
不为1的时候，连续1中断了，count重置为0
并更新maxCount
最后n判断完了再更新一次maxCount
时间复杂度O(logN)
空间复杂度O(1)
*/
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int count = 0; // 统计连续1的个数
    int maxCount = 0; // 最大连续1个数
    while(n){
        if(n%2 == 1) // 最后一位为1
            ++count;
        else{
            maxCount = max(count, maxCount);
            count = 0;
        }
        n /= 2; // 去除最后一位
    }
    maxCount = max(count, maxCount);
    cout << maxCount << endl;
    return 0;
}

/*
2022年09月21日 11:43:09
位运算
一个数和自己左移一位进行位与运算，
相当于喝自己错开的一位进行与运算，
如果有连续的1，错位位与之后就少一个1，此时count++
如果没有连续的1，错位位与之后就是0，
时间复杂度O(logN)
空间复杂度O(1)
*/
#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int count = 0;
    while(n){
        n &= n << 1;
        ++count;
    }
    cout << count << endl;
    return 0;
}

补充：
如果想求一个数二进制位有几个1，用n与n-1与运算。
n &= n-1;