Número de ceros iniciales en la representación binaria de un número dado

Dado un entero n, genera el no. de ceros iniciales en su forma binaria.
Un cero inicial es cualquier dígito 0 que viene antes del primer dígito distinto de cero en la forma binaria de un número. 
Ejemplos: 
 

Input : 16
Output :27
As Binary(16) = (00000000000000000000000000010000)

Input :33
Output :26
As Binary(16)=(00000000000000000000000000100001)

Solución 1: Un enfoque ingenuo es convertir el no. en su forma binaria y luego contar el no. de ceros iniciales. Utiliza costosas operaciones de división. 
 

// C++ program of number of leading zeros in
// binary representation of a given number
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the no. of leading zeros
int countZeros(unsigned int x)
{
    // Keep shifting x by one until leftmost bit
    // does not become 1.
    int total_bits = sizeof(x) * 8;
    int res = 0;
    while ( !(x & (1 << (total_bits - 1))) )
    {
        x = (x << 1);
        res++;
    }
 
    return res;
}
 
// Main function
int main()
{
    int x = 101;
    cout << countZeros(x);
    return 0;
}

// Java program of number of leading zeros in
// binary representation of a given number
class GFG
{
static byte sizeofInt = 8;
 
// Function to count the no. of leading zeros
static int countZeros(int x)
{
    // Keep shifting x by one until leftmost bit
    // does not become 1.
    int total_bits = sizeofInt * 8;
    int res = 0;
    while ((x & (1 << (total_bits - 1))) == 0)
    {
        x = (x << 1);
        res++;
    }
 
    return res;
}
 
// Driver Code
public static void main(String[] args)
{
    int x = 101;
    System.out.println(countZeros(x));
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 program of number of
# leading zeros in binary
# representation of a given number
 
# Function to count the
# no. of leading zeros
def countZeros(x):
     
    # Keep shifting x by one until
    # leftmost bit does not become 1.
    total_bits = 32
    res = 0
    while ((x & (1 << (total_bits - 1))) == 0):
        x = (x << 1)
        res += 1
 
    return res
 
# Driver Code
x = 101
print(countZeros(x))
 
# This code is contributed
# by Mohit Kumar

// C# program of number of leading zeros in
// binary representation of a given number
using System;
 
class GFG
{
static byte sizeofInt = 8;
 
// Function to count the
// no. of leading zeros
static int countZeros(int x)
{
    // Keep shifting x by one until
    // leftmost bit does not become 1.
    int total_bits = sizeofInt * 8;
    int res = 0;
    while ((x & (1 << (total_bits - 1))) == 0)
    {
        x = (x << 1);
        res++;
    }
    return res;
}
 
// Driver Code
public static void Main(String[] args)
{
    int x = 101;
    Console.WriteLine(countZeros(x));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript program of number of leading zeros in
// binary representation of a given number
 
let sizeofInt = 8;
 
// Function to count the no. of leading zeros
function countZeros(x)
{
    // Keep shifting x by one until leftmost bit
    // does not become 1.
    let total_bits = sizeofInt * 8;
    let res = 0;
    while ((x & (1 << (total_bits - 1))) == 0)
    {
        x = (x << 1);
        res++;
    }
  
    return res;
}
 
// Driver Code
let x = 101;
document.write(countZeros(x));
     
 
// This code is contributed by unknown2108
 
</script>

25

Solución 2: un enfoque eficiente es utilizar la operación de desplazamiento a la derecha bit a bit para lograr lo mismo. Los pasos del algoritmo son: 
Sea x nuestro número. después
 

    unsigned y;
    int n = 32;
    y = x >>16; if (y != 0) {n = n -16; x = y;}
    y = x >> 8; if (y != 0) {n = n - 8; x = y;}
    y = x >> 4; if (y != 0) {n = n - 4; x = y;}
    y = x >> 2; if (y != 0) {n = n - 2; x = y;}
    y = x >> 1; if (y != 0) return n - 2;
    return n - x;

El enfoque anterior se ejecuta en solo 12 a 20 instrucciones.
 

// C++ program of number of leading zeros in
// binary representation of a given number
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the no. of leading zeros
int countZeros(int x)
{
    unsigned y;
    int n = 32;
    y = x >> 16;
    if (y != 0) {
        n = n - 16;
        x = y;
    }
    y = x >> 8;
    if (y != 0) {
        n = n - 8;
        x = y;
    }
    y = x >> 4;
    if (y != 0) {
        n = n - 4;
        x = y;
    }
    y = x >> 2;
    if (y != 0) {
        n = n - 2;
        x = y;
    }
    y = x >> 1;
    if (y != 0)
        return n - 2;
    return n - x;
}
 
// Main function
int main()
{
    int x = 101;
    cout << countZeros(x);
    return 0;
}

// Java program of number of leading zeros in
// binary representation of a given number
import java.io.*;
 
class GFG {
    // Function to count the no. of leading zeros
static int countZeros(int x)
{
    int y;
    int n = 32;
    y = x >> 16;
    if (y != 0) {
        n = n - 16;
        x = y;
    }
    y = x >> 8;
    if (y != 0) {
        n = n - 8;
        x = y;
    }
    y = x >> 4;
    if (y != 0) {
        n = n - 4;
        x = y;
    }
    y = x >> 2;
    if (y != 0) {
        n = n - 2;
        x = y;
    }
    y = x >> 1;
    if (y != 0)
        return n - 2;
    return n - x;
}
 
// Main function
    public static void main (String[] args) {
    int x = 101;
    System.out.println (countZeros(x));
    }
//This code is contributed by @Tushil.   
}

# Python3 program of number of leading zeros in
# binary representation of a given number
 
 
# Function to count the no. of leading zeros
def countZeros(x):
    n = 32;
    y = x >> 16;
    if (y != 0):
        n = n - 16;
        x = y;
 
    y = x >> 8;
    if (y != 0):
        n = n - 8;
        x = y;
 
    y = x >> 4;
    if (y != 0):
        n = n - 4;
        x = y;
 
    y = x >> 2;
    if (y != 0):
        n = n - 2;
        x = y;
 
    y = x >> 1;
    if (y != 0):
        return n - 2;
    return n - x;
 
 
# Main function
def main():
    x = 101;
    print(countZeros(x))
 
 
if __name__ == '__main__':
    main()

// C# program of number of leading zeros in
// binary representation of a given number
using System;
 
class GFG
{
// Function to count the no. of
// leading zeros
static int countZeros(int x)
{
    int y;
    int n = 32;
    y = x >> 16;
     
    if (y != 0)
    {
        n = n - 16;
        x = y;
    }
    y = x >> 8;
     
    if (y != 0)
    {
        n = n - 8;
        x = y;
    }
    y = x >> 4;
     
    if (y != 0)
    {
        n = n - 4;
        x = y;
    }
    y = x >> 2;
     
    if (y != 0)
    {
        n = n - 2;
        x = y;
    }
    y = x >> 1;
     
    if (y != 0)
        return n - 2;
    return n - x;
}
 
// Driver Code
static public void Main ()
{
    int x = 101;
    Console.WriteLine(countZeros(x));
}
}
 
// This code is contributed by ajit

<?php
// PHP program of number of leading zeros in
// binary representation of a given number
 
// Function to count the no. of leading zeros
function countZeros($x)
{
    $y;
    $n = 32;
    $y = $x >> 16;
    if ($y != 0)
    {
        $n = $n - 16;
        $x = $y;
    }
    $y = $x >> 8;
    if ($y != 0)
    {
        $n = $n - 8;
        $x = $y;
    }
    $y = $x >> 4;
    if ($y != 0)
    {
        $n = $n - 4;
        $x = $y;
    }
    $y = $x >> 2;
    if ($y != 0) {
        $n = $n - 2;
        $x = $y;
    }
    $y = $x >> 1;
    if ($y != 0)
        return $n - 2;
    return $n - $x;
}
 
// Driver Code
$x = 101;
echo countZeros($x);
 
// This code is contributed
// by Akanksha Rai

<script>
 
// JavaScript program of number of leading zeros in
// binary representation of a given number
 
 // Function to count the no. of leading zeros
function countZeros(x)
{
    let y;
    let n = 32;
    y = x >> 16;
    if (y != 0) {
        n = n - 16;
        x = y;
    }
    y = x >> 8;
    if (y != 0) {
        n = n - 8;
        x = y;
    }
    y = x >> 4;
    if (y != 0) {
        n = n - 4;
        x = y;
    }
    y = x >> 2;
    if (y != 0) {
        n = n - 2;
        x = y;
    }
    y = x >> 1;
    if (y != 0)
        return n - 2;
    return n - x;
}
 
// Main function
let x = 101;
document.write(countZeros(x));
 
 
// This code is contributed by patel2127
 
</script>

25

Solución 3: Usando el GCC __builtin_clz(x): Esta función se usa para contar los ceros iniciales del número entero donde clz significa contar los ceros iniciales . Cuenta una cantidad de ceros antes de la primera aparición de uno (bit establecido).

#include <stdio.h>
int main()
{
    int n = 19; //00000000 00000000 00000000 010011
    printf(
        "Count of leading zeros before first occurrence: %d",
        __builtin_clz(n));
    return 0;
}

Count of leading zeros before first occurrence: 27

Salida: recuento de ceros a la izquierda antes de la primera aparición: 27

Solución 4: Uso de funciones predefinidas

En Java, el método numberOfLeadingZeros() de la clase Integer y Long se usa para contar los ceros iniciales del entero.

// Java Program that counts the number of leading zeroes
 
class GFG {
    public static void main(String[] args)
    {
        int n = 19; // 00000000 00000000 00000000 010011
        System.out.println(
            "Count of leading zeros before first occurrence: "
            + Integer.numberOfLeadingZeros(n));
    }
}

Count of leading zeros before first occurrence: 27

Complejidad de tiempo: La complejidad de tiempo de este enfoque es O(1) 
Complejidad de espacio: La complejidad de espacio de este enfoque es O(1)