Dado un número n, cuente los bits no establecidos después de MSB (bit más significativo).
Ejemplos:
Input : 17 Output : 3 Binary of 17 is 10001 so unset bit is 3 Input : 7 Output : 0
Una solución simple es atravesar todos los bits y contar los bits no configurados.
C++
// C++ program to count unset bits in an integer
#include <iostream>
using namespace std;
int countunsetbits(int n)
{
int count = 0;
// x holds one set digit at a time
// starting from LSB to MSB of n.
for (int x = 1; x <= n; x = x<<1)
if ((x & n) == 0)
count++;
return count;
}
// Driver code
int main()
{
int n = 17;
cout << countunsetbits(n);
return 0;
}
Java
// JAVA Code to Count unset bits in a number
class GFG {
public static int countunsetbits(int n)
{
int count = 0;
// x holds one set digit at a time
// starting from LSB to MSB of n.
for (int x = 1; x <= n; x = x<<1)
if ((x & n) == 0)
count++;
return count;
}
/* Driver program to test above function */
public static void main(String[] args)
{
int n = 17;
System.out.println(countunsetbits(n));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python 3 program to count unset # bits in an integer def countunsetbits(n): count = 0 # x holds one set digit at a time # starting from LSB to MSB of n. x = 1 while(x < n + 1): if ((x & n) == 0): count += 1 x = x << 1 return count # Driver code if __name__ == '__main__': n = 17 print(countunsetbits(n)) # This code is contributed by # Shashank_Sharma
C#
// C# Code to Count unset
// bits in a number
using System;
class GFG {
// Function to count unset bits
public static int countunsetbits(int n)
{
int count = 0;
// x holds one set digit at a time
// starting from LSB to MSB of n.
for (int x = 1; x <= n; x = x << 1)
if ((x & n) == 0)
count++;
return count;
}
// Driver Code
public static void Main()
{
int n = 17;
Console.Write(countunsetbits(n));
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHp program to count
// unset bits in an integer
function countunsetbits($n)
{
$count = 0;
// x holds one set digit
// at a time starting
// from LSB to MSB of n.
for ($x = 1; $x <= $n;
$x = $x << 1)
if (($x & $n) == 0)
$count++;
return $count;
}
// Driver code
$n = 17;
echo countunsetbits($n);
// This code is contributed
// by nitin mittal.
?>
Javascript
<script>
// Javascript program to count unset bits in an integer
function countunsetbits(n)
{
var count = 0;
// x holds one set digit at a time
// starting from LSB to MSB of n.
for (var x = 1; x <= n; x = x<<1)
if ((x & n) == 0)
count++;
return count;
}
// Driver code
var n = 17;
document.write(countunsetbits(n));
</script>
Producción :
3
Por encima de la complejidad de la solución está log(n) .
Complejidad espacial: O(1)
Soluciones eficientes:
La idea es alternar bits en el tiempo O(1). Luego aplique cualquiera de los métodos discutidos en el artículo contar bits establecidos .
En GCC, podemos contar directamente los bits establecidos usando __builtin_popcount(). Primero alterne los bits y luego aplique la función anterior __builtin_popcount().
C++
// An optimized C++ program to count unset bits
// in an integer.
#include <iostream>
using namespace std;
int countUnsetBits(int n)
{
int x = n;
// Make all bits set MSB
// (including MSB)
// This makes sure two bits
// (From MSB and including MSB)
// are set
n |= n >> 1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
// Count set bits in toggled number
return __builtin_popcount(x ^ n);
}
// Driver code
int main()
{
int n = 17;
cout << countUnsetBits(n);
return 0;
}
Java
// An optimized Java program to count unset bits
// in an integer.
class GFG
{
static int countUnsetBits(int n)
{
int x = n;
// Make all bits set MSB
// (including MSB)
// This makes sure two bits
// (From MSB and including MSB)
// are set
n |= n >> 1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
// Count set bits in toggled number
return Integer.bitCount(x^ n);
}
// Driver code
public static void main(String[] args)
{
int n = 17;
System.out.println(countUnsetBits(n));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# An optimized Python program to count # unset bits in an integer. import math def countUnsetBits(n): x = n # Make all bits set MSB(including MSB) # This makes sure two bits(From MSB # and including MSB) are set n |= n >> 1 # This makes sure 4 bits(From MSB and # including MSB) are set n |= n >> 2 n |= n >> 4 n |= n >> 8 n |= n >> 16 t = math.log(x ^ n, 2) # Count set bits in toggled number return math.floor(t) # Driver code n = 17 print(countUnsetBits(n)) # This code is contributed 29AjayKumar
C#
// An optimized C# program to count unset bits
// in an integer.
using System;
class GFG
{
static int countUnsetBits(int n)
{
int x = n;
// Make all bits set MSB
// (including MSB)
// This makes sure two bits
// (From MSB and including MSB)
// are set
n |= n >> 1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
// Count set bits in toggled number
return BitCount(x^ n);
}
static int BitCount(long x)
{
// To store the count
// of set bits
int setBits = 0;
while (x != 0) {
x = x & (x - 1);
setBits++;
}
return setBits;
}
// Driver code
public static void Main(String[] args)
{
int n = 17;
Console.WriteLine(countUnsetBits(n));
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// An optimized PHP program
// to count unset bits in
// an integer.
function countUnsetBits($n)
{
$x = $n;
// Make all bits set
// MSB(including MSB)
// This makes sure two
// bits(From MSB and
// including MSB) are set
$n |= $n >> 1;
// This makes sure 4
// bits(From MSB and
// including MSB) are set
$n |= $n >> 2;
$n |= $n >> 4;
$n |= $n >> 8;
$n |= $n >> 16;
$t = log($x ^ $n,2);
// Count set bits
// in toggled number
return floor($t);
}
// Driver code
$n = 17;
echo countUnsetBits($n);
// This code is contributed
// by ajit
?>
Javascript
<script>
// JavaScript program to count unset bits
// in an integer.
function countUnsetBits(n)
{
let x = n;
// Make all bits set MSB
// (including MSB)
// This makes sure two bits
// (From MSB and including MSB)
// are set
n |= n >> 1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
// Count set bits in toggled number
return BitCount(x^ n);
}
function BitCount(x)
{
// To store the count
// of set bits
let setBits = 0;
while (x != 0) {
x = x & (x - 1);
setBits++;
}
return setBits;
}
// Driver Code
let n = 17;
document.write(countUnsetBits(n));
// This code is contributed by susmitakundugoaldanga.
</script>
Producción :
3
Complejidad de tiempo: O(1)
Espacio auxiliar: O(1)
Este artículo es una contribución de Devanshu Agarwal . 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA