Desplazar a la derecha para realizar la división por 2 en -1

Question

Sé que puedo dividir entre 2 usando el desplazamiento a la derecha.

Por simplicidad, echar un sistema de números de 4 bits

-1 - 1111 
-2 - 1110 
-3 - 1101 
-4 - 1100 
-5 - 1011 
-6 - 1010 
-7 - 1001 
-8 - 1000 
7 - 0111 
6 - 0110 
5 - 0101 
4 - 0100 
3 - 0011 
2 - 0010 
1 - 0001 
0 - 0000 

Si trato de realizar

6/2 = 0110 >> 1 = 0011 = 3 
-6/ 2 = 1010 >> 1 = 1101 = -3 

es válido para ambos + ve y -ve número

Sin embargo, cuando venga a 1

1/2 = 0001 >> 1 = 0000 = 0 
-1/ 2 = 1111 >> 1 = 1111 = -1 

Parece que hay un caso especial en -1, como desplazamiento a la derecha para moverlo a infinito negativo.

Actualmente, tengo que poner una especial si cheque para esto, ya que estoy esperando -1/2 = 0.

Me preguntaba ¿cómo se controla esta excepción chico en su código? ¿Tu hombre puso un cheque si?

Answer 1

Cualquier número impar negativo no va a funcionar. Sin embargo, para responder a su pregunta, si sabe que puede tener números negativos, simplemente divida por 2. Esto se convierte en un cambio con una corrección por parte del jit/compilador.

Answer 2

En el caso impar, ambas operaciones dan como resultado una operación de piso en el resultado.

• 3/2 -> baja (1,5) => 1
• -3/2 -> baja (-1,5) => -2

Se puede poner un cheque, algo así como \

if (isOdd(number) && isNegative(number)) 
    result++; 

Answer 3

Si desplazamiento a la derecha para dividir por dos, que siempre terminan "redondeo" abajo - hacia cero si es positivo, lejos de ella si es negativo.

Si esto no es lo que quiere, se puede corregir para ello:

if (n & 1 > 0 && n < 0) 
    result += 1; 

Answer 4

Odio decirlo, pero no lo manejo en mi código, ya que no uso el cambio de bit para multiplicar o dividir. Esto me huele a premature optimisation.

¿Por qué crees que tienes que hacer la división con cambio de bit en lugar de la más legible x/2?

Answer 5

@Anon es técnicamente correcto.

Sin embargo, es mejor práctica utilizar el operador / para la división y dejar la micro-optimización en el compilador JIT. El compilador JIT es capaz de optimizar las divisiones por constantes como secuencias shift/add ... cuando esto es lo mejor para la plataforma de ejecución.

Hacer este tipo de cosas es (probablemente) una optimización prematura, y puede ser una anti-optimización si su código necesita ejecutarse rápidamente en múltiples plataformas Java.

Answer 6

Me aburrí un día y describí divisiones vs turnos para el poder de 2 cosas; pensé que lo publicaría aquí para cualquier persona interesada.

En HotSpot VM 1.6 en Windows, usando j /= 4 en -100000000 a 100000000 funcionó en aproximadamente 12 segundos mientras se usa j = (j >= 0) ? j >> 2 : ~(~j+1 >> 2) + 1; funcionó en solo 2.5s.

OpenJDK VM 1.6 en Linux tiene 5.5s para divisiones y 1.5s para turnos.

Esto sugeriría que el compilador JIT realmente no hace nada especial para el poder de 2 divisiones.

GCC logró optimizar la división para que fuera más rápido que los cambios y cambios.

~(~j+1 >> 2) + 1 usa el complemento de dos para voltear el número positivo, cambiarlo y voltearlo.

long j = 0; 
for (long i = -100000000; i < 100000000; i++) { 
    j = i; 
    j /= 4; 
} 
System.out.println(j);` 

vs

long j = 0; 
for (long i = -100000000; i < 100000000; i++) { 
    j = i; 
    j = (j >= 0) ? j >> 2 : ~(~j+1 >> 2) + 1; 
} 
System.out.println(j);`