Número binario es la forma predeterminada de almacenar números, pero en muchas aplicaciones, los números binarios son difíciles de usar y se necesita una variedad de números binarios. Aquí es donde los códigos Gray son muy útiles.
El código gris tiene la propiedad de que dos números sucesivos difieren en solo un bit debido a esta propiedad, el código gris realiza el ciclo a través de varios estados con un esfuerzo mínimo y se usa en mapas K, corrección de errores, comunicación, etc.
¿Cómo generar códigos grises de n bits?
Following is 2-bit sequence (n = 2) 00 01 11 10 Following is 3-bit sequence (n = 3) 000 001 011 010 110 111 101 100 And Following is 4-bit sequence (n = 4) 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
Los códigos Gray de n bits se pueden generar a partir de una lista de códigos Gray de (n-1) bits mediante los siguientes pasos.
- Sea L1 la lista de códigos Gray de (n-1) bits. Cree otra lista L2 que sea la inversa de L1.
- Modifique la lista L1 anteponiendo un ‘0’ en todos los códigos de L1.
- Modifique la lista L2 anteponiendo un ‘1’ en todos los códigos de L2.
- Concatenar L1 y L2. La lista concatenada es la lista requerida de códigos Gray de n bits.
Consulte Generar códigos grises de n bits para obtener un programa detallado.
¿Cómo convertir binario a gris y viceversa?
Binary : 0011 Gray : 0010 Binary : 01001 Gray : 01101
En informática muchas veces necesitamos convertir código binario a código gris y viceversa. Esta conversión se puede hacer aplicando las siguientes reglas:
Conversión de binario a gris:
- El bit más significativo (MSB) del código gris siempre es igual al MSB del código binario dado.
- Se pueden obtener otros bits del código gris de salida mediante XORing bit de código binario en ese índice y el índice anterior.
Conversión de código binario a código gris
Conversión de gris a binario:
- El bit más significativo (MSB) del código binario siempre es igual al MSB del código gris dado.
- Se pueden obtener otros bits del código binario de salida comprobando el bit de código gris en ese índice. Si el bit de código gris actual es 0, copie el bit de código binario anterior; de lo contrario, copie la inversión del bit de código binario anterior.
Conversión de código gris a código binario
A continuación se muestra la implementación de los pasos anteriores.
C++
// C++ program for Binary To Gray
// and Gray to Binary conversion
#include <iostream>
using namespace std;
// Helper function to xor two characters
char xor_c(char a, char b) { return (a == b) ? '0' : '1'; }
// Helper function to flip the bit
char flip(char c) { return (c == '0') ? '1' : '0'; }
// function to convert binary string
// to gray string
string binarytoGray(string binary)
{
string gray = "";
// MSB of gray code is same as binary code
gray += binary[0];
// Compute remaining bits, next bit is computed by
// doing XOR of previous and current in Binary
for (int i = 1; i < binary.length(); i++) {
// Concatenate XOR of previous bit
// with current bit
gray += xor_c(binary[i - 1], binary[i]);
}
return gray;
}
// function to convert gray code string
// to binary string
string graytoBinary(string gray)
{
string binary = "";
// MSB of binary code is same as gray code
binary += gray[0];
// Compute remaining bits
for (int i = 1; i < gray.length(); i++) {
// If current bit is 0, concatenate
// previous bit
if (gray[i] == '0')
binary += binary[i - 1];
// Else, concatenate invert of
// previous bit
else
binary += flip(binary[i - 1]);
}
return binary;
}
// Driver program to test above functions
int main()
{
string binary = "01001";
cout << "Gray code of " << binary << " is "
<< binarytoGray(binary) << endl;
string gray = "01101";
cout << "Binary code of " << gray << " is "
<< graytoBinary(gray) << endl;
return 0;
}
Java
// Java program for Binary To Gray
// and Gray to Binary conversion
import java.io.*;
class code_conversion
{
// Helper function to xor
// two characters
char xor_c(char a, char b)
{
return (a == b) ? '0' : '1';
}
// Helper function to flip the bit
char flip(char c)
{
return (c == '0') ? '1' : '0';
}
// function to convert binary
// string to gray string
String binarytoGray(String binary)
{
String gray = "";
// MSB of gray code is same
// as binary code
gray += binary.charAt(0);
// Compute remaining bits, next bit is
// computed by doing XOR of previous
// and current in Binary
for (int i = 1; i < binary.length(); i++)
{
// Concatenate XOR of previous bit
// with current bit
gray += xor_c(binary.charAt(i - 1),
binary.charAt(i));
}
return gray;
}
// function to convert gray code
// string to binary string
String graytoBinary(String gray)
{
String binary = "";
// MSB of binary code is same
// as gray code
binary += gray.charAt(0);
// Compute remaining bits
for (int i = 1; i < gray.length(); i++)
{
// If current bit is 0,
// concatenate previous bit
if (gray.charAt(i) == '0')
binary += binary.charAt(i - 1);
// Else, concatenate invert of
// previous bit
else
binary += flip(binary.charAt(i - 1));
}
return binary;
}
// Driver program to test above functions
public static void main(String args[])
throws IOException
{
code_conversion ob = new code_conversion();
String binary = "01001";
System.out.println("Gray code of " +
binary + " is " +
ob.binarytoGray(binary));
String gray = "01101";
System.out.println("Binary code of " +
gray + " is " +
ob.graytoBinary(gray));
}
}
// This code is contributed by Anshika Goyal.
Python3
# Python3 program for Binary To Gray
# and Gray to Binary conversion
# Helper function to xor two characters
def xor_c(a, b):
return '0' if(a == b) else '1';
# Helper function to flip the bit
def flip(c):
return '1' if(c == '0') else '0';
# function to convert binary string
# to gray string
def binarytoGray(binary):
gray = "";
# MSB of gray code is same as
# binary code
gray += binary[0];
# Compute remaining bits, next bit
# is computed by doing XOR of previous
# and current in Binary
for i in range(1, len(binary)):
# Concatenate XOR of previous
# bit with current bit
gray += xor_c(binary[i - 1],
binary[i]);
return gray;
# function to convert gray code
# string to binary string
def graytoBinary(gray):
binary = "";
# MSB of binary code is same
# as gray code
binary += gray[0];
# Compute remaining bits
for i in range(1, len(gray)):
# If current bit is 0,
# concatenate previous bit
if (gray[i] == '0'):
binary += binary[i - 1];
# Else, concatenate invert
# of previous bit
else:
binary += flip(binary[i - 1]);
return binary;
# Driver Code
binary = "01001";
print("Gray code of", binary, "is",
binarytoGray(binary));
gray = "01101";
print("Binary code of", gray, "is",
graytoBinary(gray));
# This code is contributed by mits
C#
// C# program for Binary To Gray
// and Gray to Binary conversion.
using System;
class GFG {
// Helper function to xor
// two characters
static char xor_c(char a, char b)
{
return (a == b) ? '0' : '1';
}
// Helper function to flip the bit
static char flip(char c)
{
return (c == '0') ? '1' : '0';
}
// function to convert binary
// string to gray string
static String binarytoGray(String binary)
{
String gray = "";
// MSB of gray code is same
// as binary code
gray += binary[0];
// Compute remaining bits, next
// bit is computed by doing XOR
// of previous and current in
// Binary
for (int i = 1; i < binary.Length; i++) {
// Concatenate XOR of previous
// bit with current bit
gray += xor_c(binary[i - 1],
binary[i]);
}
return gray;
}
// function to convert gray code
// string to binary string
static String graytoBinary(String gray)
{
String binary = "";
// MSB of binary code is same
// as gray code
binary += gray[0];
// Compute remaining bits
for (int i = 1; i < gray.Length; i++) {
// If current bit is 0,
// concatenate previous bit
if (gray[i] == '0')
binary += binary[i - 1];
// Else, concatenate invert of
// previous bit
else
binary += flip(binary[i - 1]);
}
return binary;
}
// Driver program to test above
// functions
public static void Main()
{
String binary = "01001";
Console.WriteLine("Gray code of "
+ binary + " is "
+ binarytoGray(binary));
String gray = "01101";
Console.Write("Binary code of "
+ gray + " is "
+ graytoBinary(gray));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program for Binary To Gray
// and Gray to Binary conversion
// Helper function to xor two characters
function xor_c($a, $b)
{
return ($a == $b) ? '0' : '1';
}
// Helper function to flip the bit
function flip($c)
{
return ($c == '0') ? '1' : '0';
}
// function to convert binary string
// to gray string
function binarytoGray($binary)
{
$gray = "";
// MSB of gray code is same as
// binary code
$gray .= $binary[0];
// Compute remaining bits, next bit is
// computed by doing XOR of previous
// and current in Binary
for ($i = 1; $i < strlen($binary); $i++)
{
// Concatenate XOR of previous bit
// with current bit
$gray .= xor_c($binary[$i - 1], $binary[$i]);
}
return $gray;
}
// function to convert gray code string
// to binary string
function graytoBinary($gray)
{
$binary = "";
// MSB of binary code is same as gray code
$binary .= $gray[0];
// Compute remaining bits
for ($i = 1; $i < strlen($gray); $i++)
{
// If current bit is 0, concatenate
// previous bit
if ($gray[$i] == '0')
$binary .= $binary[$i - 1];
// Else, concatenate invert of
// previous bit
else
$binary .= flip($binary[$i - 1]);
}
return $binary;
}
// Driver Code
$binary = "01001";
print("Gray code of " . $binary . " is " .
binarytoGray($binary) . "\n");
$gray = "01101";
print("Binary code of " . $gray . " is " .
graytoBinary($gray));
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program for Binary To Gray
// and Gray to Binary conversion
// Helper function to xor two characters
function xor_c(a, b){ return (a == b) ? '0' : '1'; }
// Helper function to flip the bit
function flip(c){ return (c == '0') ? '1' : '0'; }
// Function to convert binary string
// to gray string
function binarytoGray(binary)
{
let gray = "";
// MSB of gray code is same
// as binary code
gray += binary[0];
// Compute remaining bits, next bit
// is computed by doing XOR of previous
// and current in Binary
for(let i = 1; i < binary.length; i++)
{
// Concatenate XOR of previous bit
// with current bit
gray += xor_c(binary[i - 1], binary[i]);
}
return gray;
}
// Function to convert gray code string
// to binary string
function graytoBinary(gray)
{
let binary = "";
// MSB of binary code is same
// as gray code
binary += gray[0];
// Compute remaining bits
for(let i = 1; i < gray.length; i++)
{
// If current bit is 0, concatenate
// previous bit
if (gray[i] == '0')
binary += binary[i - 1];
// Else, concatenate invert of
// previous bit
else
binary += flip(binary[i - 1]);
}
return binary;
}
// Driver code
let binary = "01001";
document.write("Gray code of " + binary + " is " +
binarytoGray(binary) + "</br>");
let gray = "01101";
document.write("Binary code of " + gray + " is " +
graytoBinary(gray));
// This code is contributed by vaibhavrabadiya3
</script>
Producción
Gray code of 01001 is 01101 Binary code of 01101 is 01001
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Aquí, n es la longitud de la string binaria.
De binario a gris usando operadores bit a bit
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
int greyConverter(int n) { return n ^ (n >> 1); }
int main()
{
int n = 3;
cout << greyConverter(n) << endl;
n = 9;
cout << greyConverter(n) << endl;
return 0;
}
Java
// Java Program for above approach
public class Main {
public static int greyConverter(int n)
{
return n ^ (n >> 1);
}
// Driver code
public static void main(String[] args)
{
int n = 3;
System.out.println(greyConverter(n));
n = 9;
System.out.println(greyConverter(n));
}
}
// This code is contributed by divyesh072019
Python3
# Python3 code for above approach def greyConverter(n): return n ^ (n >> 1) n = 3 print(greyConverter(n)) n = 9 print(greyConverter(n)) # This code is contributed by divyeshrabadiya07
C#
// C# program for above approach
using System;
class GFG {
static int greyConverter(int n) { return n ^ (n >> 1); }
// Driver Code
public static void Main(string[] args)
{
int n = 3;
Console.WriteLine(greyConverter(n));
n = 9;
Console.WriteLine(greyConverter(n));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program for above approach
function greyConverter(n)
{
return n ^ (n >> 1);
}
// Driver code
let n = 3;
document.write(greyConverter(n) + "</br>");
n = 9;
document.write(greyConverter(n));
// This code is contributed by suresh07
</script>
Producción
2 13
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
De gris a binario usando operadores bit a bit
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
int binaryConverter(int n)
{
int res = n;
while (n > 0)
{
n >>= 1;
res ^= n;
}
return res;
}
// Driver Code
int main()
{
int n = 4;
// Function call
cout << binaryConverter(n) << endl;
return 0;
}
// This code is contributed by sshrey47
Java
// Java Program for above approach
public class Main {
public static int binaryConverter(int n)
{
int res = n;
while (n > 0) {
n >>= 1;
res ^= n;
}
return res;
}
// Driver code
public static void main(String[] args)
{
int n = 4;
System.out.println(binaryConverter(n));
}
}
// This code is contributed by sshrey47
Python3
# Python3 code for above approach def binaryConverter(n): res = n while n > 0: n >>= 1 res ^= n return res n = 4 print(binaryConverter(n)) # This code is contributed by sshrey47
C#
using System;
public class GFG {
static int binaryConverter(int n)
{
int res = n;
while (n > 0) {
n >>= 1;
res ^= n;
}
return res;
}
static public void Main()
{
int n = 4;
Console.WriteLine(binaryConverter(n));
}
}
// This code is contributed by sshrey47
Javascript
<script>
// Javascript program for above approach
function binaryConverter(n)
{
let res = n;
while (n > 0)
{
n >>= 1;
res ^= n;
}
return res;
}
let n = 4;
// Function call
document.write(binaryConverter(n));
// This code is contributed by mukesh07.
</script>
Producción
7
Complejidad de tiempo: O(log(n))
Espacio Auxiliar: O(1)
Este artículo es una contribución de Utkarsh Trivedi. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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