c++ - ¿Qué hace i+=(i &-i)? ¿Es portátil?

integer bit-manipulation (6)

Sea i un tipo entero con signo. Considerar

i += (i&-i); i -= (i&-i);

donde inicialmente i>0 .

¿Qué hacen estos? ¿Hay un código equivalente usando aritmética solamente?
¿Depende esto de una representación específica de bits de enteros negativos?

Fuente: código de configuración de un rompecabezas de codificación en línea (sin ninguna explicación / comentarios).

Aquí está lo que busqué impulsado por otras respuestas. Las manipulaciones de bits

i -= (i&-i); // strips off the LSB (least-significant bit) i += (i&-i); // adds the LSB

Se utilizan, predominantemente, para atravesar un árbol de Fenwick . En particular, i&-i proporciona el LSB si los enteros con signo se representan mediante el complemento de dos . Como ya lo señaló Peter Fenwick en su propuesta original, esto no es portátil a otras representaciones de enteros con signo. Sin embargo,

i &= i-1; // strips off the LSB

es (también funciona con el complemento y las representaciones de magnitudes firmadas ) y tiene una operación menos.

Sin embargo, no parece haber una alternativa portátil simple para agregar el LSB.

En una arquitectura de complemento de dos, con enteros con signo de 4 bits:

| i | bin | comp | -i | i&-i | dec | +----+------+------+----+------+-----+ | 0 | 0000 | 0000 | -0 | 0000 | 0 | | 1 | 0001 | 1111 | -1 | 0001 | 1 | | 2 | 0010 | 1110 | -2 | 0010 | 2 | | 3 | 0011 | 1101 | -3 | 0001 | 1 | | 4 | 0100 | 1100 | -4 | 0100 | 4 | | 5 | 0101 | 1011 | -5 | 0001 | 1 | | 6 | 0110 | 1010 | -6 | 0010 | 2 | | 7 | 0111 | 1001 | -7 | 0001 | 1 | | -8 | 1000 | 1000 | -8 | 1000 | 8 | | -7 | 1001 | 0111 | 7 | 0001 | 1 | | -6 | 1010 | 0110 | 6 | 0010 | 2 | | -5 | 1011 | 0101 | 5 | 0001 | 1 | | -4 | 1100 | 0100 | 4 | 0100 | 4 | | -3 | 1101 | 0011 | 3 | 0001 | 1 | | -2 | 1110 | 0010 | 2 | 0010 | 2 | | -1 | 1111 | 0001 | 1 | 0001 | 1 |

Observaciones:

Puede conjeturar que i&-i solo tiene un conjunto de bits (es una potencia de 2) y coincide con el conjunto de bits menos significativo de i .
i + (i&-i) tiene la propiedad interesante de estar un poco más cerca de la siguiente potencia de dos.
i += (i&-i) establece el bit de desarmado menos significativo de i .

Entonces, haciendo i += (i&-i); eventualmente te hará saltar a la siguiente potencia de dos:

| i | i&-i | sum | | i | i&-i | sum | +---+------+-----+ +---+------+-----+ | 1 | 1 | 2 | | 5 | 1 | 6 | | 2 | 2 | 4 | | 6 | 2 | -8 | | 4 | 4 | -8 | |-8 | -8 | UB | |-8 | -8 | UB | | i | i&-i | sum | | i | i&-i | sum | +---+------+-----+ +---+------+-----+ | 3 | 1 | 4 | | 7 | 1 | -8 | | 4 | 4 | -8 | |-8 | -8 | UB | |-8 | -8 | UB |

UB: el desbordamiento de un entero con signo exhibe un comportamiento indefinido.

La expresión i & -i se basa en el Complemento de Dos que se utiliza para representar enteros negativos. En pocas palabras, devuelve un valor k donde cada bit excepto el bit menos significativo se establece en 0 , pero ese bit menos significativo mantiene su propio valor. (es decir 1 )

