二进制码约束计数集问题的高效求解方法问询

Problem Definition #

Given a binary code of length l (where l % t == 0), split it into groups of t bits each. The result is the number of groups that contain at least one 1 bit.
Example: For the binary code 010 110 000 and t=3, the result is 2. The 000 group has no 1s, while 010 and 110 each have at least one 1, so each contributes 1 to the total.

My Question #

How can I solve this efficiently without iterating through each t-bit group (i.e., avoiding linear time complexity relative to the code length)?

Traditional bit-counting problems (like counting total 1s in a binary number) have constant-time algorithms such as the MIT HAKMEM Count, which uses fixed masks and shift operations. However, these don't apply to this problem. If we can assume a maximum length for the input binary code, are there any tricks to solve this?

Solution #

Great question! Let's break this down based on whether t is a power of two, and how we can leverage fixed-length assumptions to optimize for constant-time performance.

Case 1: t is a Power of Two #

If t equals 2^k (e.g., 2, 4, 8, 16), we can collapse each t-bit group into a single indicator bit using bitwise operations, then count those bits with a standard constant-time bit-counting algorithm:

1. Collapse groups: For t=4 (2^2), shift the number right by 2 bits and OR it with the original—this merges the top 2 bits of each 4-bit group with the bottom 2. Shift right by 1 bit and OR again, and each group will be collapsed to a single bit (1 if any original bit in the group was 1, 0 otherwise).
2. Extract indicators: Use a mask to isolate only the bits representing each group's result (e.g., every 4th bit for t=4).
3. Count bits: Run a constant-time bit-count (like HAKMEM or CPU-specific instructions like __builtin_popcount) on the filtered mask.

Case 2: t is Not a Power of Two #

This is trickier, but a fixed maximum input length lets us precompute operations to avoid linear traversal. Here's the core trick:

1. Binary lifting OR shifts: Successively OR the number with itself shifted by t, 2t, 4t, etc., until we've covered all groups. This propagates any 1 bit from a group to all lower groups, ensuring that each original group with a 1 will leave a trace in the first t bits (or a dedicated indicator position).
2. Group indicator mask: Precompute a mask with exactly one bit set per group (e.g., the highest bit of each t-bit block). AND this mask with the OR-ed result to get a bitmask where each 1 represents a non-zero group.
3. Count bits: Use a constant-time bit-count on the resulting mask to get the final count.

For your example (0b010110000, t=3, max length 9):

• Shift by 3 bits: 0b000010110, OR with original gives 0b010110110
• Shift again by 3 bits: 0b00010110, OR with the result gives 0b010110110
• AND with precomputed mask 0b100100100 gives 0b000100100
• Counting 1s here gives 2, which matches the expected result.

Fixed Maximum Length Advantage #

If you know the maximum input length L in advance, you can precompute all shifts and masks once. This makes every query run in constant time, regardless of the actual input length (as long as it's ≤ L and divisible by t). For example, if L=63 and t=3, you only need 5 shifts (3, 6, 12, 24, 48) to cover all 21 groups.

Edge Cases #

• All groups are zero: The result mask will be 0, so the count is 0.
• All groups have at least one 1: The result mask will have N bits set (N = L/t), so the count is N.
• t equals L: The result is 1 if the input is non-zero, 0 otherwise—this works since no shifts are needed, and the mask isolates the only group's indicator bit.

Example Implementation (C-like) #

#include <stdint.h>
#include <stdio.h>

// Assume max length is 24 bits, t=3 (8 total groups)
#define MAX_LEN 24
#define T 3
#define GROUP_COUNT (MAX_LEN / T)

// Precomputed binary lifting shifts
const int shifts[] = {3, 6, 12};
const int shift_count = sizeof(shifts)/sizeof(shifts[0]);

// Precomputed mask: 1 bit set per group (highest bit of each 3-bit block)
const uint32_t GROUP_INDICATOR_MASK = 0b100100100100100100100100;

uint32_t count_non_zero_groups(uint32_t x) {
    uint32_t temp = x;
    for (int i = 0; i < shift_count; i++) {
        temp |= temp >> shifts[i];
    }
    uint32_t result_mask = temp & GROUP_INDICATOR_MASK;
    // Use CPU-native constant-time bit count
    return __builtin_popcount(result_mask);
}

int main() {
    // Example input: 010 110 000 (binary) = 176 decimal
    uint32_t input = 176;
    printf("Result: %u\n", count_non_zero_groups(input)); // Output: 2
    return 0;
}

内容的提问来源于stack exchange，提问作者Rise of Kingdom