Что означает (число и -число) в битовом программировании?

Эти две функции представляют собой модифицированную реализацию структуры данных Двоичное индексное дерево (дерево Фенвика).
Вот две картинки в дополнение к ответу MikeCAT, показывающие, как переменная i обновляется для разных значений.

Функция get:
Предположим, что max значение ввода в функции равно 15 для простоты представления.

Узел с номером t на нем представляет tree[t] в массиве деревьев.
Если вы вызываете функцию get для i, возвращаемое значение представляет собой сумму tree[i ] плюс сумма всех элементов массива tree, индекс которых в массиве является родителем i на картинке, кроме нуля.
Вот некоторые Примеры:

get(15) = tree[15] + tree[14] + tree[12] + tree[8]
get(14) = tree[14] + tree[12] + tree[8]
get(13) = tree[13] + tree[12] + tree[8]
get(12) = tree[12] + tree[8]
get(11) = tree[11] + tree[10] + tree[8]
get(10) = tree[10] + tree[8]
get(9) = tree[9] + tree[8]
get(8) = tree[8]
get(7) = tree[7] + tree[6] + tree[4]
get(6) = tree[6] + tree[4]
get(5) = tree[5] + tree[4]
get(4) = tree[4]
get(3) = tree[3] + tree[2]
get(2) = tree[2]

Числа на метках узлов на приведенном выше рисунке обладают тем свойством, что родительским элементом каждого узла является эта метка узла за вычетом наименее значимой 1 (очень хорошо объяснено в ответе @MikeCAT)
Функция обновления:
Для простоты картины предположим, что максимальная длина массива tree равна 16.
Функция update немного сложнее.

Добавляет val к tree[i] и ко всем элементам tree, которые их индекс является родительским для узла с меткой i на картинке.

update(16, val) --> tree[16] += val;
update(15, val) --> tree[15] += val, tree[16] += val;
update(14, val) --> tree[14] += val, tree[16] += val;
update(13, val) --> tree[13] += val, tree[14] += val; tree[16] += val;
update(12, val) --> tree[12] += val, tree[16] += val;
update(11, val) --> tree[11] += val, tree[12] += val, tree[16] += val;
update(10, val) --> tree[10] += val, tree[12] += val, tree[16] += val;
update(9, val)  --> tree[9] += val, tree[10] += val, tree[12] += val, tree[16] += val;
update(8, val)  --> tree[8] += val, tree[16] += val;
update(7, val)  --> tree[7] += val, tree[8] += val, tree[16] += val;
update(6, val)  --> tree[6] += val, tree[8] += val, tree[16] += val;
update(5, val)  --> tree[5] += val, tree[6] += val, tree[8] += val, tree[16] += val;
update(4, val)  --> tree[4] += val, tree[8] += val, tree[16] += val;
update(3, val)  --> tree[3] += val, tree[4] += val, tree[8] += val, tree[16] += val;
update(2, val)  --> tree[2] += val, tree[4] += val, tree[8] += val, tree[16] += val;
update(1, val)  --> tree[1] += val, tree[2] += val, tree[4] += val, tree[8] += val, tree[16] += val;

Позвольте мне предположить, что отрицательное значение представлено с использованием дополнения до двух. В этом случае -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).

На случай, если кому-то понадобится и более общее доказательство,

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

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

• х & -х = (введите)
• a10^k & -(a10^k) = (по определению отрицания)
• a10^k & ~(a10^k) + 1 = (применить инверсию)
• a10^k & ~a01^k + 1 = (добавить 1)
• a10^k & ~a10^k = (И между чем-то и его инверсией)
• 0^в10^к

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

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