Encuentra el entero más cercano con el mismo peso

Dado un entero positivo X , la tarea es encontrar un entero Y tal que: 
 

1. El recuento de bits establecidos es Y es igual al recuento de bits establecidos en X .
2. X != Y .
3. |X-Y| es mínimo.

Ejemplos: 
 

Entrada: X = 92 
Salida: 90 
90 es el número más cercano a 92 que tiene 
el mismo número de bits establecidos.
Entrada: X = 17 
Salida: 18 
 

Enfoque: un poco de matemática puede llevarnos al enfoque de solución. Dado que el número de bits en ambos números tiene que ser el mismo, si se invierte un bit establecido, también tendrá que invertirse un bit no establecido. 
Ahora el problema se reduce a elegir dos bits para voltear. Supongamos que se invierte un bit en el índice i y otro bit en el índice j (j <i) del LSB (bit menos significativo). Entonces el valor absoluto de la diferencia entre el entero original y el nuevo es 2 ⁱ – 2 ^j . Para minimizar esto, i tiene que ser lo más pequeño posible y j tiene que estar lo más cerca posible de i . 
Dado que el número de bits establecidos debe ser igual, el bit en el índice i debe ser diferente del bit en el índice j . Esto significa que el más pequeño puede ser el bit más a la derecha que es diferente del LSB, y j debe ser el siguiente bit. En resumen, el enfoque correcto es intercambiar los dos bits consecutivos más a la derecha que son diferentes.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
const int NumUnsignBits = 64;
 
// Function to return the number
// closest to x which has equal
// number of set bits as x
unsigned long findNum(unsigned long x)
{
    // Loop for each bit in x and
    // compare with the next bit
    for (int i = 0; i < NumUnsignBits - 1; i++) {
        if (((x >> i) & 1) != ((x >> (i + 1)) & 1)) {
            x ^= (1 << i) | (1 << (i + 1));
            return x;
        }
    }
}
 
// Driver code
int main()
{
    int n = 92;
 
    cout << findNum(n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
static int NumUnsignBits = 64;
 
// Function to return the number
// closest to x which has equal
// number of set bits as x
static long findNum(long x)
{
    // Loop for each bit in x and
    // compare with the next bit
    for (int i = 0; i < NumUnsignBits - 1; i++)
    {
        if (((x >> i) & 1) != ((x >> (i + 1)) & 1))
        {
            x ^= (1 << i) | (1 << (i + 1));
            return x;
        }
    }
    return Long.MIN_VALUE;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 92;
 
    System.out.println(findNum(n));
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of the approach
NumUnsignBits = 64;
 
# Function to return the number
# closest to x which has equal
# number of set bits as x
def findNum(x) :
 
    # Loop for each bit in x and
    # compare with the next bit
    for i in range(NumUnsignBits - 1) :
        if (((x >> i) & 1) != ((x >> (i + 1)) & 1)) :
            x ^= (1 << i) | (1 << (i + 1));
            return x;
 
# Driver code
if __name__ == "__main__" :
    n = 92;
    print(findNum(n));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
     
class GFG
{
static int NumUnsignBits = 64;
 
// Function to return the number
// closest to x which has equal
// number of set bits as x
static long findNum(long x)
{
    // Loop for each bit in x and
    // compare with the next bit
    for (int i = 0; i < NumUnsignBits - 1; i++)
    {
        if (((x >> i) & 1) != ((x >> (i + 1)) & 1))
        {
            x ^= (1 << i) | (1 << (i + 1));
            return x;
        }
    }
    return long.MinValue;
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 92;
 
    Console.WriteLine(findNum(n));
}
}
 
// This code is contributed by Rajput-Ji

<script>
    // Javascript implementation of the approach
     
    let NumUnsignBits = 64;
   
    // Function to return the number
    // closest to x which has equal
    // number of set bits as x
    function findNum(x)
    {
        // Loop for each bit in x and
        // compare with the next bit
        for (let i = 0; i < NumUnsignBits - 1; i++)
        {
            if (((x >> i) & 1) != ((x >> (i + 1)) & 1))
            {
                x ^= (1 << i) | (1 << (i + 1));
                return x;
            }
        }
        return Number.MIN_VALUE;
    }
     
    let n = 92;
   
    document.write(findNum(n));
 
</script>

90

Complejidad de tiempo: O (logn)

Espacio Auxiliar: O(1)