Dado un número binario como una string, imprima sus complementos de 1 y 2.
El complemento a 1 de un número binario es otro número binario obtenido alternando todos los bits en él, es decir, transformando el bit 0 en 1 y el bit 1 en 0. En el formato de complemento a 1, los números positivos permanecen sin cambios. Los números negativos se obtienen tomando el complemento a 1 de las contrapartes positivas.
por ejemplo, +9 se representará como 00001001 en notación de ocho bits y -9 se representará como 11110110, que es el complemento a 1 de 00001001.
Ejemplos:
1's complement of "0111" is "1000" 1's complement of "1100" is "0011"
El complemento a 2 de un número binario es 1, sumado al complemento a 1 del número binario. En la representación del complemento a 2 de los números binarios, el MSB representa el signo con un ‘0’ que se usa para el signo más y un ‘1’ que se usa para el signo menos. los bits restantes se utilizan para representar la magnitud. las magnitudes positivas se representan de la misma manera que en el caso de la representación de bits de signo o complemento a 1. Las magnitudes negativas están representadas por el complemento a 2 de sus contrapartes positivas.
Ejemplos:
2's complement of "0111" is "1001" 2's complement of "1100" is "0100"
Otro truco para encontrar el complemento a dos:
Paso 1: comience desde el bit menos significativo y avance hacia la izquierda hasta que encuentre un 1. Hasta que encuentre 1, los bits permanecen igual
Paso 2: Una vez que hayas encontrado el 1, deja el 1 como está, y ahora
Paso 3: voltea todos los bits que quedan en el 1.
Ilustración
Supongamos que necesitamos encontrar el complemento a 2 de 100100
Paso 1: Recorra y deje que el bit permanezca igual hasta que encuentre 1. Aquí x aún no se conoce. Respuesta = xxxx00 –
Paso 2 : Encontraste 1. Deja que permanezca igual. Respuesta = xxx100
Paso 3: voltea todos los bits restantes en el 1. Respuesta = 011100.
Por lo tanto, el complemento a 2 de 100100 es 011100.
Para el complemento a uno, simplemente necesitamos voltear todos los bits.
Para el complemento a 2, primero encontramos el complemento a uno. Recorremos el complemento a uno comenzando desde LSB (bit menos significativo) y buscamos el 0. Volteamos todos los 1 (cambiamos a 0) hasta encontrar un 0. Finalmente, volteamos el 0 encontrado. Por ejemplo, el complemento a 2 de “01000 ” es “11000” (Tenga en cuenta que primero encontramos el complemento de uno de 01000 como 10111). Si hay todos 1 (en el complemento de uno), agregamos un 1 adicional en la string. Por ejemplo, el complemento a 2 de “000” es “1000” (el complemento a 1 de “000” es “111”).
A continuación se muestra la implementación.
C++
// C++ program to print 1's and 2's complement of
// a binary number
#include <bits/stdc++.h>
using namespace std;
// Returns '0' for '1' and '1' for '0'
char flip(char c) {return (c == '0')? '1': '0';}
// Print 1's and 2's complement of binary number
// represented by "bin"
void printOneAndTwosComplement(string bin)
{
int n = bin.length();
int i;
string ones, twos;
ones = twos = "";
// for ones complement flip every bit
for (i = 0; i < n; i++)
ones += flip(bin[i]);
// for two's complement go from right to left in
// ones complement and if we get 1 make, we make
// them 0 and keep going left when we get first
// 0, make that 1 and go out of loop
twos = ones;
for (i = n - 1; i >= 0; i--)
{
if (ones[i] == '1')
twos[i] = '0';
else
{
twos[i] = '1';
break;
}
}
// If No break : all are 1 as in 111 or 11111;
// in such case, add extra 1 at beginning
if (i == -1)
twos = '1' + twos;
cout << "1's complement: " << ones << endl;
cout << "2's complement: " << twos << endl;
}
// Driver program
int main()
{
string bin = "1100";
printOneAndTwosComplement(bin);
return 0;
}
Java
// Java program to print 1's and 2's complement of
// a binary number
class GFG
{
// Returns '0' for '1' and '1' for '0'
static char flip(char c)
{
return (c == '0') ? '1' : '0';
}
// Print 1's and 2's complement of binary number
// represented by "bin"
static void printOneAndTwosComplement(String bin)
{
int n = bin.length();
int i;
String ones = "", twos = "";
ones = twos = "";
// for ones complement flip every bit
for (i = 0; i < n; i++)
{
ones += flip(bin.charAt(i));
}
// for two's complement go from right to left in
// ones complement and if we get 1 make, we make
// them 0 and keep going left when we get first
// 0, make that 1 and go out of loop
twos = ones;
for (i = n - 1; i >= 0; i--)
{
if (ones.charAt(i) == '1')
{
twos = twos.substring(0, i) + '0' + twos.substring(i + 1);
}
else
{
twos = twos.substring(0, i) + '1' + twos.substring(i + 1);
break;
}
}
// If No break : all are 1 as in 111 or 11111;
// in such case, add extra 1 at beginning
if (i == -1)
{
twos = '1' + twos;
}
System.out.println("1's complement: " + ones);;
System.out.println("2's complement: " + twos);
}
// Driver code
public static void main(String[] args)
{
String bin = "1100";
printOneAndTwosComplement(bin);
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 program to print 1's and 2's
# complement of a binary number
# Returns '0' for '1' and '1' for '0'
def flip(c):
return '1' if (c == '0') else '0'
# Print 1's and 2's complement of
# binary number represented by "bin"
def printOneAndTwosComplement(bin):
n = len(bin)
ones = ""
twos = ""
# for ones complement flip every bit
for i in range(n):
ones += flip(bin[i])
# for two's complement go from right
# to left in ones complement and if
# we get 1 make, we make them 0 and
# keep going left when we get first
# 0, make that 1 and go out of loop
ones = list(ones.strip(""))
twos = list(ones)
for i in range(n - 1, -1, -1):
if (ones[i] == '1'):
twos[i] = '0'
else:
twos[i] = '1'
break
i -= 1
# If No break : all are 1 as in 111 or 11111
# in such case, add extra 1 at beginning
if (i == -1):
twos.insert(0, '1')
print("1's complement: ", *ones, sep = "")
print("2's complement: ", *twos, sep = "")
# Driver Code
if __name__ == '__main__':
bin = "1100"
printOneAndTwosComplement(bin.strip(""))
# This code is contributed
# by SHUBHAMSINGH10
C#
// C# program to print 1's and 2's complement of
// a binary number
using System;
class GFG
{
// Returns '0' for '1' and '1' for '0'
static char flip(char c)
{
return (c == '0') ? '1' : '0';
}
// Print 1's and 2's complement of binary number
// represented by "bin"
static void printOneAndTwosComplement(String bin)
{
int n = bin.Length;
int i;
String ones = "", twos = "";
ones = twos = "";
// for ones complement flip every bit
for (i = 0; i < n; i++)
{
ones += flip(bin[i]);
}
// for two's complement go from right to left in
// ones complement and if we get 1 make, we make
// them 0 and keep going left when we get first
// 0, make that 1 and go out of loop
twos = ones;
for (i = n - 1; i >= 0; i--)
{
if (ones[i] == '1')
{
twos = twos.Substring(0, i) + '0' +
twos.Substring(i + 1,twos.Length-(i+1));
}
else
{
twos = twos.Substring(0, i) + '1' +
twos.Substring(i + 1,twos.Length-(i+1));
break;
}
}
// If No break : all are 1 as in 111 or 11111;
// in such case, add extra 1 at beginning
if (i == -1)
{
twos = '1' + twos;
}
Console.WriteLine("1's complement: " + ones);;
Console.WriteLine("2's complement: " + twos);
}
// Driver code
public static void Main(String[] args)
{
String bin = "1100";
printOneAndTwosComplement(bin);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript program to print 1's and 2's complement of
// a binary number
// Returns '0' for '1' and '1' for '0'
function flip (c) {return (c == '0')? '1': '0';}
// Print 1's and 2's complement of binary number
// represented by "bin"
function printOneAndTwosComplement(bin)
{
var n = bin.length;
var i;
var ones, twos;
ones = twos = "";
// for ones complement flip every bit
for (i = 0; i < n; i++)
ones += flip(bin[i]);
// for two's complement go from right to left in
// ones complement and if we get 1 make, we make
// them 0 and keep going left when we get first
// 0, make that 1 and go out of loop
twos = ones;
twos = twos.split('')
for (i = n - 1; i >= 0; i--)
{
if (ones[i] == '1')
twos[i] = '0';
else
{
twos[i] = '1';
break;
}
}
twos = twos.join('')
// If No break : all are 1 as in 111 or 11111;
// in such case, add extra 1 at beginning
if (i == -1)
twos = '1' + twos;
document.write( "1's complement: " + ones + "<br>");
document.write( "2's complement: " + twos + "<br>");
}
// Driver program
var bin = "1100";
printOneAndTwosComplement(bin);
</script>
Producción:
1's complement: 0011 2's complement: 0100
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Gracias a Utkarsh Trivedi por la solución anterior.
Como nota al margen, los números con signo generalmente usan la representación del complemento a 2. Los valores positivos se almacenan tal cual y los valores negativos se almacenan en su forma de complemento a 2. Se requiere un bit adicional para indicar si el número es positivo o negativo. Por ejemplo, char tiene 8 bits en C. Si se usa la representación de complemento a 2 para char, entonces 127 se almacena tal cual, es decir, 01111111, donde el primer 0 indica positivo. Pero -127 se almacena como 10000001. Publicación
relacionada:
método eficiente para el complemento a 2 de una string binaria
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema discutido anteriormente.
Referencias:
http://qa.geeksforgeeks.org/6439/write-program-calculate-ones-and-twos-complement-of-number
http://geeksquiz.com/whats-difference- between-1s-complement-and-2s -complementar/
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