jpountz commented on code in PR #14273: URL: https://github.com/apache/lucene/pull/14273#discussion_r2018661757
########## lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java: ########## @@ -204,6 +205,40 @@ public int cardinality() { return Math.toIntExact(tot); } + /** + * Return the number of set bits between indexes {@code from} inclusive and {@code to} exclusive. + */ + public int cardinality(int from, int to) { + Objects.checkFromToIndex(from, to, length()); + + int cardinality = 0; + + // First, align `from` with a word start, ie. a multiple of Long.SIZE (64) + if ((from & 0x3F) != 0) { + long bits = this.bits[from >> 6] >>> from; + int numBitsTilNextWord = -from & 0x3F; + if (to - from < numBitsTilNextWord) { + bits &= (1L << (to - from)) - 1L; + return Long.bitCount(bits); + } + cardinality += Long.bitCount(bits); + from += numBitsTilNextWord; + assert (from & 0x3F) == 0; + } + + for (int i = from >> 6, end = to >> 6; i < end; ++i) { + cardinality += Long.bitCount(bits[i]); + } + + // Now handle bits between the last complete word and to + if ((to & 0x3F) != 0) { + long bits = this.bits[to >> 6] << -to; Review Comment: You are right. We need the low "to % 64" bits of `bits[to >> 6]`. `x << -to` is nice because it requires fewer instructions but it also moves bits to a different index. This makes iterating over set bits slightly more cumbersome, but doesn't matter for counting bits. Hence why `forEach` applies a mask instead. I haven't checked actual performance, I suspect that it doesn't matter in practice. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org