Método eficiente para el complemento a 2 de una string binaria

Dado un número binario como string, imprime sus complementos a 2.
El complemento a 2 de un número binario es 1 sumado al complemento a 1 del número binario. Tenga en cuenta que el complemento de 1 es simplemente voltear el número binario dado. 

Ejemplos: 

2's complement of "0111" is  "1001"
2's complement of "1100" is  "0100" 

Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

Hemos discutido los complementos de 1 y 2 en la publicación a continuación.
Complemento a 1 y 2 de un Número Binario.

El método discutido en la publicación anterior atraviesa la string binaria dos veces para encontrar el complemento de 2, primero encuentra el complemento de 1, luego encuentra el complemento de 2 usando el complemento de 1.
En esta publicación se analiza un método eficiente para el complemento de 2 que atraviesa la string solo una vez . Recorremos la string desde el último hasta que el único 1 no se recorre y luego cambiamos todos los valores de la string, es decir, 0 a 1 y 1 a 0.

Nota: aquí para manejar el caso de la esquina, es decir, si 1 no existe en la string, simplemente agregue 1 al comienzo de la string. 

Ilustración : 

Input:  str = "1000100"
Output:        0111100
Explanation: Starts traversing the string from last,
we got first '1' at index 4 then just flip the bits 
of 0 to 3 indexes to make the 2's complement. 

Input:  str =  "0000"
Output:        10000
Explanation: As there is no 1 in the string so just 
append '1' at starting.

Implementación:

// An efficient C++ program to find 2's complement
#include<bits/stdc++.h>
using namespace std;
 
// Function to find two's complement
string findTwoscomplement(string str)
{
    int n = str.length();
 
    // Traverse the string to get first '1' from
    // the last of string
    int i;
    for (i = n-1 ; i >= 0 ; i--)
        if (str[i] == '1')
            break;
 
    // If there exists no '1' concatenate 1 at the
    // starting of string
    if (i == -1)
        return '1' + str;
 
    // Continue traversal after the position of
    // first '1'
    for (int k = i-1 ; k >= 0; k--)
    {
        //Just flip the values
        if (str[k] == '1')
            str[k] = '0';
        else
            str[k] = '1';
    }
 
    // return the modified string
    return str;
}
 
// Driver code
int main()
{
    string str = "00000101";
    cout << findTwoscomplement(str);
    return 0;
}             

// An efficient Java program to find 2's complement
 
class Test
{
    // Method to find two's complement
    static String findTwoscomplement(StringBuffer str)
    {
        int n = str.length();
      
        // Traverse the string to get first '1' from
        // the last of string
        int i;
        for (i = n-1 ; i >= 0 ; i--)
            if (str.charAt(i) == '1')
                break;
      
        // If there exists no '1' concat 1 at the
        // starting of string
        if (i == -1)
            return "1" + str;
      
        // Continue traversal after the position of
        // first '1'
        for (int k = i-1 ; k >= 0; k--)
        {
            //Just flip the values
            if (str.charAt(k) == '1')
                str.replace(k, k+1, "0");
            else
                str.replace(k, k+1, "1");
        }
      
        // return the modified string
        return str.toString();
    }
     
    // Driver method
    public static void main(String[] args)
    {
        StringBuffer str = new StringBuffer("00000101");
        System.out.println(findTwoscomplement(str));
    }
}

# An efficient Python 3 program to
# find 2's complement
 
# Function to find two's complement
def findTwoscomplement(str):
    n = len(str)
 
    # Traverse the string to get first
    # '1' from the last of string
    i = n - 1
    while(i >= 0):
        if (str[i] == '1'):
            break
 
        i -= 1
 
    # If there exists no '1' concatenate 1
    # at the starting of string
    if (i == -1):
        return '1'+str
 
    # Continue traversal after the
    # position of first '1'
    k = i - 1
    while(k >= 0):
         
        # Just flip the values
        if (str[k] == '1'):
            str = list(str)
            str[k] = '0'
            str = ''.join(str)
        else:
            str = list(str)
            str[k] = '1'
            str = ''.join(str)
 
        k -= 1
 
    # return the modified string
    return str
 
# Driver code
if __name__ == '__main__':
    str = "00000101"
    print(findTwoscomplement(str))
 
# This code is contributed by
# Sanjit_Prasad

// An efficient c# program to find 2's complement
using System;
using System.Text;
 
class GFG
{
// Method to find two's complement
public static string findTwoscomplement(StringBuilder str)
{
    int n = str.Length;
 
    // Traverse the string to get
    // first '1' from the last of string
    int i;
    for (i = n - 1 ; i >= 0 ; i--)
    {
        if (str[i] == '1')
        {
            break;
        }
    }
 
    // If there exists no '1' concat 1
    // at the starting of string
    if (i == -1)
    {
        return "1" + str;
    }
 
    // Continue traversal after the
    // position of first '1'
    for (int k = i - 1 ; k >= 0; k--)
    {
        // Just flip the values
        if (str[k] == '1')
        {
            str.Remove(k, k + 1 - k).Insert(k, "0");
        }
        else
        {
            str.Remove(k, k + 1 - k).Insert(k, "1");
        }
    }
 
    // return the modified string
    return str.ToString();
}
 
// Driver Code
public static void Main(string[] args)
{
    StringBuilder str = new StringBuilder("00000101");
    Console.WriteLine(findTwoscomplement(str));
}
}
 
// This code is contributed by Shrikant13

<?php
// An efficient PHP program to find 2's
// complement
 
// Function to find two's complement
function findTwoscomplement($str)
{
    $n = strlen($str);
 
    // Traverse the string to get first
    // '1' from the last of string
    $i;
    for ($i = $n-1 ; $i >= 0 ; $i--)
        if ($str[$i] == '1')
            break;
 
    // If there exists no '1' concatenate
    // 1 at the starting of string
    if ($i == -1)
        return '1' + $str;
 
    // Continue traversal after the
    // position of first '1'
    for ($k = $i-1 ; $k >= 0; $k--)
    {
        // Just flip the values
        if ($str[$k] == '1')
            $str[$k] = '0';
        else
            $str[$k] = '1';
    }
 
    // return the modified string
    return $str;;
}
 
// Driver code
$str = "00000101";
echo findTwoscomplement($str);
 
// This code is contributed by jit.
?>

<script>
 
// An efficient javascript program to find 2's complement
 
    // Method to find two's complement
    function findTwoscomplement( str) {
        var n = str.length;
 
        // Traverse the string to get first '1' from
        // the last of string
        var i;
        for (i = n - 1; i >= 0; i--)
            if (str.charAt(i) == '1')
                break;
 
        // If there exists no '1' concat 1 at the
        // starting of string
        if (i == -1)
            return "1" + str;
 
        // Continue traversal after the position of
        // first '1'
        for (k = i - 1; k >= 0; k--) {
            // Just flip the values
            if (str.charAt(k) == '1')
                str = str.substring(0,k)+"0"+str.substring(k+1, str.length);
            else
                str = str.substring(0,k)+"1"+str.substring(k+1, str.length);
        }
 
        // return the modified string
        return str.toString();
    }
 
    // Driver method
     
        var str = "00000101";
        document.write(findTwoscomplement(str));
 
// This code contributed by umadevi9616
</script>

11111011

Complejidad temporal : O(n) 
Espacio auxiliar : O(1)

Este artículo es una contribución de Sahil Chhabra (akku) . 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.