Ce n' (nombre & nombre) signifie en peu de programmation?

Question

Par exemple:

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

Un arbre de fonction de mise à jour:

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

Pouvez-vous nous expliquer ce qu'ils font dans le code en utilisant ( (i) & (-i) )?

Answer 1

Supposons que la valeur négative est représentée en utilisant le complément à deux. Dans ce cas, -i peut être calculé comme (~i)+1 (flip bits, puis ajoutez 1).

Par exemple, permettez-moi de considérer i = 44. Puis, en binaire,

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

Comme vous le voyez, le moins de bits qui est 1 peut être calculée à l'aide de (i) & (-i).

Answer 2

Dans le cas où quelqu'un voulait une démonstration plus générale,

Supposons x a le format a10^k (sens ici, certains bitstring un, suivi par un 1, puis k zéros).

-x est (par définition) la même chose que ~x + 1, de sorte

• x et-x = (remplir)
• a10^k & -(a10^k) = (def. de la négation)
• a10^k & ~(a10^k) + 1 = (inversion)
• a10^k & ~a01^k + 1 = (ajouter 1)
• a10^k & ~a10^k = (ET entre une chose et son inverse)
• 0^w10^k

Il nous reste seulement que seul le plus à droite en 1 que nous avons supposé l'existence.

L'hypothèse sur la forme de la x laisse de côté les cas qu' x = 0, auquel cas le résultat est évidemment toujours de zéro.

Answer 3

Ces deux fonctions sont une modification de la mise en œuvre d'un index Binaire de l'arbre (Fenwick arbre) structure de données.
Voici deux photos pour compléter MikeCAT de répondre, en montrant comment je la variable de mises à jour pour différentes valeurs de.

La fonction get:
Pour assumer la valeur maxi de l'entrée en fonction est de 15 pour des raisons de simplicité de la représentation.

Un nœud avec le numéro de t sur elle représente l'arbre[t] dans l'arborescence de la matrice.
Si vous appelez d'obtenir la fonction de i la valeur retournée est la somme de l'arbre[i] plus la somme de tous les arbres les éléments du tableau qui leur index dans le tableau est un parent de i dans l'image, à l'exception de zéro.
Voici quelques exemples:

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]

Les numéros sur les étiquettes des nœuds dans l'image ci-dessus, a la propriété que chaque nœud parent du nœud d'étiquette moins le moins significatif de 1(très bien expliqué sur @MikeCAT réponse) La "mise à jour" de la fonction:
Pour des raisons de simplicité de l'image, nous supposons que la longueur maximum de l' arbre de la matrice est de 16.
La mise à jour de la fonction est un peu plus compliqué.

Il ajoute val d' arbre[i] et tous les arbres des éléments qui leur indice est parent du nœud avec l'étiquette j'ai dans l'image.

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;