Ограниченные подсчеты на двоичных кодах

Question

Формулировка задачи: учитывая двоичный код длины l, для каждого установленного t бит (l% t = 0), если существует хотя бы один бит значения 1, мы добавляем 1 к результату.

Мой вопрос: как эффективно получить конечный результат?

Например, у нас есть двоичный код 010 110 000, а t = 3.Тогда конечный результат равен 2. Так как для 000 нет бита значения 1. Для 110 существует хотя бы один бит значения 1. Мы добавляем 1 к результату.Для 010 также существует один бит значения 1. Мы добавляем 1 к результату.Таким образом, конечный результат равен 2.

Мой вопрос заключается в том, как эффективно решить эту проблему, не сканируя каждый t бит, что вызывает временную сложность, линейную с длиной двоичного кода.

Для задачи счетного набора (вычислите, сколько единиц в двоичном коде), есть некоторые алгоритмы, которые требуют постоянного времени для ее решения, принимая ограниченное число операций маскирования и сдвига, таких как MIT HAKMEM Count алгоритм.

Однако существующие алгоритмы для традиционной задачи подсчета не могут быть использованы для решения моей проблемы.

Кто-нибудь знает некоторые хитрости для моих проблем?Вы можете принять максимальную длину входного двоичного кода, если это облегчает решение проблемы.

Answer 1

Из комментарий :

Тогда вы можете предположить, что для этой задачи вход представляет собой двоичный код 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