Comprobar si un número dado es escaso o no

Se dice que un número es un número disperso si en la representación binaria del número no se establecen dos o más bits consecutivos. Escriba una función para verificar si un número dado es Escaso o no.
Ejemplo : 

Input:  x  = 72
Output: true
Explanation:  Binary representation of 72 is 01001000. 
There are no two consecutive 1's in binary representation

Input:  x  = 12
Output: false
Explanation:  Binary representation of 12 is 1100. 
Third and fourth bits (from end) are set.

Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

Si observamos cuidadosamente, podemos notar que si podemos usar AND bit a bit de la representación binaria del «número dado», su «número desplazado a la derecha» (es decir, la mitad del número dado) para determinar si el número es escaso o no. El resultado del operador AND sería 0 si el número es escaso y distinto de cero si no es escaso.
 

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

// C++ program to check if n is sparse or not
#include<iostream>
using namespace std;
 
// Return true if n is sparse, else false
bool checkSparse(int n)
{
    // n is not sparse if there is set
    // in AND of n and n/2
    if (n & (n>>1))
        return false;
 
    return true;
}
 
// Driver program
int main()
{
    cout << checkSparse(72) << endl;
    cout << checkSparse(12) << endl;
    cout << checkSparse(2) << endl;
    cout << checkSparse(3) << endl;
    return 0;
}

// JAVA Code to Check if a
// given number is sparse or not
import java.util.*;
 
class GFG {
     
    // Return true if n is
    // sparse,else false
    static int checkSparse(int n)
    {
 
        // n is not sparse if there
        // is set in AND of n and n/2
        if ((n & (n>>1)) >=1)
            return 0;
      
        return 1;
    }
     
    // Driver code
    public static void main(String[] args)
    {
        System.out.println(checkSparse(72)) ;
        System.out.println(checkSparse(12)) ;
        System.out.println(checkSparse(2)) ;
        System.out.println(checkSparse(3)) ;
        }
    }
 
//This code is contributed by Arnav Kr. Mandal.

# Python program to check
# if n is sparse or not
 
# Return true if n is
# sparse, else false
def checkSparse(n):
 
    # n is not sparse if there is set
    # in AND of n and n/2
    if (n & (n>>1)):
        return 0
  
    return 1
     
# Driver code
print(checkSparse(72))
print(checkSparse(12))
print(checkSparse(2))
print(checkSparse(30))
 
# This code is contributed
# by Anant Agarwal.

// C# Code to Check if a given
// number is sparse or not
using System;
 
class GFG {
     
    // Return true if n is
    // sparse,else false
    static int checkSparse(int n)
    {
 
        // n is not sparse if there
        // is set in AND of n and n/2
        if ((n & (n >> 1)) >= 1)
            return 0;
     
        return 1;
    }
     
    // Driver code
    public static void Main()
    {
        Console.WriteLine(checkSparse(72));
        Console.WriteLine(checkSparse(12));
        Console.WriteLine(checkSparse(2));
        Console.WriteLine(checkSparse(3));
    }
}
 
// This code is contributed by Sam007.

<?php
// PHP program to check if
// n is sparse or not
// Return true if n is sparse,
// else false
 
function checkSparse($n)
{
    // n is not sparse if
    // there is set in AND
    // of n and n/2
    if ($n & ($n >> 1))
        return 0;
 
    return 1;
}
 
// Driver Code
echo checkSparse(72), "\n";
echo checkSparse(12), "\n";
echo checkSparse(2), "\n";
echo checkSparse(3), "\n";
 
// This code is contributed by Ajit.
?>

<script>
 
    // Javascript program to check if n is sparse or not
     
    // Return true if n is sparse, else false
    function checkSparse(n)
    {
        // n is not sparse if there is set
        // in AND of n and n/2
        if ((n & (n>>1)) > 0)
            return 0;
 
        return 1;
    }
     
    document.write(checkSparse(72) + "</br>");
    document.write(checkSparse(12) + "</br>");
    document.write(checkSparse(2) + "</br>");
    document.write(checkSparse(3) + "</br>");
     
</script>

Producción : 

1
0
1
0

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)

Nota: en lugar del desplazamiento a la derecha, también podríamos haber utilizado el desplazamiento a la izquierda, pero el desplazamiento a la izquierda podría provocar un desbordamiento en algunos casos.
Este artículo es una contribución de Vimal Vestron . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.