Java из BigInteger в BitSet и обратно

Question

В Java 8 ниже коде преобразует число 3 в BITSET и печатает {0, 1} означает битовое представление 3 имеет те в положениях 0 и 1 что 11.

System.out.println(BitSet.valueOf(new long[]{3})); 

Я заинтересован в преобразовании BigInteger или long с большим значением, скажем, 10000000 в соответствующий BitSet, а затем обратно - имея BitSet объект (представление битов) преобразовать его в BigInteger (long). Мне также интересно, какое представление занимает больше памяти для различных значений целых чисел?

Answer 1

Вы можете использовать BigInteger.toByteArray() и BitSet.toByteArray() для них:

BigInteger bi = new BigInteger("31415926535"); 
bi = bi.multiply(new BigInteger("271828")); 
System.out.println(bi); 
BitSet bs = BitSet.valueOf(bi.toByteArray()); 
System.out.println(bs); 
BigInteger bi2 = new BigInteger(bs.toByteArray()); 
System.out.println(bi2); 

Вы можете использовать конструктор BigInteger(byte[]) преобразовать массив байтов в BigInteger и BitSet.valueOf(byte[]) для преобразования данных в требуемые значения.

Для получения данного кода, он выводит:

8539728478155980 
{1, 2, 3, 4, 9, 10, 12, 14, 17, 18, 20, 22, 23, 25, 27, 28, 29, 30, 32, 33, 35, 37, 38, 42, 44, 45, 50, 51, 54, 55} 
8539728478155980 

Обратите внимание, что используется 2-дополнение обозначения. Таким образом, для отрицательных чисел он будет генерировать дополнительные. А для 2^64-1 потребуется более 64 бит. Это также работает с big endian. (см. измененный ответ ниже).

EDIT: есть одна проблема с этим подходом: если есть хвосты хвоста, они не учитываются программой. Это может быть важно, потому что они являются частью представления. Вы можете решить эту проблему, добавив хвостохранилища немного:

public static BitSet convertTo (BigInteger bi) { 
    byte[] bia = bi.toByteArray(); 
    int l = bia.length; 
    byte[] bsa = new byte[l+1]; 
    System.arraycopy(bia,0,bsa,0,l); 
    bsa[l] = 0x01; 
    return BitSet.valueOf(bsa); 
} 

public static BigInteger convertFrom (BitSet bs) { 
    byte[] bsa = bs.toByteArray(); 
    int l = bsa.length-0x01; 
    byte[] bia = new byte[l]; 
    System.arraycopy(bsa,0,bia,0,l); 
    return new BigInteger(bia); 
} 

И назвать его:

BigInteger bi = new BigInteger("20000000"); 
System.out.println(bi); 

BitSet bs = convertTo(bi); 
System.out.println(bs); 

BigInteger bi2 = convertFrom(bs); 
System.out.println(bi2); 

об использовании памяти

В целом оба метода будут использовать примерно такое же количество бит. Для первой реализации (без маркера размера и, следовательно, ошибок) возможно, что иногда подход BitSet будет использовать один байт меньше, чем подход BigInteger. С маркером размера (второй подход) это наоборот: в общем случае BitSet будет использовать всегда один дополнительный байт, за исключением некоторых редких случаев.

Answer 2

Как BigInteger является big-endian, в то время как BitSet является малорисковым, байты будут отменены при попытке конвертировать напрямую из одного в другое через toByteArray(). Самым простым решением было бы просто реверс их снова:

/** 
* Converts from BigInteger to BitSet. The BigInteger must be non-negative, 
* otherwise an IllegalArgumentException is thrown. 
*/ 
public static BitSet toBitSet(BigInteger val) { 
    if(val.signum() < 0) 
     throw new IllegalArgumentException("Negative value: " + val); 
    return BitSet.valueOf(reverse(val.toByteArray())); 
} 
/** 
* Converts from BitSet to BigInteger. 
*/ 
public static BigInteger toBigInteger(BitSet val) { 
    return new BigInteger(1, reverse(val.toByteArray())); 
} 
/** 
* Reverses and returns the specified byte array. 
*/ 
private static byte[] reverse(byte[] bytes) { 
    for(int i = 0; i < bytes.length/2; i++) { 
     byte temp = bytes[i]; 
     bytes[i] = bytes[bytes.length-i-1]; 
     bytes[bytes.length-i-1] = temp; 
    } 
    return bytes; 
} 

Кстати, если вы заинтересованы только в битовых индексов, вы можете использовать вместо BigInteger#testBit.