如何列出一个计数的数字？

Question

快速列出 Java BigInteger 的 1 的选项有哪些？我们可以假设 BigInteger 是正数，但它可能是一个相当大的 Java BigInteger，其中 1 的分布很少。尽管如此，我们还是希望尽快找到它们。我想为 Java BigInteger 的 1 的位位置设置一个枚举器或迭代器。

Answer 1

使用 .toString(radix) 方法。像这样：bigInteger.toString(2) 然后检查字符串中的那些

Answer 2

您可以使用 BigInteger 的 getLowestSetBit and clearBit 方法。例如，打印出来：

public static final void printOneIndexes(BigInteger n) {
    while (!n.equals(BigInteger.ZERO)) {
        int i = n.getLowestSetBit();
        System.out.printf(" %d", i);
        n = n.clearBit(i);
    }
}

Answer 3

可以使用 getLowestSetBit()，但测试表明以下速度大约是其 3-4 倍：

public static final void printOneIndexes(BigInteger n)
{
    for (int i = 0; i < n.bitLength(); i++)
    {
        if (n.testBit(i))
            System.out.printf(" %d", i);
    }
}

当然，如果去掉打印，并将结果存储在列表中，速度会更快。

我用只设置了几个位的 BigInteger 测试了它，创建者：

public static BigInteger makeSparseInt()
{
    BigInteger b = BigInteger.ZERO.setBit(1000000);

    Random r = new Random();

    for (int i = 0; i < 100; i++)
    {
        b = b.setBit(r.nextInt(1000000));
    }
    return b;
}

如何列出一个计数的数字？

How to list the ones of a counting number?

java

biginteger