Gray code: Difference between revisions
Content added Content deleted
(Added solution for EDSAC) |
(An existing post had a warning message on a yellow background stating that the code had not been fully tested. This post adds the missing tests while altering the existing post as little as possible.) |
||
Line 3,151: | Line 3,151: | ||
{{trans|C}} |
{{trans|C}} |
||
<syntaxhighlight lang="java"> |
<syntaxhighlight lang="java"> |
||
import java.math.BigInteger; |
|||
public class Gray { |
public class Gray { |
||
public static long grayEncode(long n){ |
public static long grayEncode(long n){ |
||
return n ^ (n >>> 1); |
return n ^ ( n >>> 1 ); |
||
} |
} |
||
public static long grayDecode(long n) { |
public static long grayDecode(long n) { |
||
long p = n; |
long p = n; |
||
while ((n >>>= 1) != 0) |
while ( ( n >>>= 1 ) != 0 ) { |
||
p ^= n; |
p ^= n; |
||
} |
|||
return p; |
return p; |
||
} |
|||
public static BigInteger grayEncode(BigInteger n) { |
|||
return n.xor(n.shiftRight(1)); |
|||
} |
} |
||
public static BigInteger grayDecode(BigInteger n) { |
|||
BigInteger p = n; |
|||
while ( ( n = n.shiftRight(1) ).signum() != 0 ) { |
|||
p = p.xor(n); |
|||
} |
|||
return p; |
|||
} |
|||
/** |
|||
* An alternative version of grayDecode, |
|||
* less efficient, but demonstrates the principal of gray decoding. |
|||
*/ |
|||
public static BigInteger grayDecode2(BigInteger n) { |
|||
String nBits = n.toString(2); |
|||
String result = nBits.substring(0, 1); |
|||
for ( int i = 1; i < nBits.length(); i++ ) { |
|||
// bin[i] = gray[i] ^ bin[i-1] |
|||
// XOR using characters |
|||
result += nBits.charAt(i) != result.charAt(i - 1) ? "1" : "0"; |
|||
} |
|||
return new BigInteger(result, 2); |
|||
} |
|||
/** |
|||
* An alternative version of grayEncode, |
|||
* less efficient, but demonstrates the principal of gray encoding. |
|||
*/ |
|||
public static long grayEncode2(long n) { |
|||
long result = 0; |
|||
for ( int exp = 0; n > 0; n >>= 1, exp++ ) { |
|||
long nextHighestBit = ( n >> 1 ) & 1; |
|||
if ( nextHighestBit == 1 ) { |
|||
result += ( ( n & 1 ) == 0 ) ? ( 1 << exp ) : 0; // flip this bit |
|||
} else { |
|||
result += ( n & 1 ) * ( 1 << exp ); // don't flip this bit |
|||
} |
|||
} |
|||
return result; |
|||
} |
|||
public static void main(String[] args){ |
public static void main(String[] args){ |
||
System.out.println("i\tBinary\tGray\tDecoded"); |
System.out.println("i\tBinary\tGray\tGray2\tDecoded"); |
||
System.out.println("======================================="); |
|||
for(int i = -1; i < 32;i++){ |
|||
for ( int i = 0; i < 32; i++ ) { |
|||
System.out.print(i +"\t"); |
|||
System.out.print(i + "\t"); |
|||
System.out.print(Integer.toBinaryString(i) + "\t"); |
System.out.print(Integer.toBinaryString(i) + "\t"); |
||
System.out.print(Long.toBinaryString(grayEncode(i))+ "\t"); |
System.out.print(Long.toBinaryString(grayEncode(i)) + "\t"); |
||
System.out.print(Long.toBinaryString(grayEncode2(i)) + "\t"); |
|||
System.out.println(grayDecode(grayEncode(i))); |
System.out.println(grayDecode(grayEncode(i))); |
||
} |
|||
System.out.println(); |
|||
final BigInteger base = BigInteger.TEN.pow(30).add( new BigInteger("12345678901234567890") ); |
|||
for ( int i = 0; i < 5; i++ ) { |
|||
BigInteger test = base.add(BigInteger.valueOf(i)); |
|||
System.out.println("test decimal = " + test); |
|||
System.out.println("gray code decimal = " + grayEncode(test)); |
|||
System.out.println("gray code binary = " + grayEncode(test).toString(2)); |
|||
System.out.println("decoded decimal = " + grayDecode(grayEncode(test))); |
|||
System.out.println("decoded2 decimal = " + grayDecode2(grayEncode(test))); |
|||
System.out.println(); |
|||
} |
} |
||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
</syntaxhighlight> |
||
{{out}} |
{{ out }} |
||
<pre> |
<pre> |
||
i Binary Gray Decoded |
i Binary Gray Gray2 Decoded |
||
======================================= |
|||
-1 11111111111111111111111111111111 1000000000000000000000000000000000000000000000000000000000000000 -1 |
|||
0 0 0 0 |
0 0 0 0 0 |
||
1 1 1 1 |
1 1 1 1 1 |
||
2 10 11 2 |
2 10 11 11 2 |
||
3 11 10 3 |
3 11 10 10 3 |
||
4 100 110 4 |
4 100 110 110 4 |
||
5 101 111 5 |
5 101 111 111 5 |
||
6 110 101 6 |
6 110 101 101 6 |
||
7 111 100 7 |
7 111 100 100 7 |
||
8 1000 1100 8 |
8 1000 1100 1100 8 |
||
9 1001 1101 9 |
9 1001 1101 1101 9 |
||
10 1010 1111 10 |
10 1010 1111 1111 10 |
||
11 1011 1110 11 |
11 1011 1110 1110 11 |
||
12 1100 1010 12 |
12 1100 1010 1010 12 |
||
13 1101 1011 13 |
13 1101 1011 1011 13 |
||
14 1110 1001 14 |
14 1110 1001 1001 14 |
||
15 1111 1000 15 |
15 1111 1000 1000 15 |
||
16 10000 11000 16 |
16 10000 11000 11000 16 |
||
17 10001 11001 17 |
17 10001 11001 11001 17 |
||
18 10010 11011 18 |
18 10010 11011 11011 18 |
||
19 10011 11010 19 |
19 10011 11010 11010 19 |
||
20 10100 11110 20 |
20 10100 11110 11110 20 |
||
21 10101 11111 21 |
21 10101 11111 11111 21 |
||
22 10110 11101 22 |
22 10110 11101 11101 22 |
||
23 10111 11100 23 |
23 10111 11100 11100 23 |
||
24 11000 10100 24 |
24 11000 10100 10100 24 |
||
25 11001 10101 25 |
25 11001 10101 10101 25 |
||
26 11010 10111 26 |
26 11010 10111 10111 26 |
||
27 11011 10110 27 |
27 11011 10110 10110 27 |
||
28 11100 10010 28 |
28 11100 10010 10010 28 |
||
29 11101 10011 29 |
29 11101 10011 10011 29 |
||
30 11110 10001 30 |
30 11110 10001 10001 30 |
||
31 11111 10000 31 |
31 11111 10000 10000 31 |
||
</pre> |
|||
Here is an example encoding function that does it in a bit-by-bit, more human way: |
|||
<syntaxhighlight lang="java">public static long grayEncode(long n){ |
|||
long result = 0; |
|||
for(int exp = 0; n > 0; n /= 2, exp++){ |
|||
long nextHighestBit = (n >> 1) & 1; |
|||
if(nextHighestBit == 1){ |
|||
result += ((n & 1) == 0) ? (1 << exp) : 0; //flip the bit |
|||
}else{ |
|||
result += (n & 1) * (1 << exp); //"n & 1" is "this bit", don't flip it |
|||
} |
|||
} |
|||
return result; |
|||
}</syntaxhighlight> |
|||
This decoding function should work for gray codes of any size: |
|||
{{untested}} |
|||
<syntaxhighlight lang="java">public static BigInteger grayDecode(BigInteger n){ |
|||
String nBits = n.toString(2); |
|||
String result = nBits.substring(0, 1); |
|||
for(int i = 1; i < nBits.length(); i++){ |
|||
//bin[i] = gray[i] ^ bin[i-1] |
|||
test decimal = 1000000000012345678901234567890 |
|||
//XOR with characters |
|||
gray code decimal = 856880362488978442236330020795 |
|||
result += nBits.charAt(i) != result.charAt(i - 1) ? "1" : "0"; |
|||
gray code binary = 1010110100001011101011010010101110001000100100101101010111001100110010111110100100001000111110111011 |
|||
} |
|||
decoded decimal = 1000000000012345678901234567890 |
|||
return new BigInteger(result, 2); |
|||
decoded2 decimal = 1000000000012345678901234567890 |
|||
}</syntaxhighlight> |
|||
test decimal = 1000000000012345678901234567891 |
|||
gray code decimal = 856880362488978442236330020794 |
|||
gray code binary = 1010110100001011101011010010101110001000100100101101010111001100110010111110100100001000111110111010 |
|||
decoded decimal = 1000000000012345678901234567891 |
|||
decoded2 decimal = 1000000000012345678901234567891 |
|||
test decimal = 1000000000012345678901234567892 |
|||
gray code decimal = 856880362488978442236330020798 |
|||
gray code binary = 1010110100001011101011010010101110001000100100101101010111001100110010111110100100001000111110111110 |
|||
decoded decimal = 1000000000012345678901234567892 |
|||
decoded2 decimal = 1000000000012345678901234567892 |
|||
test decimal = 1000000000012345678901234567893 |
|||
gray code decimal = 856880362488978442236330020799 |
|||
gray code binary = 1010110100001011101011010010101110001000100100101101010111001100110010111110100100001000111110111111 |
|||
decoded decimal = 1000000000012345678901234567893 |
|||
decoded2 decimal = 1000000000012345678901234567893 |
|||
test decimal = 1000000000012345678901234567894 |
|||
gray code decimal = 856880362488978442236330020797 |
|||
gray code binary = 1010110100001011101011010010101110001000100100101101010111001100110010111110100100001000111110111101 |
|||
decoded decimal = 1000000000012345678901234567894 |
|||
decoded2 decimal = 1000000000012345678901234567894 |
|||
</pre> |
|||
=={{header|Javascript}}== |
=={{header|Javascript}}== |