Java: Count number of bits set in a java.util.BitSet

Question

Any quick method to count the number of set bits in a BitSet other than the usual 'keep a counter' method?

score 44 · Accepted Answer · edited Jul 05 '17 at 01:09

44

The cardinality() method returns the number of set bits.

edited Jul 05 '17 at 01:09

mwfearnley

answered Feb 03 '11 at 06:52

pwc

3

If you were wondering how this is implemented: It does not keep an internal counter, it loops over the `long[]` that is used to hold the bits and calls `Long#bitCount` for each of them. – Thilo Feb 03 '11 at 07:03
1

under the covers it uses Long.bitCount(). On modern CPU's there is a CPU instruction for this, popcnt. In recent versions of Java, Long.bitCount() uses this instruction. Just use -XX:+UsePopCountInstruction to turn it on (this is the default in recent versions of Java) – Karl Mar 19 '17 at 23:04

score 3 · Answer 2 · answered Feb 03 '11 at 06:53

3

(Assuming you don't want to call cardinality())

int count = 0; 
for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
    count++;
}

answered Feb 03 '11 at 06:53

Ron

score 1 · Answer 3 · edited Jul 05 '17 at 00:51

1

BitSet B1 = new BitSet(3);
B1.set(0);
B1.cardinality();

Output:

edited Jul 05 '17 at 00:51

Pang

answered Jun 24 '17 at 03:54

Aditya Parmar

5

This doesn't really add much beyond the answer referring to this method posted 6 years ago. – Bernhard Barker Jun 24 '17 at 20:23
I disagree with @Dukeling. One - it uses BitSet's API. Two - it's one method call, not 4 lines with a loop. This is the correct answer IMO, previous answer is a brute force approach. – vacant78 May 18 '18 at 20:37
@vacant78 I was referring to [the other answer](https://stackoverflow.com/a/4883196/1711796), which references the same method, with a link to the docs and a brief explanation of what it does. – Bernhard Barker May 21 '18 at 07:44
@Dukeling - clearly, I had a bad moment there, unable to see the best (and highest voted) answer... my mistake. – vacant78 May 21 '18 at 10:47

3 Answers3