Perform logical AND operation on multiple BigInteger Values in lists Java

Question

I'm trying to develop an efficient method to perform logical AND operation among several BigInteger values. For example, let us consider the snippet below:

public static void main(String[] args) {
    List<BigInteger> a = Arrays.asList(new BigInteger("1000",2), new BigInteger("101",2), new BigInteger("111",2));
    List<BigInteger> b = Arrays.asList(new BigInteger("10",2), new BigInteger("10110",2), new BigInteger("10011",2));
    List<BigInteger> c = Arrays.asList(new BigInteger("1",2), new BigInteger("10110",2), new BigInteger("11110",2));

    List<BigInteger> dd = IntStream.range(0, a.size())
                              .mapToObj(i -> a.get(i).and(b.get(i)).and(c.get(i)))
                              .collect(Collectors.toList());
    
    System.out.println(dd);
    //OUTPUT = [0, 4, 2]
}

However, the problem of this solution is the static number of values accepted by the map function. Let us suppose to consider an ArrayList containing several lists (also more than 3), how can I change the previous solution?

public static void main(String[] args) {
    List<BigInteger> a = Arrays.asList(new BigInteger("1000",2), new BigInteger("101",2), new BigInteger("111",2));
    List<BigInteger> b = Arrays.asList(new BigInteger("10",2), new BigInteger("10110",2), new BigInteger("10011",2));
    List<BigInteger> c = Arrays.asList(new BigInteger("1",2), new BigInteger("10110",2), new BigInteger("11110",2));
    ArrayList<List<BigInteger>> collection = new ArrayList<List<BigInteger>>();
    collection.add(a);
    collection.add(b);
    collection.add(c);
    List<BigInteger> dd = null;
    //......
    System.out.println(dd);
}

Notice that, I've decided to choose adopting stream.map() since the number of the BigInteger values in the lists could be large (thousands of values) and I would like to exploit parallelStream() to perform this operation. However, I accept any advice to do this efficiently.

It seems like you may benefit from BitSet rather than BigInteger. — Stanislav Bashkyrtsev, May 15 '21 at 14:46

BeUndead · Accepted Answer · 2021-05-18T19:39:22.513

If I understand what you're trying to do correctly, then this is what the reduce method of a Stream is for.

For example, the following should work:

final List<BigInteger> result = IntStream.range(0, a.size())
    .mapToObj(i -> collection.stream()
        .map(l -> l.get(i)) // Map to the i'th element of all streams.

        // This line is the trick.  It effectively performs '&' on all elements
        // in the mapped stream.  The first argument is the 'identity' element
        // of '&'-ing, which is a binary 11111...
        // -1 Behaves like this (although I have no idea how it works for
        // BigInteger, it seems to give the right values for the things you've
        // given as examples).
        .reduce(BigInteger.ZERO.subtract(BigInteger.ONE), BigInteger::and))
    .collect(Collectors.toList());

Note: if you're looking for efficiency here (and it really is important to your use case) then consider if you need BigInteger. Ignoring sign (since you're doing bitwise operations) long arrays would give you 64 bits, which easily covers everything you've given in the example (and most numbers in common use-cases) and would be much faster.

BeUndead · Answer 2 · 2021-05-27T01:22:10.940

Alternative answer inspired by Stanislav Bashkyrtsev's comment, which uses BitSets instead.

public static void main(String[] args) {
    final List<BitSet> a = Arrays.asList(
            BitSet.valueOf(new long[] {0b1000L}),
            BitSet.valueOf(new long[] {0b101L}),
            BitSet.valueOf(new long[] {0b111L})
    );
    final List<BitSet> b = Arrays.asList(
            BitSet.valueOf(new long[] {0b10L}),
            BitSet.valueOf(new long[] {0b1_0110L}),
            BitSet.valueOf(new long[] {0b1_0011L})
    );
    final List<BitSet> c = Arrays.asList(
            BitSet.valueOf(new long[] {0b1L}),
            BitSet.valueOf(new long[] {0b1_0110L}),
            BitSet.valueOf(new long[] {0b1_1110L})
    );

    final List<List<BitSet>> bitSets = Arrays.asList(a, b, c);

    final List<BitSet> results = IntStream.range(0, a.size())
        .mapToObj(i -> bitSets.stream().map(l -> l.get(i))

            // First argument of reduce is identity element, it needs
            // to be a BitSet with at least as many bits as any input
            // ones which are all set.  In this case, 64 bits are
            // used, initialised by a long.  If you have /more/ bits
            // needed, then create one with new BitSet(bitCount);
            // and then set all bits.
            .reduce(BitSet.valueOf(new long[] {0xFFFF_FFFF_FFFF_FFFFL}), (_0, _1) -> {

                // Or used to copy the first element into a new
                // BitSet.
                // No need to copy  here if you don't mind
                // modifying the above Lists.
                final BitSet tmp = BitSet.valueOf(new long[] {});
                tmp.or(_0);

                tmp.and(_1);
                return tmp;
            }))
        .collect(Collectors.toList());

    results.forEach(bs -> System.out.println(convert(bs)));
}

public static long convert(final BitSet bits) {
    long value = 0L;
    for (int i = bits.nextSetBit(0); i >= 0; i = bits.nextSetBit(i + 1)) {
        value += bits.get(i) ? (1L << i) : 0L;
    }
    return value;
}

Where the convert method was taken and slightly modified from this answer.

I'll try to also consider BitSet! Thanks! – Stefano May 16 '21 at 10:33 — Stefano, May 16 '21 at 10:33

Shadab · Answer 3 · 2021-05-15T15:01:54.630

1

You could try something like this

    List<BigInteger> dd = IntStream.range(0, a.size())
      .mapToObj(i -> 
        collection.stream()
            .map(col -> col.get(i))
            .reduce(BigInteger::and)
            .get())
      .collect(Collectors.toList());

edited May 15 '21 at 15:01

answered May 15 '21 at 14:22

Shadab

1,297
6
9

Perform logical AND operation on multiple BigInteger Values in lists Java

3 Answers3