Representación binaria del siguiente número

Dada una entrada binaria que represente la representación binaria del número positivo n, encuentre una representación binaria de n+1.
La entrada binaria puede ser y puede no caber incluso en int largo largo sin signo.

Ejemplos: 

Input : 10011
Output : 10100
Here n = (19)10 = (10011)2
next greater integer = (20)10 = (10100)2 

Input : 111011101001111111
Output : 111011101010000000 

Almacenamos la entrada como una string para poder manejar grandes números. Atravesamos la string desde el carácter más a la derecha y convertimos todos los 1 en 0 hasta que encontramos un 0. Finalmente, convertimos el 0 encontrado en 1. Si no encontramos un 0, agregamos un 1 a la string general. 

string nextGreater(num)
  l = num.length

  // Find first 0 from right side. While
  // searching, convert 1s to 0s
  for i = l-1 to 0
    if num[i] == '0'
       num[i] = '1'
       break
    else
       num[i] = '0'
         
  // If there was no 0  
  if i < 0
      num = '1' + num
  return num        

A continuación se muestra la implementación de la idea anterior. 

// C++ implementation to find the binary
// representation of next greater integer
#include <bits/stdc++.h>
using namespace std;
 
// function to find the required
// binary representation
string nextGreater(string num)
{
    int l = num.size();
 
    // examine bits from the right
    for (int i=l-1; i>=0; i--)
    {
        // if '0' is encountered, convert
        // it to '1' and then break
        if (num.at(i) == '0')
        {
            num.at(i) = '1';
            break;
        }
 
        // else convert '1' to '0'
        else
            num.at(i) = '0';
 
 
    // if the binary representation
    // contains only the set bits
    if (i < 0)
        num = "1" + num;
    }
    // final binary representation
    // of the required integer
    return num;
}
 
// Driver program to test above
int main()
{
    string num = "10011";
    cout << "Binary representation of next number = "
         << nextGreater(num);
    return 0;
}

// Java implementation to find the binary
// representation of next greater integer
 
class GFG {
 
// function to find the required
// binary representation
    static String nextGreater(String num) {
 
        int l = num.length();
        int i;
        // examine bits from the right
        for (i = l - 1; i >= 0; i--) {
            // if '0' is encountered, convert
            // it to '1' and then break
            if (num.charAt(i) == '0') {
                num = num.substring(0, i) + '1' + num.substring(i+1);
                break;
            } // else convert '1' to '0'
            else {
                num = num.substring(0, i) + '0' + num.substring(i + 1);
            }
            // num[i] = '0';
        }
 
        // if the binary representation
        // contains only the set bits
        if (i < 0) {
            num = "1" + num;
        }
 
        // final binary representation
        // of the required integer
        return num;
    }
 
// Driver program to test above
    public static void main(String[] args) {
        String num = "10011";
        System.out.println("Binary representation of next number = "
                + nextGreater(num));
    }
}
//this code contributed by Rajput-Ji

# Python3 implementation to find the binary
# representation of next greater integer
 
# function to find the required
# binary representation
def nextGreater(num1):
 
    l = len(num1);
    num = list(num1);
 
    # examine bits from the right
    i = l-1;
    while(i >= 0):
        # if '0' is encountered, convert
        # it to '1' and then break
        if (num[i] == '0'):
            num[i] = '1';
            break;
 
        # else convert '1' to '0'
        else:
            num[i] = '0';
        i-=1;
 
    # if the binary representation
    # contains only the set bits
    num1 = ''.join(num);
    if (i < 0):
        num1 = '1' + num1;
 
    # final binary representation
    # of the required integer
    return num1;
 
# Driver Code
num = "10011";
print("Binary representation of next number = ",nextGreater(num));
 
# This code is contributed by mits

     
// C# implementation to find the binary
// representation of next greater integer
 using System;
public class GFG {
  
// function to find the required
// binary representation
    static String nextGreater(String num) {
  
        int l = num.Length;
        int i;
        // examine bits from the right
        for (i = l - 1; i >= 0; i--) {
            // if '0' is encountered, convert
            // it to '1' and then break
            if (num[i] == '0') {
                num = num.Substring(0, i) + '1' + num.Substring(i+1);
                break;
            } // else convert '1' to '0'
            else {
                num = num.Substring(0, i) + '0' + num.Substring(i + 1);
            }
            // num[i] = '0';
        }
  
        // if the binary representation
        // contains only the set bits
        if (i < 0) {
            num = "1" + num;
        }
  
        // final binary representation
        // of the required integer
        return num;
    }
  
// Driver program to test above
    public static void Main() {
        String num = "10011";
        Console.WriteLine("Binary representation of next number = "
                + nextGreater(num));
    }
}
//this code contributed by Rajput-Ji

<?php
// PHP implementation to find the binary
// representation of next greater integer
 
// function to find the required
// binary representation
function nextGreater($num)
{
    $l = strlen($num);
 
    // examine bits from the right
    for ($i = $l - 1; $i >= 0; $i--)
    {
        // if '0' is encountered, convert
        // it to '1' and then break
        if ($num[$i] == '0')
        {
            $num[$i] = '1';
            break;
        }
 
        // else convert '1' to '0'
        else
            $num[$i] = '0';
    }
 
    // if the binary representation
    // contains only the set bits
    if ($i < 0)
        $num = "1" . $num;
 
    // final binary representation
    // of the required integer
    return $num;
}
 
// Driver Code
$num = "10011";
echo "Binary representation of next number = " .
                              nextGreater($num);
 
// This code is contributed by ita_c
?>

<script>
 
// Javascript implementation to find the binary
// representation of next greater integer
     
    // function to find the required
    // binary representation
    function nextGreater(num)
    {
        let l = num.length;
        let i;
        // examine bits from the right
        for (i = l - 1; i >= 0; i--) {
            // if '0' is encountered, convert
            // it to '1' and then break
            if (num[i] == '0') {
                num = num.substring(0, i) + '1'
                + num.substring(i+1);
                break;
            } // else convert '1' to '0'
            else {
                num = num.substring(0, i) + '0'
                + num.substring(i + 1);
            }
            // num[i] = '0';
        }
   
        // if the binary representation
        // contains only the set bits
        if (i < 0) {
            num = "1" + num;
        }
   
        // final binary representation
        // of the required integer
        return num;
    }
     
    // Driver program to test above
    let num = "10011";
    document.write(
    "Binary representation of next number = "
                            + nextGreater(num)
    );
     
     
    // This code is contributed by rag2127
     
</script>

Binary representation of next number = 10100

Complejidad de tiempo: O(n) donde n es el número de bits en la entrada.
Espacio Auxiliar: O(n), ya que la string se copia cuando la pasamos a una función.

Este artículo es una contribución de Ayush Jauhari . 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.