Java 从 BigInteger 到 BitSet 再返回

Question

在 Java 8 中，下面的代码将整数 3 转换为位集并打印 {0, 1} 意味着 3 的位表示在位置 0 和1 即 11.

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

我有兴趣将具有较大值的 BigInteger 或 long 转换为相应的 BitSet 然后返回 - 具有 BitSet对象（位表示）将其转换为BigInteger（long）。我也想知道对于整数的各种值，哪种表示占用更多的内存？

Answer 1

您可以对这些使用 BigInteger.toByteArray() and 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[]) to convert the array of bytes into a BigInteger and the 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-complement 表示法。因此对于负数，它会产生额外的。而一个 2^64-1 将需要超过 64 位来表示。这也适用于 big endian。（请参阅下面修改后的答案）。

编辑：但是这种方法有一个问题：如果有尾零，程序不会考虑这些。这可能很重要，因为它们是表示的一部分。您可以通过添加拖尾位来解决此问题：

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 是大端，而 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代替。

Java 从 BigInteger 到 BitSet 再返回

Java from BigInteger to BitSet and back

java

bitset

bigint