Gray code: Difference between revisions
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.
(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:
{{trans|C}}
<syntaxhighlight lang="java">
import java.math.BigInteger;
public class Gray {
public static long grayEncode(long n){
return n ^ ( n >>> 1 );
}
public static long grayDecode(long n) {
long p = n;
while ( ( n >>>= 1 ) != 0 ) {
p ^= n;
}
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){
System.out.println("i\tBinary\tGray\tGray2\tDecoded");
System.out.println("=======================================");
for ( int i = 0; i < 32; i++ ) {
System.out.print(i + "\t");
System.out.print(Integer.toBinaryString(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();
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>
{{ out }}
<pre>
i Binary Gray Gray2 Decoded
=======================================
0 0 0 0 0
1 1 1 1 1
2 10 11 11 2
3 11 10 10 3
4 100 110 110 4
5 101 111 111 5
6 110 101 101 6
7 111 100 100 7
8 1000 1100 1100 8
9 1001 1101 1101 9
10 1010 1111 1111 10
11 1011 1110 1110 11
12 1100 1010 1010 12
13 1101 1011 1011 13
14 1110 1001 1001 14
15 1111 1000 1000 15
16 10000 11000 11000 16
17 10001 11001 11001 17
18 10010 11011 11011 18
19 10011 11010 11010 19
20 10100 11110 11110 20
21 10101 11111 11111 21
22 10110 11101 11101 22
23 10111 11100 11100 23
24 11000 10100 10100 24
25 11001 10101 10101 25
26 11010 10111 10111 26
27 11011 10110 10110 27
28 11100 10010 10010 28
29 11101 10011 10011 29
30 11110 10001 10001 30
31 11111 10000 10000 31
test decimal = 1000000000012345678901234567890
gray code decimal = 856880362488978442236330020795
gray code binary = 1010110100001011101011010010101110001000100100101101010111001100110010111110100100001000111110111011
decoded decimal = 1000000000012345678901234567890
decoded2 decimal = 1000000000012345678901234567890
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}}==
| |||