Бит-операция, используемая в цикле for

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

    void update(int i, int value, int array[], int n) {
        for(; i < n; i += ~i & (i + 1)) {
            array[i] += value;
        }
}

Я действительно не понимаю, что происходит в этом цикле, это какой-то трюк? Я нашел нечто похожее по названию деревьев Фенвика, но они немного отличаются от того, что у меня здесь.

Любые идеи, что означает этот цикл?

Также найдено следующее:

"Бит Hack # 9. Изолируйте самый правый 0-бит.

y = ~ x и (x + 1) "

Ответы

Ответ 1

Вы правы: бит-хак ~i & (i + 1) должен оценивать целое число, которое является двоичным 0, за исключением того, что соответствует самому правому нулевому биту i, который установлен в двоичный 1.

Итак, в конце каждого прохода цикла for он добавляет это значение себе. Поскольку соответствующий бит в i равен нулю, это влияет на его настройку, не затрагивая никаких других бит в i. Это будет строго увеличивать значение i на каждом проходе до тех пор, пока i не переполнится (или станет -1, если вы начали с i<0). В контексте вы, вероятно, можете ожидать, что он вызывается с помощью i>=0 и что i < n устанавливается завершающим циклом до того, как ваш индекс отключится от array.

Общая функция должна иметь эффект итерации через нулевые разряды исходного значения i от наименьшего значения до самого значительного, устанавливая их один за другим и увеличивая соответствующие элементы array.

Деревья Фенвика - это умный способ эффективно накапливать и запрашивать статистику; как вы говорите, их цикл обновления выглядит примерно так и обычно использует сопоставимый бит-хак. Существуют определенные способы выполнения такого рода бит-возиться, поэтому, конечно, возможно, что ваш исходный код обновляет дерево Fenwick или что-то сравнимое.

Ответ 2

Предположим, что справа налево у вас есть несколько бит, бит 0, а затем больше бит в x.

Если вы добавите x + 1, то все 1 справа будут изменены на 0, значение 0 будет изменено на 1, остальное останется неизменным. Например, xxxx011 + 1 = xxxx100.

В ~ x у вас есть то же количество 0 бит, 1 бит и обратные символы других бит. Побитовое и выдает 0 бит, один бит, а так как оставшиеся биты и имеют свое отрицание, эти биты равны 0.

Таким образом, результат ~ x и (x + 1) является числом с одним 1 битом, где x имеет самый правый нулевой бит.

Если вы добавите это значение в x, вы измените крайний правый 0 на 1. Таким образом, если вы это сделаете повторно, вы измените 0 бит в x на 1, справа налево.

Ответ 3

Функция update выполняет итерацию и устанавливает 0-бит i от самого левого нуля до самого нуля и добавляет value к элементу i th <<24 > .

Цикл for проверяет, меньше ли i n, если это так, ~i & (i + 1) будет целочисленным, имеет все двоичные 0, кроме самого правого бита (т.е. 1). Затем array[i] += value добавляет value к самому итерации.

Настройка i на 8, и повторение итераций может очистить вас.