¿Qué significa (number & - number) en la programación de bits? [duplicar]

Esta pregunta ya tiene una respuesta aquí:

Por ejemplo: 

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

Una función de actualización de árbol: 

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

¿Puede explicar lo que hacen en el código usando ( (i) & (-i) )?

Author: SwadhIn, 2016-03-08
Source

3 answers

Estas dos funciones son una implementación modificada de una estructura de datos árbol de índice binario (árbol de Fenwick).
Aquí hay dos imágenes para complementar la respuesta de MikeCAT que muestran cómo i las variables se actualizan para diferentes valores.

La función" get":
Para asumir el valor máximo de entrada en la función es 15 para la simplicidad de la representación.
introduzca la descripción de la imagen aquí
Un nodo con el número t en él representa tree[t] en la matriz de árboles.
Si call getfunction for ithe returned value is sum of tree[i] plus sum of all treearray elements that their index in the array is a parent of i in the picture, except zero.
Estos son algunos ejemplos:

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]


Numbers en las etiquetas de los nodos en la imagen de arriba, tiene la propiedad de que el padre de cada nodo es esa etiqueta de nodo menos la menos significativa 1 (explicado muy bien en @MikeCAT respuesta) La " actualización" función:
Para simplificar la imagen, supongamos que la longitud máxima de la matriz tree es 16.
La función update es un poco más complicada.
introduzca la descripción de la imagen aquí
Agrega val a tree[i] y todos los elementos tree que su índice es padre del nodo con label i en la imagen.

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;
 11
Author: FazeL,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-03-09 09:38:51

Permítanme asumir que el valor negativo se representa utilizando el complemento de dos. En este caso, -i se puede calcular como (~i)+1 (voltear bits, luego agregar 1).

Por ejemplo, permítanme considerar i = 44. Entonces, en binario, 

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

Como ves, el mínimo bit que es 1 se puede calcular usando (i) & (-i).

 85
Author: MikeCAT,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-03-08 07:19:39

En caso de que alguien quisiera una prueba más general también,

Supongamos que xtiene el formato a10 k (lo que significa aquí, alguna cadena de bits a, seguida de un 1, seguida de k ceros).

-x es (por definición) lo mismo que ~x + 1, entonces

  • x & - x = (rellenar)
  • a10k & -(a10k) = (def. de negación)
  • a10k & ~(a10k) + 1 = (aplicar la inversión)
  • a10k & ~a01k + 1 = (agregar 1)
  • a10k & ~a10k = (Y entre algo y su inversa)
  • 0w10k

Así que nos quedamos solo con ese único 1 a la derecha que asumimos que existía.

La suposición sobre la forma de x deja fuera el caso de que x = 0, en cuyo caso el resultado es obviamente todavía cero.

 21
Author: harold,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-03-08 15:20:17