Máximo de 0 entre dos 1 inmediatos en representación binaria

Dado un número n, la tarea es encontrar el máximo de 0 entre dos 1 inmediatos en representación binaria de n dado. Devuelve -1 si la representación binaria contiene menos de dos unos.

Ejemplos: 

Input : n = 47
Output: 1
// binary of n = 47 is 101111

Input : n = 549
Output: 3
// binary of n = 549 is 1000100101

Input : n = 1030
Output: 7
// binary of n = 1030 is 10000000110

Input : n = 8
Output: -1
// There is only one 1 in binary representation
// of 8.

La idea para resolver este problema es utilizar el operador shift . Solo necesitamos encontrar la posición de dos 1 inmediatos en representación binaria de n y maximizar la diferencia de estas posiciones. 

• Devuelve -1 si el número es 0 o es una potencia de 2. En estos casos, hay menos de dos 1 en representación binaria.
• Inicialice la variable prev con la posición del primer 1 más a la derecha, básicamente almacena la posición del 1 visto anteriormente.
• Ahora tome otra variable cur que almacena la posición del 1 inmediato justo después de prev .
• Ahora tome la diferencia de cur – prev – 1 , será el número de 0 entre los 1 inmediatos y compárelo con el valor máximo anterior de 0 y actualice prev ie; prev=cur para la próxima iteración.
• Use la variable auxiliar setBit , que escanea todos los bits de n y ayuda a detectar si los bits actuales son 0 o 1.
• Inicialmente verifique si N es 0 o potencia de 2 .

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

// C++ program to find maximum number of 0's
// in binary representation of a number
#include <bits/stdc++.h>
using namespace std;
 
// Returns maximum 0's between two immediate
// 1's in binary representation of number
int maxZeros(int n)
{
    // If there are no 1's or there is only
    // 1, then return -1
    if (n == 0 || (n & (n - 1)) == 0)
        return -1;
 
    // loop to find position of right most 1
    // here sizeof int is 4 that means total 32 bits
    int setBit = 1, prev = 0, i;
    for (i = 1; i <= sizeof(int) * 8; i++) {
        prev++;
 
        // we have found right most 1
        if ((n & setBit) == setBit) {
            setBit = setBit << 1;
            break;
        }
 
        // left shift setBit by 1 to check next bit
        setBit = setBit << 1;
    }
 
    // now loop through for remaining bits and find
    // position of immediate 1 after prev
    int max0 = INT_MIN, cur = prev;
    for (int j = i + 1; j <= sizeof(int) * 8; j++) {
        cur++;
 
        // if current bit is set, then compare
        // difference of cur - prev -1 with
        // previous maximum number of zeros
        if ((n & setBit) == setBit) {
            if (max0 < (cur - prev - 1))
                max0 = cur - prev - 1;
 
            // update prev
            prev = cur;
        }
        setBit = setBit << 1;
    }
    return max0;
}
 
// Driver program to run the case
int main()
{
    int n = 549;
 
    // Initially check that number must not
    // be 0 and power of 2
    cout << maxZeros(n);
    return 0;
}

// Java program to find maximum number of 0's
// in binary representation of a number
class GFG {
 
    // Returns maximum 0's between two immediate
    // 1's in binary representation of number
    static int maxZeros(int n) {
        // If there are no 1's or there is only
        // 1, then return -1
        if (n == 0 || (n & (n - 1)) == 0) {
            return -1;
        }
        //int size in java is 4 byte
        byte b = 4;
        // loop to find position of right most 1
        // here sizeof int is 4 that means total 32 bits
        int setBit = 1, prev = 0, i;
        for (i = 1; i <= b* 8; i++) {
            prev++;
 
            // we have found right most 1
            if ((n & setBit) == setBit) {
                setBit = setBit << 1;
                break;
            }
 
            // left shift setBit by 1 to check next bit
            setBit = setBit << 1;
        }
 
        // now loop through for remaining bits and find
        // position of immediate 1 after prev
        int max0 = Integer.MIN_VALUE, cur = prev;
        for (int j = i + 1; j <= b * 8; j++) {
            cur++;
 
            // if current bit is set, then compare
            // difference of cur - prev -1 with
            // previous maximum number of zeros
            if ((n & setBit) == setBit) {
                if (max0 < (cur - prev - 1)) {
                    max0 = cur - prev - 1;
                }
 
                // update prev
                prev = cur;
            }
            setBit = setBit << 1;
        }
        return max0;
    }
 
    // Driver program to run the case
    static public void main(String[] args) {
        int n = 549;
 
        // Initially check that number must not
        // be 0 and power of 2
        System.out.println(maxZeros(n));
    }
}
 
// This code is contributed by 29AjayKumar

# Python3 program to find maximum number of
# 0's in binary representation of a number
 
