Encuentre la secuencia más larga de 1 en representación binaria con un giro

Da un número entero n. Podemos voltear exactamente un bit. Escriba código para encontrar la longitud de la secuencia más larga de 1 s que podría crear. 

Ejemplos: 

Input : 1775         
Output : 8 
Binary representation of 1775 is 11011101111.
After flipping the highlighted bit, we get 
consecutive 8 bits. 11011111111.

Input : 12         
Output : 3 

Input : 15
Output : 5

Input : 71
Output: 4

Binary representation of 71 is 1000111.
After flipping the highlighted bit, we get 
consecutive 4 bits. 1001111. 

Una solución simple es almacenar la representación binaria de un número dado en una array binaria. Una vez que tenemos elementos en una array binaria, podemos aplicar los métodos discutidos aquí .

Una solución eficiente es recorrer los bits en la representación binaria del número dado. Realizamos un seguimiento de la longitud de la secuencia del 1 actual y la longitud de la secuencia del 1 anterior. Cuando veamos un cero, actualice la longitud anterior:  

1. Si el siguiente bit es un 1, la longitud anterior debe establecerse en la longitud actual.
2. Si el siguiente bit es un 0, entonces no podemos fusionar estas secuencias. Por lo tanto, establezca la longitud anterior en 0.

Actualizamos la longitud máxima comparando los dos siguientes:  

1. El valor actual de max-length
2. Duración actual + Duración anterior .