Siempre que la expresión que proporcionó se ejecute en un sistema en el que el Complemento de Dos se utiliza para representar enteros negativos, sería portátil. Entonces, la respuesta a su segunda pregunta sería que la expresión depende de la representación de enteros negativos.

Para responder a su primera pregunta, dado que las expresiones aritméticas dependen de los tipos de datos y sus representaciones, no creo que haya una única expresión aritmética que sea equivalente a la expresión i & -i . En esencia, el siguiente código sería equivalente en funcionalidad a esa expresión. (Suponiendo que i sea del tipo int ). Sin embargo, tenga en cuenta que tuve que hacer uso de un bucle para producir la misma funcionalidad, y no solo aritmética.

int tmp = 0, k = 0; while(tmp < 32) { if(i & (1 << tmp)) { k = i & (1 << tmp); break; } tmp++; } i += k;

La forma más fácil de pensarlo es en términos de equivalencia matemática:

-i == (~i + 1)

Entonces -i invierte los bits del valor y luego agrega 1 . El significado de esto es que todos los 0 bits más bajos de i se convierten en 1 s mediante la operación ~i , por lo que agregar 1 al valor hace que todos esos bits 1 bajos se conviertan en 0 mientras se lleva el 1 hacia arriba hasta que caiga en una 0 bit, que simplemente será la misma posición que el bit 1 más bajo en i .

Aquí hay un ejemplo para el número 6 (0110 en binario):

i = 0110 ~i == 1001 (~i + 1) == 1010 i & (~i + 1) == 0010

Es posible que deba realizar cada operación manualmente varias veces antes de realizar los patrones en los bits.

Aquí hay dos ejemplos más:

i = 1000 ~i == 0111 (~i + 1) == 1000 i & (~i + 1) == 1000 i = 1100 ~i == 0011 (~i + 1) == 0100 i & (~i + 1) == 0100

¿Ves cómo el + 1 causa una especie de ''cascada de bits'' que lleva el uno hasta el primer bit 0 abierto?

Entonces, si (i & -i) es un medio para extraer el bit 1 más bajo, entonces se deduce que los casos de uso de i += (i & -i) y i -= (i & -i) son intentos de agregar y Resta el bit 1 más bajo de un valor.

Restar el 1 bit más bajo de un valor de sí mismo sirve como un medio para poner a cero ese bit.

Agregar el 1 bit más bajo de un valor a sí mismo no parece tener ningún propósito especial, simplemente hace lo que dice en la lata.

Debe ser portátil en cualquier sistema utilizando el complemento de dos.

Si i tiene un tipo sin signo, las expresiones son completamente portátiles y están bien definidas.

Si i tiene tipo firmado, no es portátil, ya que & se define en términos de representaciones, pero unario - , += , y -= se definen en términos de valores. Sin embargo, si la próxima versión de los mandatos estándar de C ++ se complementa , se convertirá en portátil y hará lo mismo que en el caso sin firma.

En el caso sin firma (y el caso del complemento de dos), es fácil confirmar que i&-i es una potencia de dos (tiene solo un bit distinto de cero), y tiene el mismo valor que el bit de posición más bajo de i (que también es el bit más bajo de -i ). Por lo tanto:

i -= i&-i; borra el bit de conjunto más bajo de i .
i += i&-i; incrementos (borrado, pero con llevar a bits más altos) el bit de conjunto más bajo de i .

Para los tipos sin firmar nunca hay desbordamiento para ninguna expresión. Para los tipos con signo, i -= i&-i desborda tomando -i cuando inicialmente tengo el valor mínimo del tipo, y i += i&-i desborda en el += cuando i inicialmente tiene el valor máximo del tipo.

i & -i es la forma más fácil de obtener el bit menos significativo (LSB) para un entero i .
Puedes leer más here .
A1: Puede leer más sobre ''Equivalentes matemáticos'' here .
A2: Si la representación de enteros negativos no es la forma estándar usual (es decir, enteros grandes extraños), entonces i & -i podría no ser LSB.