Dado un número x, encuentre el siguiente número con el mismo número de 1 bits en su representación binaria.
Por ejemplo, considere x = 12, cuya representación binaria es 1100 (excluyendo los ceros iniciales en una máquina de 32 bits). Contiene dos bits 1 lógicos. El siguiente número más alto con dos bits lógicos 1 es 17 (10001 2 ).
Algoritmo:
cuando observamos la secuencia binaria de 0 a 2 n – 1 (n es el número de bits), la mayoría de los bits de la derecha (menos significativos) varían rápidamente que la mayoría de los bits de la izquierda. La idea es encontrar la string más a la derecha de 1 en x, y cambiar el patrón al extremo derecho, excepto el bit más a la izquierda en el patrón. Desplace el bit más a la izquierda en el patrón (bit omitido) a la parte izquierda de x una posición. Un ejemplo lo hace más claro,
x = 156
10
x = 10011100
(2)
10011100 00011100 - right most string of 1's in x 00000011 - right shifted pattern except left most bit ------> [A] 00010000 - isolated left most bit of right most 1's pattern 00100000 - shiftleft-ed the isolated bit by one position ------> [B] 10000000 - left part of x, excluding right most 1's pattern ------> [C] 10100000 - add B and C (OR operation) ------> [D] 10100011 - add A and D which is required number 163
(10)
Después de practicar con algunos ejemplos, es fácil de entender. Use el programa dado a continuación para generar más conjuntos.
Diseño del programa:
debemos tener en cuenta algunos hechos de los números binarios. La expresión x & -x aislará el bit establecido más a la derecha en x (asegurando que x usará la forma de complemento a 2 para números negativos). Si sumamos el resultado a x, se restablecerá la string de 1 más a la derecha en x, y se establecerá el ‘0’ inmediato a la izquierda de este patrón de 1, que es la parte [B] de la explicación anterior. Por ejemplo, si x = 156, x & -x dará como resultado 00000100, sumando este resultado a x se obtiene 10100000 (ver parte D). Nos fuimos con la parte derecha de desplazamiento del patrón de 1 (parte A de la explicación anterior).
Hay diferentes formas de lograr la parte A. El desplazamiento a la derecha es esencialmente una operación de división. ¿Cuál debe ser nuestro divisor? Claramente, debería ser un múltiplo de 2 (evita un error de 0,5 en el desplazamiento a la derecha) y debería desplazar el patrón de 1 más a la derecha al extremo derecho. La expresión (x & -x) servirá como divisor. Una operación EX-OR entre el número X y la expresión que se usa para restablecer la mayoría de los bits a la derecha, aislará el patrón de los 1 más a la derecha.
Un factor de corrección: tenga
en cuenta que estamos agregando el bit establecido más a la derecha al patrón de bits. La operación de suma provoca un cambio en las posiciones de los bits. El peso del sistema binario es 2, un cambio provoca un aumento por un factor de 2. Dado que el número aumentado ( rightOnesPatternen el código) se usa dos veces, el error se propaga dos veces. El error necesita ser corregido. Un desplazamiento a la derecha de 2 posiciones corregirá el resultado. El nombre
popular de este programa es el mismo número de bits .
C++
#include<iostream>
using namespace std;
typedef unsigned int uint_t;
// this function returns next higher number with same number of set bits as x.
uint_t snoob(uint_t x)
{
uint_t rightOne;
uint_t nextHigherOneBit;
uint_t rightOnesPattern;
uint_t next = 0;
if(x)
{
// right most set bit
rightOne = x & -(signed)x;
// reset the pattern and set next higher bit
// left part of x will be here
nextHigherOneBit = x + rightOne;
// nextHigherOneBit is now part [D] of the above explanation.
// isolate the pattern
rightOnesPattern = x ^ nextHigherOneBit;
// right adjust pattern
rightOnesPattern = (rightOnesPattern)/rightOne;
// correction factor
rightOnesPattern >>= 2;
// rightOnesPattern is now part [A] of the above explanation.
// integrate new pattern (Add [D] and [A])
next = nextHigherOneBit | rightOnesPattern;
}
return next;
}
int main()
{
int x = 156;
cout<<"Next higher number with same number of set bits is "<<snoob(x);
getchar();
return 0;
}
Java
// Java Implementation on above approach
class GFG
{
// this function returns next higher
// number with same number of set bits as x.
static int snoob(int x)
{
int rightOne, nextHigherOneBit, rightOnesPattern, next = 0;
if(x > 0)
{
// right most set bit
rightOne = x & -x;
// reset the pattern and set next higher bit
// left part of x will be here
nextHigherOneBit = x + rightOne;
// nextHigherOneBit is now part [D] of the above explanation.
// isolate the pattern
rightOnesPattern = x ^ nextHigherOneBit;
// right adjust pattern
rightOnesPattern = (rightOnesPattern)/rightOne;
// correction factor
rightOnesPattern >>= 2;
// rightOnesPattern is now part [A] of the above explanation.
// integrate new pattern (Add [D] and [A])
next = nextHigherOneBit | rightOnesPattern;
}
return next;
}
// Driver code
public static void main (String[] args)
{
int x = 156;
System.out.println("Next higher number with same" +
"number of set bits is "+snoob(x));
}
}
// This code is contributed by mits
Python 3
# This function returns next
# higher number with same
# number of set bits as x.
def snoob(x):
next = 0
if(x):
# right most set bit
rightOne = x & -(x)
# reset the pattern and
# set next higher bit
# left part of x will
# be here
nextHigherOneBit = x + int(rightOne)
# nextHigherOneBit is
# now part [D] of the
# above explanation.
# isolate the pattern
rightOnesPattern = x ^ int(nextHigherOneBit)
# right adjust pattern
rightOnesPattern = (int(rightOnesPattern) /
int(rightOne))
# correction factor
rightOnesPattern = int(rightOnesPattern) >> 2
# rightOnesPattern is now part
# [A] of the above explanation.
# integrate new pattern
# (Add [D] and [A])
next = nextHigherOneBit | rightOnesPattern
return next
# Driver Code
x = 156
print("Next higher number with " +
"same number of set bits is",
snoob(x))
# This code is contributed by Smita
C#
// C# Implementation on above approach
using System;
class GFG
{
// this function returns next higher
// number with same number of set bits as x.
static int snoob(int x)
{
int rightOne, nextHigherOneBit,
rightOnesPattern, next = 0;
if(x > 0)
{
// right most set bit
rightOne = x & -x;
// reset the pattern and set next higher bit
// left part of x will be here
nextHigherOneBit = x + rightOne;
// nextHigherOneBit is now part [D]
// of the above explanation.
// isolate the pattern
rightOnesPattern = x ^ nextHigherOneBit;
// right adjust pattern
rightOnesPattern = (rightOnesPattern) / rightOne;
// correction factor
rightOnesPattern >>= 2;
// rightOnesPattern is now part [A]
// of the above explanation.
// integrate new pattern (Add [D] and [A])
next = nextHigherOneBit | rightOnesPattern;
}
return next;
}
// Driver code
static void Main()
{
int x = 156;
Console.WriteLine("Next higher number with same" +
"number of set bits is " + snoob(x));
}
}
// This code is contributed by mits
PHP
<?php
// This function returns next higher number
// with same number of set bits as x.
function snoob($x)
{
$next = 0;
if($x)
{
// right most set bit
$rightOne = $x & - $x;
// reset the pattern and set next higher
// bit left part of x will be here
$nextHigherOneBit = $x + $rightOne;
// nextHigherOneBit is now part [D] of
// the above explanation.
// isolate the pattern
$rightOnesPattern = $x ^ $nextHigherOneBit;
// right adjust pattern
$rightOnesPattern = intval(($rightOnesPattern) /
$rightOne);
// correction factor
$rightOnesPattern >>= 2;
// rightOnesPattern is now part [A]
// of the above explanation.
// integrate new pattern (Add [D] and [A])
$next = $nextHigherOneBit | $rightOnesPattern;
}
return $next;
}
// Driver Code
$x = 156;
echo "Next higher number with same " .
"number of set bits is " . snoob($x);
// This code is contributed by ita_c
?>
Javascript
<script>
// this function returns next higher
// number with same number of set bits as x.
function snoob(x)
{
let rightOne, nextHigherOneBit, rightOnesPattern, next = 0;
if(x > 0)
{
// right most set bit
rightOne = x & -x;
// reset the pattern and set next higher bit
// left part of x will be here
nextHigherOneBit = x + rightOne;
// nextHigherOneBit is now part [D] of the above explanation.
// isolate the pattern
rightOnesPattern = x ^ nextHigherOneBit;
// right adjust pattern
rightOnesPattern = (rightOnesPattern)/rightOne;
// correction factor
rightOnesPattern >>= 2;
// rightOnesPattern is now part [A] of the above explanation.
// integrate new pattern (Add [D] and [A])
next = nextHigherOneBit | rightOnesPattern;
}
return next;
}
// Driver code
let x = 156;
document.write("Next higher number with same " +
"number of set bits is "+snoob(x));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Next higher number with same number of set bits is 163
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Uso: Búsqueda/Generación de subconjuntos.
Variaciones:
- ¿Escribir un programa para encontrar un número inmediatamente menor que el dado, con el mismo número de bits lógicos 1? (Bastante simple)
- ¿Cómo contar o generar los subconjuntos disponibles en el conjunto dado?
Referencias:
- Una buena presentación aquí .
- Hackers Delight de Warren (Un excelente y breve libro sobre varios algoritmos mágicos de bits, imprescindible para los entusiastas)
- Manual de referencia de CA por Harbison y Steele (un buen libro sobre C estándar, puede acceder a la parte del código de esta publicación aquí ).
– Venki . 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