Siguiente número mayor que N con exactamente un bit diferente en representación binaria de N

Dado un número N. La tarea es encontrar el número más pequeño que sea mayor que N y tenga solo un bit diferente en la representación binaria de N. 
Nota : Aquí N puede ser muy grande 10^9 < N < 10^15.
Ejemplos: 
 

Input : N = 11
Output : The next number is 15
The binary representation of 11 is 1011
So the smallest number greater than 11 
with one bit different is 1111 which is 15.

Input : N = 17
Output : The next number is 19

Enfoque simple : Ejecutaremos un bucle desde N+1 hasta que encontremos un número que tenga exactamente un bit diferente a N. Este proceso puede tardar mucho en procesarse en caso de números grandes.
Enfoque eficiente : En el enfoque eficiente, tenemos que representar el número en su forma binaria. Ahora, un número mayor que N con solo 1 bit diferente solo es posible cuando mantenemos intactos todos los bits establecidos del número N y cambiamos el bit más bajo posible que es cero a 1. 
Tomemos el ejemplo, 1001 que es la forma binaria de 9, 
Si cambiamos los bits establecidos de 1001 a 1000 o 0001, encontramos que los números son 8 y 1, que son menores que N. Mientras que si cambiamos los bits que son cero a 1, encontramos que los números son 11 (1011) o 13 (1101), por lo que si cambiamos el bit más bajo posible que es cero a 1, obtenemos el número más pequeño posible mayor que N con solo 1 bit diferente, en este caso es 11 (1011).
Nota : Se garantiza que el número de entrada N no tiene todos sus bits configurados. Existe al menos un bit no establecido en la representación binaria de N.
A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to find next greater number than N
// with exactly one bit different in binary
// representation of N
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find next greater number than N
// with exactly one bit different in binary
// representation of N
long long nextGreater(long long N)
{
    long long power_of_2 = 1, shift_count = 0;
 
    // It is guaranteed that there
    // is a bit zero in the number
    while (true) {
        // If the shifted bit is zero then break
        if (((N >> shift_count) & 1) % 2 == 0)
            break;
 
        // increase the bit shift
        shift_count++;
 
        // increase the power of 2
        power_of_2 = power_of_2 * 2;
    }
 
    // set the lowest bit of the number
    return (N + power_of_2);
}
 
// Driver code
int main()
{
    long long N = 11;
 
    // display the next number
    cout << "The next number is = " << nextGreater(N);
 
    return 0;
}

// Java program to find next greater number than N
// with exactly one bit different in binary
// representation of N
 
class GFG{
// Function to find next greater number than N
// with exactly one bit different in binary
// representation of N
static int nextGreater(int N)
{
    int power_of_2 = 1, shift_count = 0;
 
    // It is guaranteed that there
    // is a bit zero in the number
    while (true) {
        // If the shifted bit is zero then break
        if (((N >> shift_count) & 1) % 2 == 0)
            break;
 
        // increase the bit shift
        shift_count++;
 
        // increase the power of 2
        power_of_2 = power_of_2 * 2;
    }
 
    // set the lowest bit of the number
    return (N + power_of_2);
}
 
// Driver code
public static void main(String[]a)
{
    int N = 11;
 
    // display the next number
    System.out.println("The next number is = " + nextGreater(N));
 
}
}

# Python3 program to find next greater
# number than N with exactly one
# bit different in binary
# representation of N
 
# Function to find next greater
# number than N with exactly
# one bit different in binary
# representation of N
def nextGreater(N):
 
    power_of_2 = 1;
    shift_count = 0;
 
    # It is guaranteed that there
    # is a bit zero in the number
    while (True):
         
        # If the shifted bit is
        # zero then break
        if (((N >> shift_count) & 1) % 2 == 0):
            break;
 
        # increase the bit shift
        shift_count += 1;
 
        # increase the power of 2
        power_of_2 = power_of_2 * 2;
 
    # set the lowest bit
    # of the number
    return (N + power_of_2);
 
# Driver code
N = 11;
 
# display the next number
print("The next number is =",
             nextGreater(N));
 
# This code is contributed by mits

// C# program to find next
// greater number than N with 
// exactly one bit different in
// binary representation of N
using System;
 
class GFG
{
// Function to find next greater
// number than N with exactly
// one bit different in binary
// representation of N
static int nextGreater(int N)
{
    int power_of_2 = 1,
        shift_count = 0;
 
    // It is guaranteed that there
    // is a bit zero in the number
    while (true)
    {
        // If the shifted bit is
        // zero then break
        if (((N >> shift_count) & 1) % 2 == 0)
            break;
 
        // increase the bit shift
        shift_count++;
 
        // increase the power of 2
        power_of_2 = power_of_2 * 2;
    }
 
    // set the lowest bit
    // of the number
    return (N + power_of_2);
}
 
// Driver code
public static void Main()
{
    int N = 11;
 
    // display the next number
    Console.WriteLine("The next number is = " +
                               nextGreater(N));
}
}
 
// This code is contributed
// by anuj_67

<?php
// PHP program to find next greater
// number than N with exactly one
// bit different in binary
// representation of N
 
// Function to find next greater
// number than N with exactly
// one bit different in binary
// representation of N
function nextGreater($N)
{
    $power_of_2 = 1;
    $shift_count = 0;
 
    // It is guaranteed that there
    // is a bit zero in the number
    while (true)
    {
        // If the shifted bit is
        // zero then break
        if ((($N >> $shift_count) & 1) % 2 == 0)
            break;
 
        // increase the bit shift
        $shift_count++;
 
        // increase the power of 2
        $power_of_2 = $power_of_2 * 2;
    }
 
    // set the lowest bit of the number
    return ($N + $power_of_2);
}
 
// Driver code
$N = 11;
 
// display the next number
echo "The next number is = " ,
              nextGreater($N);
 
// This code is contributed
// by anuj_67
?>

<script>
 
//Javascript program to find next greater number than N
// with exactly one bit different in binary
// representation of N
 
 
// Function to find next greater number than N
// with exactly one bit different in binary
// representation of N
function nextGreater(N)
{
   var power_of_2 = 1, shift_count = 0;
 
    // It is guaranteed that there
    // is a bit zero in the number
    while (true) {
        // If the shifted bit is zero then break
        if (((N >> shift_count) & 1) % 2 == 0)
            break;
 
        // increase the bit shift
        shift_count++;
 
        // increase the power of 2
        power_of_2 = power_of_2 * 2;
    }
 
    // set the lowest bit of the number
    return (N + power_of_2);
}
 
var N = 11;
// display the next number
document.write("The next number is = " + nextGreater(N));
 
// This code is contributed by SoumikMondal
 
</script>

The next number is = 15

Complejidad de tiempo: O(log(N)), donde N representa el entero dado.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.