How to Efficiently Count Set Bits at a Position or Lower in a Bitset?

Efficiently Counting Set Bits at a Position or Lower

Problem Statement:

Given a std::bitset<64> with arbitrary bit values and a bit position X (0-63), determine the most efficient way to count bits at position X or lower, or return 0 if the bit at X is not set.

Optimized Solution:

The following C code generates highly optimized x86 ASM that efficiently counts set bits within a specified range:

#include <bitset>

int popcount_subset(std::bitset<64> bits, int pos) {
    int high_bits_to_eliminate = 63 - pos;
    bits <<= high_bits_to_eliminate & 63; // Shift to place desired bits at the top
    return (bits[63] ? ~0ULL : 0) & bits.count(); // Broadcast high bit or return 0, then popcount
}

Implementation Details:

1. Shift Operation: The bitset is shifted left by 63 - pos to align the desired bits with the top of a 64-bit register. This eliminates unwanted bits from the count.
2. Bit Broadcast: The high bit of the shifted bitset is broadcast to all bit positions using an arithmetic right shift. This creates a mask where all bits are set if the high bit is set (i.e., the bit at pos is set) and all bits are clear otherwise.
3. Conditional Popcount: The AND operation combines the bitset with the mask. If the bit at pos is set, the mask will be ~0ULL, resulting in the original popcount. Otherwise, the mask will be 0, resulting in a popcount of 0.
4. Optimal ASM: This code produces efficient x86 ASM on 64-bit architectures, leveraging hardware popcount instructions and bit broadcast techniques.

Benefits:

• Efficient for counting set bits within a specified range.
• Works for arbitrary bitset sizes by adjusting constants accordingly.
• Generates highly optimized ASM on many architectures, including x86-64 and ARM64.
• Handles cases where pos exceeds the bitset size without undefined behavior.

The above is the detailed content of How to Efficiently Count Set Bits at a Position or Lower in a Bitset?. For more information, please follow other related articles on the PHP Chinese website!