Что (номер-количество) означает в Разрядном программировании? [дубликат]

этот вопрос уже есть ответ здесь:

  • значение (число) & (- число) 3 ответы

например:

int get(int i) {
    int res = 0;
    while (i) {
        res = (res + tree[i]) % MOD;
        i -= ( (i) & (-i) );
    }
    return res;
}

функция обновления дерева:

void update(int i, int val) {
    while (i <= m) {
        tree[i] = (tree[i] + val) % MOD;
        i += ( (i) & (-i) );
    }
}

не могли бы вы объяснить, что они делают в коде с помощью ( (i) & (-i) )?

3 64
c++ bit-fields bitwise-and fenwick-tree

3 ответа:

эти две функции являются модифицированной реализацией a дерево двоичных индексов (дерево Фенвика) структуры данных.
вот две фотографии, чтобы дополнить ответ MikeCAT, показывающий, как Я обновления переменных для разных значений.

функция "get":
Для предположим, что максимальное значение в функции input in равно 15 для простоты представления.
enter image description here
узел с номером t в этом представляет дерево[t] в массиве дерева.
Если вы позвоните get

11

позвольте мне предположить, что отрицательное значение представлено с помощью дополнения two. В этом случае -i можно вычислить как (~i)+1 (переверните биты, затем добавьте 1).

например, позвольте мне рассмотреть i = 44. Затем, в двоичном формате,

i           = 0000 0000 0000 0000 0000 0000 0010 1100
~i          = 1111 1111 1111 1111 1111 1111 1101 0011
-i = (~i)+1 = 1111 1111 1111 1111 1111 1111 1101 0100
(i) & (-i)  = 0000 0000 0000 0000 0000 0000 0000 0100

как вы видите, наименьший бит, который равен 1, может быть вычислен с помощью (i) & (-i).

85

в случае, если кто-то хочет более общее доказательство,

предположим x имеет формат a10k (здесь имеется в виду некоторая битовая строка a, за которой следует 1, а затем K нулей).

-x это (по определению) то же самое как ~x + 1, Так что

  • x & - x = (заполнить)
  • a10k & - (a10k) = (def. отрицания)
  • a10k & ~(a10k) + 1 = (применить инверсия)
  • a10k & ~a01k + 1 = (добавить 1)
  • a10k & ~a10k = (и между чем-то и его инверсии)
  • 0 w10k

таким образом, у нас остается только один самый правый 1, который мы предполагали, существовал.

предположение о форме x упускает случай, что x = 0, в этом случае результат, очевидно, все еще нуль.

21