寻找快速的方法来转换布尔[]以格雷码至BigInteger和反之亦然的Java

Question

对于GA需要两种方法：

BigInteger greyToBigInteger(boolean[]){...} 

和

boolean[] bigIntegerToGrey(BigInteger){...} 

例如：

15 ---> {true,false,false,false} 
and 
{true,false,false,false} --> 15 

我不知道，如何让这非常快。要转换的最大数量是10^1125，所以对于一个数字，它的工作时间超过5分钟，如果我这样做的话，就像维基百科的例子。

Answer 1

我写了这段代码，它运行得非常快，没有任何特别的技巧 - 我的笔记本电脑上的它需要少于2毫秒将小于或等于10^1125的给定数字转换为灰背：

import java.math.BigInteger; 
import java.util.Random; 

public class GrayCode { 

    public static void main(String[] args) { 

     // actually 10^1125 is a number with max length of 3738 bits 
     int bitLength = new BigInteger("10").pow(1125).bitLength(); 
     System.out.println("10^1125 is a number with max bit length = " + bitLength); 
     new GrayCode().test(bitLength); 
    } 

    private void test(int bitLength) { 
     long totalTime = 0; 
     long numberOfTests = 1000; 

     for (int n = 0; n < numberOfTests; n++) { 
      // We don't include time needed for generation of a number 
      BigInteger binary = generateBigInteger(bitLength); 

      // here we start measuring execution time of single conversion 
      long start = System.currentTimeMillis(); 

      // The conversion to gray and back 
      boolean[] gray = bigIntegerToGrey(binary); 
      BigInteger back = grayToBigInteger(gray); 

      // we sum up the conversion times to totalTime per this test suite 
      totalTime += System.currentTimeMillis() - start; 
     } 
     System.out.println("We have run a "+numberOfTests+" tests, for a random numbers of "+bitLength+" bit length to convert to gray code and back to binary"); 
     System.out.println("The total execution time of this test was "+totalTime+" milliseconds, giving average convesion time of " + totalTime/1000d + " ms per single test "); 

    } 

    private BigInteger grayToBigInteger(boolean[] booleanGray) { 
     BigInteger input = booleanToBigInteger(booleanGray); 
     return grayToBinary(input); 
    } 

    private boolean[] bigIntegerToGrey(BigInteger binary) { 
     BigInteger gray = binaryToGray(binary); 
     return bigIntegerToBooleanArray(gray); 
    } 

    public boolean[] bigIntegerToBooleanArray(BigInteger number) { 
     char[] binary = number.toString(2).toCharArray(); 
     boolean[] binaryBoolean = new boolean[binary.length]; 
     for (int n = 0; n < binary.length; n++) { 
      if (binary[n] == '1') { 
       binaryBoolean[n] = true; 
      } 
     } 
     return binaryBoolean; 
    } 

    private BigInteger generateBigInteger(int numBits) { 
     Random rnd = new Random(); 
     BigInteger number = new BigInteger(numBits, rnd); 
     return number; 
    } 

    public BigInteger booleanToBigInteger(boolean[] binary) { 
     StringBuilder sb = new StringBuilder(); 
     for (boolean b : binary) { 
      sb.append(b ? '1' : '0'); 
     } 
     return new BigInteger(sb.toString(), 2); 
    } 

    public BigInteger binaryToGray(BigInteger num) { 
     return num.xor(num.shiftRight(1)); 
    } 

    public BigInteger grayToBinary(BigInteger num) { 
     BigInteger mask; 
     for (mask = num.shiftRight(1); mask.compareTo(BigInteger.ZERO) != 0; mask = mask.shiftRight(1)) { 
      num = num.xor(mask); 
     } 
     return num; 
    } 

} 

结果：

10^1125 is a number with max bit length = 3738 
We have run a 1000 tests, for a number of 3738 bit length to convert to gray code and back to binary 
The total execution time of this test was 1828 milliseconds, giving average convesion time of 1.828 ms per single test