• Resultado = devuelve la longitud máxima + 1 (// agrega 1 para el conteo de bits invertidos)

A continuación se muestra la implementación de la idea anterior: 

// C++ program to find maximum consecutive
// 1's in binary representation of a number
// after flipping one bit.
#include<bits/stdc++.h>
using namespace std;
 
int flipBit(unsigned a)
{
    /* If all bits are l, binary representation
       of 'a' has all 1s */
    if (~a == 0)
        return 8*sizeof(int);
 
    int currLen = 0, prevLen = 0, maxLen = 0;
    while (a!= 0)
    {
        // If Current bit is a 1 then increment currLen++
        if ((a & 1) == 1)
            currLen++;
 
        // If Current bit is a 0 then check next bit of a
        else if ((a & 1) == 0)
        {
            /* Update prevLen to 0 (if next bit is 0)
            or currLen (if next bit is 1). */
            prevLen = (a & 2) == 0? 0 : currLen;
 
            // If two consecutively bits are 0
            // then currLen also will be 0.
            currLen = 0;
        }
 
        // Update maxLen if required
        maxLen = max(prevLen + currLen, maxLen);
 
        // Remove last bit (Right shift)
        a >>= 1;
    }
 
    // We can always have a sequence of
    // at least one 1, this is flipped bit
    return maxLen+1;
}
 
// Driver code
int main()
{
    // input 1
    cout << flipBit(13);
    cout << endl;
 
    // input 2
    cout << flipBit(1775);
    cout << endl;
 
    // input 3
    cout << flipBit(15);
    return 0;
}

// Java program to find maximum consecutive
// 1's in binary representation of a number
// after flipping one bit.
 
class GFG
{
 
    static int flipBit(int a)
    {
        /* If all bits are l, binary representation
        of 'a' has all 1s */
        if (~a == 0)
        {
            return 8 * sizeof();
        }
 
        int currLen = 0, prevLen = 0, maxLen = 0;
        while (a != 0)
        {
            // If Current bit is a 1
            // then increment currLen++
            if ((a & 1) == 1)
            {
                currLen++;
            }
             
            // If Current bit is a 0 then
            // check next bit of a
            else if ((a & 1) == 0)
            {
                /* Update prevLen to 0 (if next bit is 0)
                or currLen (if next bit is 1). */
                prevLen = (a & 2) == 0 ? 0 : currLen;
 
                // If two consecutively bits are 0
                // then currLen also will be 0.
                currLen = 0;
            }
 
            // Update maxLen if required
            maxLen = Math.max(prevLen + currLen, maxLen);
 
            // Remove last bit (Right shift)
            a >>= 1;
        }
 
        // We can always have a sequence of
        // at least one 1, this is flipped bit
        return maxLen + 1;
    }
 
    static byte sizeof()
    {
        byte sizeOfInteger = 8;
        return sizeOfInteger;
    }
     
    // Driver code
    public static void main(String[] args)
    {
        // input 1
        System.out.println(flipBit(13));
 
        // input 2
        System.out.println(flipBit(1775));
 
        // input 3
        System.out.println(flipBit(15));
    }
}
 
// This code is contributed by PrinciRaj1992

# Python3 program to find maximum
# consecutive 1's in binary
# representation of a number
# after flipping one bit.
def flipBit(a):
     
    # If all bits are l,
    # binary representation
    # of 'a' has all 1s
    if (~a == 0):
        return 8 * sizeof();
 
    currLen = 0;
    prevLen = 0;
    maxLen = 0;
    while (a > 0):
         
        # If Current bit is a 1
        # then increment currLen++
        if ((a & 1) == 1):
            currLen += 1;
 
        # If Current bit is a 0
        # then check next bit of a
        elif ((a & 1) == 0):
             
            # Update prevLen to 0
            # (if next bit is 0)
            # or currLen (if next
            # bit is 1). */
            prevLen = 0 if((a & 2) == 0) else currLen;
 
            # If two consecutively bits
            # are 0 then currLen also
            # will be 0.
            currLen = 0;
 
        # Update maxLen if required
        maxLen = max(prevLen + currLen, maxLen);
 
        # Remove last bit (Right shift)
        a >>= 1;
 
    # We can always have a sequence
    # of at least one 1, this is
    # flipped bit
    return maxLen + 1;
 
# Driver code
# input 1
print(flipBit(13));
 
# input 2
print(flipBit(1775));
 
# input 3
print(flipBit(15));
     
# This code is contributed by mits

// C# program to find maximum consecutive
// 1's in binary representation of a number
// after flipping one bit.
using System;
 
class GFG
{
  
    static int flipBit(int a)
    {
        /* If all bits are l, binary representation
        of 'a' has all 1s */
        if (~a == 0)
        {
            return 8 * sizeof(int);
        }
  
        int currLen = 0, prevLen = 0, maxLen = 0;
        while (a != 0)
        {
            // If Current bit is a 1
            // then increment currLen++
            if ((a & 1) == 1)
            {
                currLen++;
            }
              
            // If Current bit is a 0 then
            // check next bit of a
            else if ((a & 1) == 0)
            {
                /* Update prevLen to 0 (if next bit is 0)
                or currLen (if next bit is 1). */
                prevLen = (a & 2) == 0 ? 0 : currLen;
  
                // If two consecutively bits are 0
                // then currLen also will be 0.
                currLen = 0;
            }
  
            // Update maxLen if required
            maxLen = Math.Max(prevLen + currLen, maxLen);
  
            // Remove last bit (Right shift)
            a >>= 1;
        }
  
        // We can always have a sequence of
        // at least one 1, this is flipped bit
        return maxLen + 1;
    }
  
    // Driver code
    public static void Main(String[] args)
    {
        // input 1
        Console.WriteLine(flipBit(13));
  
        // input 2
        Console.WriteLine(flipBit(1775));
  
        // input 3
        Console.WriteLine(flipBit(15));
    }
}
  
// This code contributed by Rajput-Ji

<?php
// PHP program to find maximum consecutive
// 1's in binary representation of a number
// after flipping one bit.
 
function flipBit($a)
{
    /* If all bits are l,
       binary representation
       of 'a' has all 1s */
    if (~$a == 0)
        return 8 * sizeof();
 
    $currLen = 0;
    $prevLen = 0;
    $maxLen = 0;
    while ($a!= 0)
    {
         
        // If Current bit is a 1
        // then increment currLen++
        if (($a & 1) == 1)
            $currLen++;
 
        // If Current bit is a 0
        // then check next bit of a
        else if (($a & 1) == 0)
        {
             
            /* Update prevLen to 0
               (if next bit is 0)
               or currLen (if next
               bit is 1). */
            $prevLen = ($a & 2) == 0? 0 : $currLen;
 
            // If two consecutively bits are 0
            // then currLen also will be 0.
            $currLen = 0;
        }
 
        // Update maxLen if required
        $maxLen = max($prevLen + $currLen, $maxLen);
 
        // Remove last bit (Right shift)
        $a >>= 1;
    }
 
    // We can always have a sequence of
    // at least one 1, this is flipped bit
    return $maxLen+1;
}
 
    // Driver code
    // input 1
    echo flipBit(13);
    echo "\n";
 
    // input 2
    echo flipBit(1775);
    echo "\n";
 
    // input 3
    echo flipBit(15);
     
// This code is contributed by aj_36
?>

<script>
 
    // Javascript program to
    // find maximum consecutive
    // 1's in binary representation
    // of a number
    // after flipping one bit.
     
    function flipBit(a)
    {
        /* If all bits are l,
        binary representation
        of 'a' has all 1s */
        if (~a == 0)
        {
            return 8 * sizeof(int);
        }
    
        let currLen = 0, prevLen = 0, maxLen = 0;
        while (a != 0)
        {
            // If Current bit is a 1
            // then increment currLen++
            if ((a & 1) == 1)
            {
                currLen++;
            }
                
            // If Current bit is a 0 then
            // check next bit of a
            else if ((a & 1) == 0)
            {
                /* Update prevLen to 0
                (if next bit is 0)
                or currLen (if next bit is 1). */
                prevLen = (a & 2) == 0 ? 0 : currLen;
    
                // If two consecutively bits are 0
                // then currLen also will be 0.
                currLen = 0;
            }
    
            // Update maxLen if required
            maxLen = Math.max(prevLen + currLen, maxLen);
    
            // Remove last bit (Right shift)
            a >>= 1;
        }
    
        // We can always have a sequence of
        // at least one 1, this is flipped bit
        return maxLen + 1;
    }
     
    // input 1
    document.write(flipBit(13) + "</br>");
 
    // input 2
    document.write(flipBit(1775) + "</br>");
 
    // input 3
    document.write(flipBit(15));
                                 
</script>

Producción : 

4
8
5

Este artículo es una contribución del Sr. Somesh Awasthi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuido@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.