# Returns maximum 0's between two immediate
# 1's in binary representation of number
def maxZeros(n):
    # If there are no 1's or there is
    # only 1, then return -1
    if (n == 0 or (n & (n - 1)) == 0):
        return -1
 
    # loop to find position of right most 1
    # here sizeof is 4 that means total 32 bits
    setBit = 1
    prev = 0
    i = 1
    while(i < 33):
        prev += 1
 
        # we have found right most 1
        if ((n & setBit) == setBit):
            setBit = setBit << 1
            break
 
        # left shift setBit by 1 to check next bit
        setBit = setBit << 1
 
    # now loop through for remaining bits and find
    # position of immediate 1 after prev
    max0 = -10**9
    cur = prev
    for j in range(i + 1, 33):
        cur += 1
 
        # if current bit is set, then compare
        # difference of cur - prev -1 with
        # previous maximum number of zeros
        if ((n & setBit) == setBit):
            if (max0 < (cur - prev - 1)):
                max0 = cur - prev - 1
 
            # update prev
            prev = cur
        setBit = setBit << 1
 
    return max0
 
# Driver Code
n = 549
 
# Initially check that number must not
# be 0 and power of 2
print(maxZeros(n))
 
# This code is contributed by Mohit Kumar

// C# program to find maximum number of 0's
// in binary representation of a number
using System;
 
class GFG {
 
    // Returns maximum 0's between two immediate
    // 1's in binary representation of number
    static int maxZeros(int n)
    {
        // If there are no 1's or there is only
        // 1, then return -1
        if (n == 0 || (n & (n - 1)) == 0)
            return -1;
 
        // loop to find position of right most 1
        // here sizeof int is 4 that means total 32 bits
        int setBit = 1, prev = 0, i;
        for (i = 1; i <= sizeof(int) * 8; i++) {
            prev++;
 
            // we have found right most 1
            if ((n & setBit) == setBit) {
                setBit = setBit << 1;
                break;
            }
 
            // left shift setBit by 1 to check next bit
            setBit = setBit << 1;
        }
 
        // now loop through for remaining bits and find
        // position of immediate 1 after prev
        int max0 = int.MinValue, cur = prev;
        for (int j = i + 1; j <= sizeof(int) * 8; j++) {
            cur++;
 
            // if current bit is set, then compare
            // difference of cur - prev -1 with
            // previous maximum number of zeros
            if ((n & setBit) == setBit) {
                if (max0 < (cur - prev - 1))
                    max0 = cur - prev - 1;
 
                // update prev
                prev = cur;
            }
            setBit = setBit << 1;
        }
        return max0;
    }
 
    // Driver program to run the case
    static public void Main()
    {
        int n = 549;
 
        // Initially check that number must not
        // be 0 and power of 2
        Console.WriteLine(maxZeros(n));
    }
}
 
// This code is contributed by vt_m.

<script>
 
// JavaScript program to find maximum number of 0's
// in binary representation of a number
 
// Returns maximum 0's between two immediate
// 1's in binary representation of number
function maxZeros(n)
{
     
    // If there are no 1's or there is only
    // 1, then return -1
    if (n == 0 || (n & (n - 1)) == 0)
    {
        return -1;
    }
     
    // int size in java is 4 byte
    let b = 4;
     
    // Loop to find position of right most 1
    // here sizeof int is 4 that means total 32 bits
    let setBit = 1, prev = 0, i;
     
    for(i = 1; i <= b* 8; i++)
    {
        prev++;
 
        // We have found right most 1
        if ((n & setBit) == setBit)
        {
            setBit = setBit << 1;
            break;
        }
 
        // Left shift setBit by 1
        // to check next bit
        setBit = setBit << 1;
    }
 
    // Now loop through for remaining bits
    // and find position of immediate 1 after prev
    let max0 = Number.MIN_VALUE, cur = prev;
    for(let j = i + 1; j <= b * 8; j++)
    {
        cur++;
 
        // If current bit is set, then compare
        // difference of cur - prev -1 with
        // previous maximum number of zeros
        if ((n & setBit) == setBit)
        {
            if (max0 < (cur - prev - 1))
            {
                max0 = cur - prev - 1;
            }
 
            // Update prev
            prev = cur;
        }
        setBit = setBit << 1;
    }
    return max0;
}
 
// Driver Code
let n = 549;
 
// Initially check that number must not
// be 0 and power of 2
document.write(maxZeros(n));
 
// This code is contributed by code_hunt
 
</script>

Producción: 

3

Complejidad de tiempo : O (1), porque toma un tiempo constante independientemente de la entrada n.

Espacio auxiliar : O(1)
Este artículo es una contribución de Shashank Mishra (Gullu) . 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 review-team@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.