首页 > 试题广场 >

求最大连续bit数

[编程题]求最大连续bit数

热度指数：136884 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

数据范围：数据组数： $1\le t\le 5\$ ， $1\le n\le 500000\$

进阶：时间复杂度： $O(logn)\$ ，空间复杂度： $O(1)\$

输入描述:

输入一个int类型数字

输出描述:

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

示例1

输入

输出

说明

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

算法知识视频讲解

超小白

肯定是用位运算了，一边右移一边统计，不断更新count和max

#include<iostream>
using namespace std;

int main(){    
    int byte;
    while(cin>>byte){
        int max =0;
        int count =0;
        while(byte){
            int flag =0;
            while(byte && (byte & 1)){
                byte=byte>>1;
                count++;
            }
            if(!(byte&1)){
                if(count>max)
                    max = count;
                count=0;
                byte = byte>>1;
            }
        }
        cout<<max<<endl;
    }
    
    return 0;
}

编辑于 2016-06-20 07:22:28 回复(2)

牛客-120抢救中心

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int input = sc.nextInt();
            String bi = Integer.toBinaryString(input);
            String subs = "1";
            int cnt = 1;
            for(int i=1; i<=bi.length(); i++) {
                if(bi.contains(subs)) {
                    cnt = subs.length();
                    subs += "1";
                }
            }
            System.out.println(cnt);
        }
    }
}

发表于 2018-10-08 23:15:14 回复(5)

InGodWeTrust

import java.util.Scanner;
public class Main{
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int a=sc.nextInt();
            System.out.println(getNums(a));
        }
    }
    
    private static int getNums(int a){
        if(a==0)	return 0;
        String str=Integer.toBinaryString(a);
        int count=0;
        int max=0;
        for(int i=0;i+1<str.length();i++){
            if(str.charAt(i)=='1'&&str.charAt(i)==str.charAt(i+1)){
                 count++;
                if(count>max){
                    max=count;
                }
            }
            else{
                count=0;
            }
        }
        return max+1;
    }
}

发表于 2017-05-24 16:22:49 回复(2)

viod

2进制转换，除2取余，逆序排列。

#include<stdio.h>
int main(){
    int n;
    while(~scanf("%d",&n)){
        int max=1;  //假设当前最大连续为1
        for(int seq=0;n>0;n/=2){
            if(n%2!=0){
                seq++;  //连续进行累加
                if(seq>max) max=seq;  //如果超过就修改当前最大连续数
            }
            else seq=0;  //断连就重置计数
        }printf("%d\n",max);
    }
}

发表于 2022-03-31 02:15:26 回复(0)

Python 3

牛客968767289号

while True:
    try:
        b_nums=list(map(int,bin(int(input())).replace('0', ' ' ).replace('b', ' ').split()))
        print(len(str(max(b_nums))))
    except:
        break

发表于 2022-02-08 14:17:36 回复(0)

萌个腿

#include <stdio.h>

int main()
{
    int input;
    int num,max;
    while(scanf("%d",&input)!=EOF)
    {
        num=0;
        max=0;
        while(input)
        {
            if(input%2==1)
                num++;
            else
                num=0;
            max=max>num?max:num;
            input=input/2;
        }
        printf("%d\n",max);
    }
    return 0;
}

循环除2，%2余1则计数+1,%2余0则计数归零，最后保存计数最大值。

发表于 2021-12-10 21:53:52 回复(0)

Java

迈克尔·哪儿都有我·乔丹

import java.util.Scanner;

public class Main {

     public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sbf = new StringBuilder();
        while (sc.hasNext()) {
            int num = sc.nextInt();
            int max = 0;
            while (num / 2 != 0) {
                sbf.append(num % 2);
                num = num / 2;
            }
            sbf.append(1);
            String string1 = sbf.reverse().toString();

            String[] strings = string1.split("0");
            
            for (String string : strings) {
                if (string.contains("1")) {
                    max = Math.max(string.length(), max);
                }
            }
            System.out.println(max);
            sbf.replace(0, sbf.length(), "");
        }
    }
}
/**
按正常十进制转二进制得到结果，但是值为反，构造StringBuilder取反
最后分片取出值为连续一的字符串的最大长度 
*/

发表于 2021-12-08 09:35:07 回复(0)

Python 3

Snow君

while True:
    try:
        bit = bin(int(input()))[2:].split('0')
        num = 1
        for i in bit:
            if len(i) > num:
                num = len(i)
        print(num)
    except:
        break

发表于 2021-10-12 22:13:18 回复(0)

Java

牛客最小的小白

import java.util.Scanner;

//转二进制字符串，双指针法
// public class Main{
//     public static void main(String[] args){
//         Scanner sc = new Scanner(System.in);
//         while(sc.hasNext()){
//             int num = sc.nextInt();
//             String s = Integer.toBinaryString(num);
//             int left=0, right=0;
//             int maxLen=0;
//             while(right<s.length()){
//                 if(s.charAt(right)=='1'){//1处
//                     right++;
//                 }else{//0处
//                     if(right-left>maxLen){//更新最大值
//                         maxLen=right-left;
//                     }
//                     if(left!=right) left=right;//更新left
//                     left++;
//                     right++;
//                 }
//             }
            
//             //处理末尾连续1的情况
//             if(right-left>maxLen) maxLen=right-left;
//             System.out.println(maxLen);
//         }
//     }
// }

