java - 二进制代码的约束计数集

问题公式：给定长度为L的二进制代码，对于每一个T比特集（L%T＝0），如果存在至少一个值1位，则将结果加1。
我的问题是：如何有效地得到最终结果？
例如，我们有一个二进制代码010 110 000，t=3。最后的结果是2。因为对于000，没有值1的位对于110，存在至少一个值1位。结果加1。对于010，还存在一个值1的位。结果加1。因此，最终结果是2。
我的问题是如何有效地解决这个问题而不扫描每个T位，这导致时间复杂度与二进制代码的长度成线性关系。
对于计数集问题（计算二进制代码中有多少个1），有一些算法通过使用有限的掩码和移位操作（如MIT HAKMEM Count算法）来花费恒定的时间来解决它。
然而，传统的计数集问题的现有算法不能用于解决我的问题。
有人知道解决我问题的诀窍吗如果输入二进制代码使问题更容易解决，则可以假定其最大长度。

最佳答案

从comment：
然后，您可以假设对于这个问题，输入是64位整数的二进制代码。
这里有两种不同的方法。
第一次运行O（I/t）并通过测试所有0位的每组来工作。

public static int countSets(int setSize, long bits) {
    Long mask = (1L << setSize) - 1;
    int count = 0;
    for (long b = bits; b != 0; b >>>= setSize)
        if ((b & mask) != 0)
            count++;
    return count;
}

第二次运行o（log i），通过将集合的位折叠到集合的最右边，然后计算集合的位来工作。

public static int countSets(int setSize, int bitCount, long bits) {
    long b = bits, mask = 1;
    for (int i = 1; i < setSize; i++)
        b |= bits >>> i;
    for (int i = setSize; i < bitCount; i <<= 1)
        mask |= mask << i;
    return Long.bitCount(b & mask);
}

进一步解释
第一种方法为集合构建掩码，例如，使用t = 3，掩码为111。
然后，它一次将值右移t位，例如使用input = 010 110 000和t = 3，您将得到：

mask = 111
b = 010 110 000  ->  b & mask = 000  ->  don't count
b =     010 110  ->  b & mask = 110  ->  count
b =         010  ->  b & mask = 010  ->  count
result: 2

第二种方法首先将位合并到集合的最右边，例如使用input = 010 110 000和t = 3，可以得到：

bits      = 010 110 000
bits >> 1 = 001 011 000
bits >> 2 = 000 101 100
b (OR'd)  = 011 111 100

然后，它构建一个只检查最右边的位的掩码，然后应用掩码并计数位集：

mask     = 001 001 001
b & mask = 001 001 000
result: 2

关于java - 二进制代码的约束计数集，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50595969/