Dado un entero positivo n, imprima el siguiente número más pequeño y el anterior más grande que tenga el mismo número de 1 bit en su representación binaria.
Ejemplos:
Input : n = 5
Output : Closest Greater = 6
Closest Smaller = 3
Note that 5, 6 and 3 have same number of
set bits.
Input : n = 11
Output : Closest Greater = 13
Closest Smaller = 7
El enfoque
de la fuerza bruta Un enfoque sencillo es la fuerza bruta simple: cuente el número de 1 en n y luego incremente (o disminuya) hasta encontrar un número con el mismo número de 1.
Enfoques óptimos
Comencemos con el código para getNext y luego pasemos a getPrev.
Enfoque de manipulación de bits para obtener el siguiente número
Si pensamos en cuál debería ser el siguiente número, podemos observar lo siguiente. Dado el número 13948, la representación binaria se ve así:
1 1 0 1 1 0 0 1 1 1 1 1 0 0 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Queremos hacer este número más grande (pero no demasiado grande). También tenemos que mantener el mismo número de unos.
Observación: dado un número n y ubicaciones de dos bits i y j, supongamos que cambiamos el bit i de 1 a 0 y el bit j de 0 a 1. Si i > j, entonces n habrá disminuido. Si i < j, entonces n habrá aumentado.
Sabemos lo siguiente:
- Si cambiamos cero a uno, debemos cambiar uno a cero.
- El número (después de dos vueltas) será mayor si y solo si el bit de cero a uno estaba a la izquierda del bit de uno a cero.
- Queremos hacer el número más grande, pero no innecesariamente más grande. Por lo tanto, necesitamos voltear el cero más a la derecha, que tiene uno a la derecha.
Para poner esto de una manera diferente, estamos volteando el cero no final más a la derecha. Es decir, usando el ejemplo anterior, los ceros finales están en el lugar 0 y 1. El cero no final más a la derecha está en 7. Llamemos a esta posición p.
p ==> Position of rightmost non-trailing 0.
Paso 1: voltea el cero no final más a la derecha
1 1 0 1 1 0 1 1 1 1 1 1 0 0 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Con este cambio, hemos aumentado el número de 1s de n. Podemos reducir el número reorganizando todos los bits a la derecha del bit p de modo que los 0 estén a la izquierda y los 1 a la derecha. Mientras hacemos esto, queremos reemplazar uno de los 1 con un 0.
Una forma relativamente fácil de hacer esto es contar cuántos están a la derecha de p, borrar todos los bits desde 0 hasta p, y luego sumarlos. de vuelta a los c1-1. Sea c1 el número de unos a la derecha de p y c0 el número de ceros a la derecha de p.
Analicemos esto con un ejemplo.
c1 ==> Number of ones to the right of p c0 ==> Number of zeros to the right of p. p = c0 + c1
Paso 2: borre los bits a la derecha de p. Desde antes, c0 = 2. c1 = 5. p = 7.
1 1 0 1 1 0 1 0 0 0 0 0 0 0 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Para borrar estos bits, necesitamos crear una máscara que sea una secuencia de unos, seguida de p ceros. Podemos hacer esto de la siguiente manera:
// all zeros except for a 1 at position p. a = 1 << p; // all zeros, followed by p ones. b = a - 1; // all ones, followed by p zeros. mask = ~b; // clears rightmost p bits. n = n & mask; Or, more concisely, we do: n &= ~((1 << p) - 1).
Paso 3: Agrega un c1 – 1 uno.
1 1 0 1 1 0 1 0 0 0 1 1 1 1 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Para insertar c1 – 1 uno a la derecha, hacemos lo siguiente:
// 0s with a 1 at position c1– 1 a = 1 << (c1 - 1); // 0s with 1s at positions 0 through c1-1 b = a - 1; // inserts 1s at positions 0 through c1-1 n = n | b; Or, more concisely: n | = (1 << (c1 - 1)) - 1;
Ahora hemos llegado al número más pequeño, mayor que n con el mismo número de unos. La implementación del código para getNext se encuentra a continuación.
C++
// C++ implementation of getNext with
// same number of bits 1's is below
#include <bits/stdc++.h>
using namespace std;
// Main Function to find next smallest
// number bigger than n
int getNext(int n)
{
/* Compute c0 and c1 */
int c = n;
int c0 = 0;
int c1 = 0;
while (((c & 1) == 0) && (c != 0))
{
c0 ++;
c >>= 1;
}
while ((c & 1)==1)
{
c1++;
c >>= 1;
}
// If there is no bigger number with the
// same no. of 1's
if (c0 +c1 == 31 || c0 +c1== 0)
return -1;
// position of rightmost non-trailing zero
int p = c0 + c1;
// Flip rightmost non-trailing zero
n |= (1 << p);
// Clear all bits to the right of p
n &= ~((1 << p) - 1);
// Insert (c1-1) ones on the right.
n |= (1 << (c1 - 1)) - 1;
return n;
}
// Driver Code
int main()
{
int n = 5; // input 1
cout << getNext(n) << endl;
n = 8; // input 2
cout << getNext(n);
return 0;
}
Java
// Java implementation of
// getNext with same number
// of bits 1's is below
import java.io.*;
class GFG
{
// Main Function to find next
// smallest number bigger than n
static int getNext(int n)
{
/* Compute c0 and c1 */
int c = n;
int c0 = 0;
int c1 = 0;
while (((c & 1) == 0) &&
(c != 0))
{
c0++;
c >>= 1;
}
while ((c & 1) == 1)
{
c1++;
c >>= 1;
}
// If there is no bigger number
// with the same no. of 1's
if (c0 + c1 == 31 ||
c0 + c1 == 0)
return -1;
// position of rightmost
// non-trailing zero
int p = c0 + c1;
// Flip rightmost
// non-trailing zero
n |= (1 << p);
// Clear all bits
// to the right of p
n &= ~((1 << p) - 1);
// Insert (c1-1) ones
// on the right.
n |= (1 << (c1 - 1)) - 1;
return n;
}
// Driver Code
public static void main (String[] args)
{
int n = 5; // input 1
System.out.println(getNext(n));
n = 8; // input 2
System.out.println(getNext(n));
}
}
// This code is contributed by aj_36
Python3
# Python 3 implementation of getNext with # same number of bits 1's is below # Main Function to find next smallest # number bigger than n def getNext(n): # Compute c0 and c1 c = n c0 = 0 c1 = 0 while (((c & 1) == 0) and (c != 0)): c0 += 1 c >>= 1 while ((c & 1) == 1): c1 += 1 c >>= 1 # If there is no bigger number with # the same no. of 1's if (c0 + c1 == 31 or c0 + c1== 0): return -1 # position of rightmost non-trailing zero p = c0 + c1 # Flip rightmost non-trailing zero n |= (1 << p) # Clear all bits to the right of p n &= ~((1 << p) - 1) # Insert (c1-1) ones on the right. n |= (1 << (c1 - 1)) - 1 return n # Driver Code if __name__ == "__main__": n = 5 # input 1 print(getNext(n)) n = 8 # input 2 print(getNext(n)) # This code is contributed by ita_c
C#
// C# implementation of getNext with
// same number of bits 1's is below
using System;
class GFG {
// Main Function to find next
// smallest number bigger than n
static int getNext(int n)
{
/* Compute c0 and c1 */
int c = n;
int c0 = 0;
int c1 = 0;
while (((c & 1) == 0) && (c != 0))
{
c0++;
c >>= 1;
}
while ((c & 1) == 1)
{
c1++;
c >>= 1;
}
// If there is no bigger number
// with the same no. of 1's
if (c0 + c1 == 31 || c0 + c1== 0)
return -1;
// position of rightmost
// non-trailing zero
int p = c0 + c1;
// Flip rightmost non-trailing
// zero
n |= (1 << p);
// Clear all bits to the right
// of p
n &= ~((1 << p) - 1);
// Insert (c1-1) ones on the
// right.
n |= (1 << (c1 - 1)) - 1;
return n;
}
// Driver Code
static void Main()
{
int n = 5; // input 1
Console.WriteLine(getNext(n));
n = 8; // input 2
Console.Write(getNext(n));
}
}
// This code is contributed by Anuj_67
PHP
<?php
// PHP implementation of getNext with
// same number of bits 1's is below
// Function to find next smallest
// number bigger than n
function getNext($n)
{
// Compute c0 and c1
$c = $n;
$c0 = 0;
$c1 = 0;
while ((($c & 1) == 0) &&
($c != 0))
{
$c0 ++;
$c >>= 1;
}
while (($c & 1) == 1)
{
$c1++;
$c >>= 1;
}
// If there is no bigger
// number with the
// same no. of 1's
if ($c0 + $c1 == 31 ||
$c0 + $c1== 0)
return -1;
// position of rightmost
// non-trailing zero
$p = $c0 + $c1;
// Flip rightmost non -
// trailing zero
$n |= (1 << $p);
// Clear all bits to
// the right of p
$n &= ~((1 << $p) - 1);
// Insert (c1-1) ones
// on the right.
$n |= (1 << ($c1 - 1)) - 1;
return $n;
}
// Driver Code
// input 1
$n = 5;
echo getNext($n),"\n";
// input 2
$n = 8;
echo getNext($n);
// This code is contributed by ajit
?>
Javascript
<script>
function getNext(n)
{
/* Compute c0 and c1 */
let c = n;
let c0 = 0;
let c1 = 0;
while (((c & 1) == 0) &&
(c != 0))
{
c0++;
c >>= 1;
}
while ((c & 1) == 1)
{
c1++;
c >>= 1;
}
// If there is no bigger number
// with the same no. of 1's
if (c0 + c1 == 31 ||
c0 + c1 == 0)
return -1;
// position of rightmost
// non-trailing zero
let p = c0 + c1;
// Flip rightmost
// non-trailing zero
n |= (1 << p);
// Clear all bits
// to the right of p
n &= ~((1 << p) - 1);
// Insert (c1-1) ones
// on the right.
n |= (1 << (c1 - 1)) - 1;
return n;
}
let n = 5; // input 1
document.write(getNext(n)+"<br>");
n = 8; // input 2
document.write(getNext(n));
// This code is contributed by rag2127
</script>
Producción:
6 16
Enfoque de manipulación de bits óptimo para obtener el número anterior
Para implementar getPrev, seguimos un enfoque muy similar.
- Calcule c0 y c1. Tenga en cuenta que c1 es el número de unos finales y c0 es el tamaño del bloque de ceros inmediatamente a la izquierda de los finales.
- Voltee el uno que no se arrastra más a la derecha a cero. Esta estará en la posición p = c1 + c0.
- Borra todos los bits a la derecha del bit p.
- Inserte c1 + 1 unos inmediatamente a la derecha de la posición p.
Tenga en cuenta que el Paso 2 establece los bits p en cero y el Paso 3 establece los bits 0 a p-1 en cero. Podemos fusionar estos pasos.
Analicemos esto con un ejemplo.
c1 ==> number of trailing ones
c0 ==> size of the block of zeros immediately
to the left of the trailing ones.
p = c1 + c0
Paso 1: Número inicial: p = 7. c1 = 2. c0 = 5.
1 0 0 1 1 1 1 0 0 0 0 0 1 1 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Pasos 2 y 3: Borrar bits 0 a p.
1 0 0 1 1 1 0 0 0 0 0 0 0 0 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Podemos hacer esto de la siguiente manera:
// Sequence of 1s int a = ~0; // Sequence of 1s followed by p + 1 zeros. int b = a << (p + 1); // Clears bits 0 through p. n & = b;
Paso 4: Inserte c1 + 1 unos inmediatamente a la derecha de la posición p.
1 0 0 1 1 1 0 1 1 1 0 0 0 0 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Tenga en cuenta que dado que p = c1 + c0, entonces (c1 + 1) unos serán seguidos por (c0 – 1) ceros.
Podemos hacer esto de la siguiente manera:
// 0s with 1 at position (c1 + 1) int a = 1 << (c1 + 1); // 0s followed by c1 + 1 ones int b = a - 1; // c1 + 1 ones followed by c0 - 1 zeros. int c = b << (c0 - 1); n |= c;
El código para implementar esto se encuentra a continuación.
C++
// C++ Implementation of getPrev in
// Same number of bits 1's is below
#include <bits/stdc++.h>
using namespace std;
// Main Function to find next Bigger number
// Smaller than n
int getPrev(int n)
{
/* Compute c0 and c1 and store N*/
int temp = n;
int c0 = 0;
int c1= 0;
while ((temp & 1) == 1)
{
c1++;
temp = temp >> 1;
}
if (temp == 0)
return -1;
while (((temp & 1) == 0) && (temp!= 0))
{
c0++;
temp = temp >> 1;
}
// position of rightmost non-trailing one.
int p = c0 + c1;
// clears from bit p onwards
n = n & ((~0) << (p + 1));
// Sequence of (c1+1) ones
int mask = (1 << (c1 + 1)) - 1;
n = n | mask << (c0 - 1);
return n;
}
// Driver Code
int main()
{
int n = 6; // input 1
cout << getPrev(n);
n = 16; // input 2
cout << endl;
cout << getPrev(n);
return 0;
}
Java
// Java Implementation of
// getPrev in Same number
// of bits 1's is below
import java.io.*;
class GFG
{
// Main Function to find
// next Bigger number
// Smaller than n
static int getPrev(int n)
{
// Compute c0 and
// c1 and store N
int temp = n;
int c0 = 0;
int c1= 0;
while((temp & 1) == 1)
{
c1++;
temp = temp >> 1;
}
if(temp == 0)
return -1;
while(((temp & 1) == 0) &&
(temp!= 0))
{
c0++;
temp = temp >> 1;
}
// position of rightmost
// non-trailing one.
int p = c0 + c1;
// clears from bit p onwards
n = n & ((~0) << (p + 1));
// Sequence of (c1+1) ones
int mask = (1 << (c1 + 1)) - 1;
n = n | mask << (c0 - 1);
return n;
}
// Driver Code
public static void main(String[] args)
{
int n = 6; // input 1
System.out.println(getPrev(n));
n = 16; // input 2
System.out.println(getPrev(n));
}
}
// This code is contributed by aj_36
Python3
# Python3 Implementation of getPrev in # Same number of bits 1's is below # Main Function to find next Bigger number # Smaller than n def getPrev(n): # Compute c0 and c1 and store N temp = n c0 = 0 c1 = 0 while ((temp & 1) == 1): c1 = c1+1 temp = temp >> 1 if (temp == 0): return -1 while (((temp & 1) == 0) and (temp != 0)): c0 = c0+1 temp = temp >> 1 # position of rightmost non-trailing one. p = c0 + c1 # clears from bit p onwards n = n & ((~0) << (p + 1)) # Sequence of (c1+1) ones mask = (1 << (c1 + 1)) - 1 n = n | mask << (c0 - 1) return n if __name__ == '__main__': n = 6 # input 1 print(getPrev(n)) n = 16 # input 2 print(getPrev(n)) # This code is contributed by nirajgusain5
C#
// C# Implementation of
// getPrev in Same number
// of bits 1's is below
using System;
class GFG
{
// Main Function to find
// next Bigger number
// Smaller than n
static int getPrev(int n)
{
// Compute c0 and
// c1 and store N
int temp = n;
int c0 = 0;
int c1 = 0;
while((temp & 1) == 1)
{
c1++;
temp = temp >> 1;
}
if(temp == 0)
return -1;
while(((temp & 1) == 0) &&
(temp != 0))
{
c0++;
temp = temp >> 1;
}
// position of rightmost
// non-trailing one.
int p = c0 + c1;
// clears from
// bit p onwards
n = n & ((~0) << (p + 1));
// Sequence of
// (c1+1) ones
int mask = (1 << (c1 + 1)) - 1;
n = n | mask << (c0 - 1);
return n;
}
// Driver Code
static public void Main ()
{
int n = 6; // input 1
Console.WriteLine(getPrev(n));
n = 16; // input 2
Console.WriteLine(getPrev(n));
}
}
// This code is contributed by ajit
PHP
<?php
// PHP Implementation of getPrev in
// Same number of bits 1's is below
// Main Function to find next Bigger
// number Smaller than n
function getPrev($n)
{
// Compute c0 and
// c1 and store N
$temp = $n;
$c0 = 0;
$c1= 0;
while (($temp & 1) == 1)
{
$c1++;
$temp = $temp >> 1;
}
if ($temp == 0)
return -1;
while ((($temp & 1) == 0) &&
($temp!= 0))
{
$c0++;
$temp = $temp >> 1;
}
// position of rightmost
// non-trailing one.
$p = $c0 + $c1;
// clears from bit p onwards
$n = $n & ((~0) << ($p + 1));
// Sequence of (c1 + 1) ones
$mask = (1 << ($c1 + 1)) - 1;
$n = $n | $mask << ($c0 - 1);
return $n;
}
// Driver Code
// input 1
$n = 6;
echo getPrev($n);
// input 2
$n = 16;
echo " \n" ;
echo getPrev($n);
// This code is contributed by Ajit
?>
Javascript
<script>
// Javascript Implementation of
// getPrev in Same number
// of bits 1's is below
// Main Function to find
// next Bigger number
// Smaller than n
function getPrev(n)
{
// Compute c0 and
// c1 and store N
let temp = n;
let c0 = 0;
let c1= 0;
while((temp & 1) == 1)
{
c1++;
temp = temp >> 1;
}
if(temp == 0)
return -1;
while(((temp & 1) == 0) &&
(temp!= 0))
{
c0++;
temp = temp >> 1;
}
// position of rightmost
// non-trailing one.
let p = c0 + c1;
// clears from bit p onwards
n = n & ((~0) << (p + 1));
// Sequence of (c1+1) ones
let mask = (1 << (c1 + 1)) - 1;
n = n | mask << (c0 - 1);
return n;
}
// Driver Code
let n = 6; // input 1
document.write(getPrev(n)+"<br>");
n = 16; // input 2
document.write(getPrev(n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
5 8
Enfoque aritmético para obtener el siguiente número
Si c0 es el número de ceros finales, c1 es el tamaño del bloque inmediatamente siguiente y p = c0 + c1, podemos formar nuestra solución anterior de la siguiente manera:
- Establezca el p-ésimo bit en 1.
- Establezca todos los bits que siguen a p en 0.
- Configure los bits de 0 a c1 – 2 a 1. Esto será c1 – 1 bits totales.
Una forma rápida de realizar los pasos 1 y 2 es establecer los ceros finales en 1 (lo que nos da p unos finales) y luego agregar 1. Agregar uno invertirá todos los unos finales, por lo que terminamos con un 1 en el bit p seguido de p ceros. Podemos hacer esto aritméticamente.
// Establece 0s finales a 1, dándonos p 1s finales.
n += 2 c0 – 1 ;
// Cambia el primer p ls a 0s y pone un 1 en el bit p.
n+= 1;
Ahora, para realizar el Paso 3 aritméticamente, simplemente hacemos:
// Establece los ceros finales c1 – 1 en unos.
n += 2 c1 – 1 – 1;
Esta matemática se reduce a:
siguiente = n + (2 c0 – 1) + 1 + (2 c1 – 1 – 1)
= n + 2 c0 + 2 c1 – 1– 1
La mejor parte es que usando un poco de manipulación, es fácil de codificar.
C++
// C++ Implementation of getNext with
// Same number of bits 1's is below
#include <bits/stdc++.h>
using namespace std;
// Main Function to find next smallest number
// bigger than n
int getNext(int n)
{
/* Compute c0 and c1 */
int c = n;
int c0 = 0;
int c1 = 0;
while (((c & 1) == 0) && (c != 0))
{
c0 ++;
c >>= 1;
}
while ((c & 1)==1)
{
c1++;
c >>= 1;
}
// If there is no bigger number with the
// same no. of 1's
if (c0 +c1 == 31 || c0 +c1== 0)
return -1;
return n + (1 << c0) + (1 << (c1 - 1)) - 1;
}
// Driver Code
int main()
{
int n = 5; // input 1
cout << getNext(n);
n = 8; // input 2
cout << endl;
cout << getNext(n);
return 0;
}
Java
// Java Implementation of getNext with
// Same number of bits 1's is below
import java.io.*;
class GFG
{
// Function to find next smallest
// number bigger than n
static int getNext(int n)
{
/* Compute c0
and c1 */
int c = n;
int c0 = 0;
int c1 = 0;
while (((c & 1) == 0) && (c != 0))
{
c0 ++;
c >>= 1;
}
while ((c & 1) == 1)
{
c1++;
c >>= 1;
}
// If there is no bigger number
// with the same no. of 1's
if (c0 + c1 == 31 || c0 + c1 == 0)
return -1;
return n + (1 << c0) +
(1 << (c1 - 1)) - 1;
}
// Driver Code
public static void main (String[] args)
{
int n = 5; // input 1
System.out.println(getNext(n));
n = 8; // input 2
System.out.println(getNext(n));
}
}
// This code is contributed by ajit
Python3
# python3 Implementation of getNext with # Same number of bits 1's is below # Main Function to find next smallest number # bigger than n def getNext(n): # Compute c0 and c1 c = n c0 = 0 c1 = 0 while (((c & 1) == 0) and (c != 0)): c0 = c0+1 c >>= 1 while ((c & 1) == 1): c1 = c1+1 c >>= 1 # If there is no bigger number with the # same no. of 1's if (c0 + c1 == 31 or c0 + c1 == 0): return -1 return n + (1 << c0) + (1 << (c1 - 1)) - 1 # Driver Code if __name__ == '__main__': n = 5 # input 1 print(getNext(n)) n = 8 # input 2 print(getNext(n)) # This code is contributed by nirajgusain5
C#
// C# Implementation of getNext
// with Same number of bits
// 1's is below
using System;
class GFG
{
// Function to find next smallest
// number bigger than n
static int getNext(int n)
{
/* Compute c0
and c1 */
int c = n;
int c0 = 0;
int c1 = 0;
while (((c & 1) == 0) &&
(c != 0))
{
c0 ++;
c >>= 1;
}
while ((c & 1) == 1)
{
c1++;
c >>= 1;
}
// If there is no bigger
// number with the same
// no. of 1's
if (c0 + c1 == 31 ||
c0 + c1 == 0)
return -1;
return n + (1 << c0) +
(1 << (c1 - 1)) - 1;
}
// Driver Code
static public void Main ()
{
int n = 5; // input 1
Console.WriteLine(getNext(n));
n = 8; // input 2
Console.WriteLine(getNext(n));
}
}
// This code is contributed by m_kit
PHP
<?php
// PHP Implementation of
// getNext with Same number
// of bits 1's is below
// Main Function to find
// next smallest number
// bigger than n
function getNext($n)
{
/* Compute c0 and c1 */
$c = $n;
$c0 = 0;
$c1 = 0;
while ((($c & 1) == 0) &&
($c != 0))
{
$c0 ++;
$c >>= 1;
}
while (($c & 1) == 1)
{
$c1++;
$c >>= 1;
}
// If there is no bigger
// number with the
// same no. of 1's
if ($c0 + $c1 == 31 ||
$c0 + $c1 == 0)
return -1;
return $n + (1 << $c0) +
(1 << ($c1 - 1)) - 1;
}
// Driver Code
$n = 5; // input 1
echo getNext($n);
$n = 8; // input 2
echo "\n";
echo getNext($n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript Implementation of getNext
// with Same number of bits
// 1's is below
// Function to find next smallest
// number bigger than n
function getNext(n)
{
/* Compute c0
and c1 */
let c = n;
let c0 = 0;
let c1 = 0;
while (((c & 1) == 0) &&
(c != 0))
{
c0 ++;
c >>= 1;
}
while ((c & 1) == 1)
{
c1++;
c >>= 1;
}
// If there is no bigger
// number with the same
// no. of 1's
if (c0 + c1 == 31 ||
c0 + c1 == 0)
return -1;
return n + (1 << c0) +
(1 << (c1 - 1)) - 1;
}
let n = 5; // input 1
document.write(getNext(n) + "</br>");
n = 8; // input 2
document.write(getNext(n));
</script>
Producción :
6 16
Enfoque aritmético para obtener el número anterior
Si c1 es el número de unos finales, c0 es el tamaño del bloque cero inmediatamente siguiente y p = c0 + c1, podemos redactar la solución getPrev inicial de la siguiente manera:
- Establezca el bit pth en 0
- Establecer todos los bits siguientes p a 1
- Configure los bits 0 a c0 – 1 a 0.
Podemos implementar esto aritméticamente de la siguiente manera. Para mayor claridad en el ejemplo, asumimos n = 10000011. Esto hace que c1 = 2 y c0 = 5.
// Removes trailing 1s. n is now 10000000.
n -= 2c1 – 1;
// Flips trailing 0s. n is now 01111111.
n -= 1;
// Flips last (c0-1) 0s. n is now 01110000.
n -= 2c0 - 1 - 1;
This reduces mathematically to:
next = n - (2c1 - 1) - 1 - ( 2c0-1 - 1) .
= n - 2c1 - 2c0-1 + 1;
Una vez más, esto es muy fácil de implementar.
C++
// C++ Implementation of Arithmetic Approach to
// getPrev with Same number of bits 1's is below
#include <bits/stdc++.h>
using namespace std;
// Main Function to find next Bigger number
// Smaller than n
int getPrev(int n)
{
/* Compute c0 and c1 and store N*/
int temp = n;
int c0 = 0;
int c1 = 0;
while ((temp & 1) == 1)
{
c1++;
temp = temp >> 1;
}
if (temp == 0)
return -1;
while (((temp & 1) == 0) && (temp!= 0))
{
c0++;
temp = temp >> 1;
}
return n - (1 << c1) - (1 << (c0 - 1)) + 1;
}
// Driver Code
int main()
{
int n = 6; // input 1
cout << getPrev(n);
n = 16; // input 2
cout << endl;
cout << getPrev(n);
return 0;
}
Java
// Java Implementation of Arithmetic
// Approach to getPrev with Same
// number of bits 1's is below
import java.io.*;
class GFG
{
// Main Function to find next
// Bigger number Smaller than n
static int getPrev(int n)
{
/* Compute c0 and
c1 and store N*/
int temp = n;
int c0 = 0;
int c1 = 0;
while ((temp & 1) == 1)
{
c1++;
temp = temp >> 1;
}
if (temp == 0)
return -1;
while (((temp & 1) == 0) &&
(temp!= 0))
{
c0++;
temp = temp >> 1;
}
return n - (1 << c1) -
(1 << (c0 - 1)) + 1;
}
// Driver Code
public static void main (String[] args)
{
int n = 6; // input 1
System.out.println (getPrev(n));
n = 16; // input 2
System.out.println(getPrev(n));
}
}
// This code is contributed by akt_mit
Python3
# Python3 Implementation of Arithmetic Approach to # getPrev with Same number of bits 1's is below # Main Function to find next Bigger # number Smaller than n def getPrev(n): # Compute c0 and c1 and store N temp = n c0 = 0 c1 = 0 while ((temp & 1) == 1): c1 += 1 temp = temp >> 1 if (temp == 0): return -1 while (((temp & 1) == 0) and (temp != 0)): c0 += 1 temp = temp >> 1 return n - (1 << c1) - (1 << (c0 - 1)) + 1 # Driver Code if __name__ == '__main__': n = 6 # input 1 print(getPrev(n)) n = 16 # input 2 print(getPrev(n)) # This code is contributed # by PrinciRaj1992
C#
// C# Implementation of Arithmetic
// Approach to getPrev with Same
// number of bits 1's is below
using System;
class GFG
{
// Main Function to find next
// Bigger number Smaller than n
static int getPrev(int n)
{
/* Compute c0 and
c1 and store N*/
int temp = n;
int c0 = 0;
int c1 = 0;
while ((temp & 1) == 1)
{
c1++;
temp = temp >> 1;
}
if (temp == 0)
return -1;
while (((temp & 1) == 0) &&
(temp!= 0))
{
c0++;
temp = temp >> 1;
}
return n - (1 << c1) -
(1 << (c0 - 1)) + 1;
}
// Driver Code
static public void Main ()
{
int n = 6; // input 1
Console.WriteLine(getPrev(n));
n = 16; // input 2
Console.WriteLine(getPrev(n));
}
}
// This code is contributed by ajit
PHP
<?php
// PHP program to count of
// steps until one of the
// two numbers become 0.
// Returns count of steps
// before one of the numbers
// become 0 after repeated
// subtractions.
function countSteps($x, $y)
{
// If y divides x, then
// simply return x/y.
if ($x % $y == 0)
return floor(((int)$x / $y));
// Else recur. Note that this
// function works even if x is
// smaller than y because in that
// case first recursive call
// exchanges roles of x and y.
return floor(((int)$x / $y) +
countSteps($y, $x % $y));
}
// Driver code
$x = 100;
$y = 19;
echo countSteps($x, $y);
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript Implementation of Arithmetic
// Approach to getPrev with Same
// number of bits 1's is below
// Main Function to find next
// Bigger number Smaller than n
function getPrev(n)
{
/* Compute c0 and
c1 and store N*/
let temp = n;
let c0 = 0;
let c1 = 0;
while ((temp & 1) == 1)
{
c1++;
temp = temp >> 1;
}
if (temp == 0)
return -1;
while (((temp & 1) == 0) &&
(temp!= 0))
{
c0++;
temp = temp >> 1;
}
return n - (1 << c1) -
(1 << (c0 - 1)) + 1;
}
let n = 6; // input 1
document.write(getPrev(n) + "</br>");
n = 16; // input 2
document.write(getPrev(n));
</script>
Producción :
5 8
Este artículo es una contribución del Sr. Somesh Awasthi . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su 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