//位运算法
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int num = sc.nextInt();
            int maxLen=0, temp=0;
            while(num!=0){
                if((num&1)==1){//遇到末尾1，temp加1
                    temp++;
                    maxLen = maxLen>temp ? maxLen:temp;
                }else{//遇到末尾0，temp置零，重新计数
                    temp=0;
                }
                num >>>= 1;//逻辑右移
            }
            System.out.println(maxLen);
        }
    }
}

发表于 2021-08-17 09:08:19 回复(0)

Python 3

sunshine_c

while True:
    try:
        n = int(input())
        count = 0
        res = 0
        while n:
            count += n&1
            n >>= 1
            if not n&1:
                if count > res:
                    res = count
                count = 0
        print(res)
    except:
        break

思路：从后往前找，在碰到0之前一直计数，如果连续1的计数超过当前记录值，则赋给记录的变量；一旦碰到0，计数恢复为0，再碰到1重新计数

发表于 2021-08-12 23:46:09 回复(0)

66_6

while True:
    try:
        m = int(input())
        re = []
        cnt=0
        while m!=0:
            if m%2 ==1:
                cnt += 1
                re.append(cnt)
            else:
                cnt=0
            m = m >> 1
        print(max(re))
    except:
        break

发表于 2021-08-07 20:07:23 回复(0)

80后大叔

使用位运算，向右减少，低位为1则表示除2余1
#include<stdio.h>
int main(){
    int in;
    while(scanf("%d",&in)!=EOF){
        int count=0;
        int max=0;
        do{
            if(in%2==1){
                count++;
                max=max>count?max:count;
            }else{
                count=0;
            }
        }while((in=in>>1)>0);
        printf("%d\n",max);
    }
}

发表于 2021-08-06 19:30:29 回复(0)

山大崇新小小小小小芳

Python解法

用0当作分隔符，再计算每片的长度就可以了

while True:
    try:
        n = int(input())
        bn = bin(n).replace("0b","").split("0")
        m = 0
        for i in bn:
            if len(i)>m:
                m = len(i)
        print(m)
    except:
        break

发表于 2021-04-12 23:52:23 回复(0)

Java

牛客43509880号

import java.util.Scanner;
public class Main {
   public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		while(input.hasNext()) {
			int num =input.nextInt();
			String str=dexToBinary(num);
			char[] chars =str.toCharArray();//将字符串转换为字符数组\
			int count=0,maxcount=0;
			for (int i = 0; i < chars.length; i++) {
				if(chars[i]=='1') {
					count++;
				}
				else {
					maxcount = Math.max(maxcount, count);
		            count = 0;
				}
			}
		     maxcount = Math.max(maxcount, count);
		     System.out.println(maxcount);
		}
		input.close();
	}

	public static String dexToBinary(int decNum) {
		String binary = "";  //转换好的二进制字符串
		while(decNum!=0) {
			int temp=decNum%2;   //取余数
				binary = temp +binary;//每取一个余数，就往前拼接
			decNum/=2;
		}
		//System.out.println(binary);
		return binary;	
	
	
	}	     
}

发表于 2021-04-01 10:58:47 回复(0)

__24

while True:
    try:
        print(max(len(k) for k in bin(int(input()))[2:].split('0')))
    except:
        break

发表于 2021-01-11 18:04:40 回复(0)

Python

JeremyStar

# 思路：二进制字符串中只有1和0两种字符，那么我们以‘0’作为分隔符(刀)来切割二进制串。
# 遇到每个'0'就切一刀，若刀和刀之间没有内容，则为空字符串，也包含在结果当中。
# 如：字符串'111000101100111111'.split('0')得到['111', '', '', '1', '11', '', '111111']
# 我们只需统计结果列表中最大的长度是几，即为本题答案。

while True:
    try:
        ten = int(input().strip())
        bin = format(ten, 'b')
        print(max(map(len, bin.split('0'))))
    except:
        break

发表于 2020-12-06 11:14:17 回复(0)

走:路

一行代码解决

while True:
    try:
        print(max(list(map(len, bin(int(input()))[2:].split('0')))))
    except:
        break

发表于 2020-07-19 17:52:25 回复(0)

上大-黄志栋

评论区都是算法大佬，我还需要继续学习

while True:
    try:
        s = bin(int(input()))[2:]
        maxl, curl = 0, 0
        for i in s:
            if i == '1':
                curl += 1
                maxl = max(maxl, curl)
            else:
                curl = 0
        print(maxl)
    except:
        break

发表于 2020-07-18 20:30:25 回复(0)

Python

君临天下201804050931706

while True:
    try:
        n = int(input())
        s_list = "{0:b}".format(n).split("0")
        max1 = 0
        for i in range(len(s_list)):
            if(len(s_list[i])>max1):
                max1 = len(s_list[i])
        print(max1)
    except:
        break

发表于 2020-07-11 14:40:26 回复(1)

only_boy

#include <iostream>

using namespace std;
//通过取余数的操作可以查看二进制数中有多少个1
int main()
{
    int n;
    while(cin>>n)
    {
        int max = 0;
        int len = 0;
        while(n>0)
        {
            if(n%2 == 1) len++;
            else
            {
                max = max<len?len:max;
                len = 0;
            }
            n = n/2;
        }
        max = max<len?len:max;
        cout<<max<<endl;
    }

    return 0;
}

发表于 2020-07-11 09:53:39 回复(0)