Aritmética en modo bit a la derecha "a shr b" con enteros con signo que se almacenan en variables-¡resultados incorrectos! ¿Error interno de Delphi?

integer delphi-7

Question

Tengo una pregunta (o más probablemente un informe de error) sobre el comportamiento de cambio de bit en Delphi (probado en Borland Delphi 7).

Objetivo: realice un desplazamiento de bit a la derecha "Aritmético" con cualquier número.

Esto significa que debe ampliarse el bit de signo: el número binario se rellenará desde la izquierda con 1 en lugar de 0 si se configuró el bit más significativo de un número.

Entonces, el número "-1" después de un desplazamiento aritmético a la derecha debe permanecer igual (todos los bits = 1), pero con "cambio lógico" (que siempre llena el número con ceros) debe dar un entero positivo máximo (entero máximo con signo positivo) , ser correcto)

Lo probé solo en un sistema de 32 bits (Windows); además, necesito que trabaje explícitamente con enteros de 32 bits.

Parece que hay un error interno en Delphi con "shr" cuando el número fuente está almacenado en una variable.

Mi código de ejemplo:

program bug;

{$APPTYPE CONSOLE}

var
I:Integer;
C:Cardinal;

begin
I := -1;  // we’ll need that later
C := $FFFFFFFF;

(Es solo el comienzo). A continuación, probemos algunos "shr" s:

Writeln(''0) '', -1 shr 1 );
Writeln(''1) '', $FFFFFFFF shr 1 );

"-1" es un equivalente firmado a "$ FFFFFFFF". Parece que el comportamiento "shr" (aritmético o lógico) se basa en el hecho de si el número fuente está firmado o no (entero o cardinal).

La salida es:

0) -1
1) 2147483647

Bastante correcto. Luego, tengo que intentar convertir estos números manualmente en enteros o cardenales:

Writeln(''2) '', Integer(-1) shr 1 );
Writeln(''3) '', Integer($FFFFFFFF) shr 1 );
Writeln(''4) '', Cardinal(-1) shr 1 );
Writeln(''5) '', Cardinal($FFFFFFFF) shr 1 );

Resultado:

2) -1
3) -1
4) 2147483647
5) 2147483647

Aún correcto Entonces, creo que puedo convertir cualquier cosa en "entero" si necesito un cambio aritmético; o lanzar al "cardenal" cuando quiero un cambio lógico. ¡Pero espera! Ejemplo con variables (declaradas arriba):

Writeln(''6) '', I shr 1 );
Writeln(''7) '', C shr 1 );

Repentinamente:

6) 2147483647
7) 2147483647

INCORRECTO. Mi "I" era un número entero con signo, ¡y esperaba el cambio aritmético! Entonces, ¿quizás el casting podría ayudar?

Writeln(''8) '', Integer(I) shr 1 );
Writeln(''9) '', Cardinal(I) shr 1 );
Writeln(''A) '', Integer(C) shr 1 );
Writeln(''B) '', Cardinal(C) shr 1 );

No, sigue igual ...

8) 2147483647
9) 2147483647
A) 2147483647
B) 2147483647

Las cosas son incluso peores si intento hacer una función "a shr b" y usarla en su lugar:

// Simple shift right with signed integers
function shrI(a,b:Integer):Integer;
begin
Result := a shr b;
end;

// Simple shift right with unsigned integers
function shrC(a,b:Cardinal):Cardinal;
begin
Result := a shr b;
end;

Ahora:

Writeln(''C) '', shrI(-1,1) );
Writeln(''D) '', shrC($FFFFFFFF,1) );

- Dejó de funcionar incluso con expresiones constantes: (tiene sentido, porque los números se almacenan nuevamente en variables dentro de una función)

C) 2147483647
D) 2147483647

Ya que necesito hacer mi cambio aritmético correcto de todos modos, escribí estas fórmulas para hacer esto (cambie "a" a la derecha por bits "b"). Primero es el cambio lógico:

(a shr b) and ((1 shl (32-b))-1)

Solo necesito bitwise, y el resultado con "32 - b" (de la derecha) para borrar bits "b" de la izquierda en caso de que "shr" me falle e hiciera aritmética shift (ningún ejemplo lo muestra, sino simplemente para hacer Por supuesto). Luego el cambio aritmético:

(a shr b) or (( 0-((a shr 31) and 1)) shl (32-b))

Lo necesito a nivel de bit, o el resultado con "b" de la izquierda, pero solo cuando se estableció el bit más significativo; para hacer esto primero tomo el bit de signo con "(un shr 31) y 1", luego niego este número para obtener "-1" (o $ FFFFFFFF - todos los bits = 1) si la fuente fue negativa, y 0 de lo contrario (puse "0-x" en lugar de solo "-x" porque en mi puerto C, en algunos casos, el compilador C de bcc32 informa de una advertencia de vinculación para anular un entero sin signo); y finalmente lo cambié a "32 - b" bits restantes, así que obtuve lo que deseo incluso cuando "shr" falla y doy los ceros. Hice dos versiones de cada función para tratar con enteros y cardenales (también pude compartir nombres y "sobrecargarlos", pero aquí no haré esto para mantener el ejemplo claro):

// Logical shift right with signed integers
function srlI(a,b:Integer):Integer;
begin
Result := (a shr b) and ((1 shl (32-b))-1);
end;

// Arithmetic shift right with signed integers
function sraI(a,b:Integer):Integer;
begin
Result := (a shr b) or (( 0-((a shr 31) and 1)) shl (32-b));
end;

// Logical shift right with unsigned integers
function srlC(a,b:Cardinal):Cardinal;
begin
Result := (a shr b) and ((1 shl (32-b))-1);
end;

// Arithmetic shift right with unsigned integers
function sraC(a,b:Cardinal):Cardinal;
begin
Result := (a shr b) or (( 0-((a shr 31) and 1)) shl (32-b));
end;

Pruébalo:

Writeln(''E) '', sraI(-1,1) );
Writeln(''F) '', srlI(-1,1) );
Writeln(''G) '', sraC($FFFFFFFF,1) );
Writeln(''H) '', srlC($FFFFFFFF,1) );

Y obtuve resultados perfectos:

E) -1
F) 2147483647
G) 4294967295
H) 2147483647

(G-case sigue siendo correcto, porque "4294967295" es la versión sin firma de "-1")

Controles finales con variables:

Writeln(''K) '', sraI(I,1) );
Writeln(''L) '', srlI(I,1) );
Writeln(''M) '', sraC(C,1) );
Writeln(''N) '', srlC(C,1) );

Perfecto:

K) -1
L) 2147483647
M) 4294967295
N) 2147483647

Para este error, también traté de cambiar el segundo número (cantidad de turno) a una variable y / o probar el casting diferente - el mismo error presente, parece que no está relacionado con el segundo argumento. Y tratar de lanzar el resultado (a entero o al cardenal) antes de la salida tampoco mejoró nada.

Para asegurarme de que no solo soy uno que tiene el error, traté de ejecutar todo mi ejemplo en http://codeforces.com/ (allí un usuario registrado puede compilar y ejecutar un código en diferentes idiomas y compiladores en lado del servidor) para ver la salida.

El compilador "Delphi 7" me dio exactamente lo que tengo: el error estaba presente. La opción alternativa, "Free Pascal 2" muestra aún más resultados incorrectos:

0) 9223372036854775807
1) 2147483647
2) 9223372036854775807
3) 9223372036854775807
4) 2147483647
5) 2147483647
6) 2147483647
7) 2147483647
8) 2147483647
9) 2147483647
A) 2147483647
B) 2147483647
C) 2147483647
D) 2147483647
E) -1
F) 2147483647
G) 4294967295
H) 2147483647
K) -1
L) 2147483647
M) 4294967295
N) 2147483647

Extraño "9223372036854775807" en los casos 0-2-3 (había "-1", "Entero (-1)" y "Entero ($ FFFFFFFF)" que no recuerdo).

Aquí está mi ejemplo completo en Delphi:

program bug;

{$APPTYPE CONSOLE}

// Simple shift right with signed integers
function shrI(a,b:Integer):Integer;
begin
Result := a shr b;
end;

// Simple shift right with unsigned integers
function shrC(a,b:Cardinal):Cardinal;
begin
Result := a shr b;
end;

// Logical shift right with signed integers
function srlI(a,b:Integer):Integer;
begin
Result := (a shr b) and ((1 shl (32-b))-1);
end;

// Arithmetic shift right with signed integers
function sraI(a,b:Integer):Integer;
begin
Result := (a shr b) or (( 0-((a shr 31) and 1)) shl (32-b));
end;

// Logical shift right with unsigned integers
function srlC(a,b:Cardinal):Cardinal;
begin
Result := (a shr b) and ((1 shl (32-b))-1);
end;

// Arithmetic shift right with unsigned integers
function sraC(a,b:Cardinal):Cardinal;
begin
Result := (a shr b) or (( 0-((a shr 31) and 1)) shl (32-b));
end;

var
I:Integer;
C:Cardinal;

begin
I := -1;
C := $FFFFFFFF;

Writeln(''0) '', -1 shr 1 );
Writeln(''1) '', $FFFFFFFF shr 1 );
// 0) -1           - correct
// 1) 2147483647   - correct

Writeln(''2) '', Integer(-1) shr 1 );
Writeln(''3) '', Integer($FFFFFFFF) shr 1 );
// 2) -1           - correct
// 3) -1           - correct

Writeln(''4) '', Cardinal(-1) shr 1 );
Writeln(''5) '', Cardinal($FFFFFFFF) shr 1 );
// 4) 2147483647   - correct
// 5) 2147483647   - correct

Writeln(''6) '', I shr 1 );
Writeln(''7) '', C shr 1 );
// 6) 2147483647   - INCORRECT!
// 7) 2147483647   - correct

Writeln(''8) '', Integer(I) shr 1 );
Writeln(''9) '', Cardinal(I) shr 1 );
// 8) 2147483647   - INCORRECT!
// 9) 2147483647   - correct

Writeln(''A) '', Integer(C) shr 1 );
Writeln(''B) '', Cardinal(C) shr 1 );
// A) 2147483647   - INCORRECT!
// B) 2147483647   - correct

Writeln(''C) '', shrI(-1,1) );
Writeln(''D) '', shrC($FFFFFFFF,1) );
// C) 2147483647   - INCORRECT!
// D) 2147483647   - correct

Writeln(''E) '', sraI(-1,1) );
Writeln(''F) '', srlI(-1,1) );
// E) -1           - correct
// F) 2147483647   - correct

Writeln(''G) '', sraC($FFFFFFFF,1) );
Writeln(''H) '', srlC($FFFFFFFF,1) );
// G) 4294967295   - correct
// H) 2147483647   - correct

Writeln(''K) '', sraI(I,1) );
Writeln(''L) '', srlI(I,1) );
// K) -1           - correct
// L) 2147483647   - correct

Writeln(''M) '', sraC(C,1) );
Writeln(''N) '', srlC(C,1) );
// M) 4294967295   - correct
// N) 2147483647   - correct

end.

Entonces yo era curioso, ¿este error también está presente en C ++? Escribí un puerto a C ++ y uso (Borland!) Bcc32.exe para compilarlo.

Resultados:

0) -1
1) 2147483647
2) -1
3) -1
4) 2147483647
5) 2147483647
6) -1
7) 2147483647
8) -1
9) 2147483647
A) -1
B) 2147483647
C) -1
D) 2147483647
E) -1
F) 2147483647
G) 4294967295
H) 2147483647
K) -1
L) 2147483647
M) 4294967295
N) 2147483647

Todo está bien. Aquí está la versión de C ++, en caso de que alguien también quiera mirar:

#include <iostream>
using namespace std;

// Simple shift right with signed integers
int shrI(int a, int b){
return a >> b;
}

// Simple shift right with unsigned integers
unsigned int shrC(unsigned int a, unsigned int b){
return a >> b;
}

// Logical shift right with signed integers
int srlI(int a, int b){
return (a >> b) & ((1 << (32-b))-1);
}

// Arithmetic shift right with signed integers
int sraI(int a, int b){
return (a >> b) | (( 0-((a >> 31) & 1)) << (32-b));
}

// Logical shift right with unsigned integers
unsigned int srlC(unsigned int a, unsigned int b){
return (a >> b) & ((1 << (32-b))-1);
}

// Arithmetic shift right with unsigned integers
unsigned int sraC(unsigned int a, unsigned int b){
return (a >> b) | (( 0-((a >> 31) & 1)) << (32-b));
}

int I;
unsigned int C;

int main(){
I = -1;
C = 0xFFFFFFFF;

cout<<"0) "<<( -1 >> 1 )<<endl;
cout<<"1) "<<( 0xFFFFFFFF >> 1 )<<endl;
// 0) -1           - correct
// 1) 2147483647   - correct

cout<<"2) "<<( ((int)(-1)) >> 1 )<<endl;
cout<<"3) "<<( ((int)(0xFFFFFFFF)) >> 1 )<<endl;
// 2) -1           - correct
// 3) -1           - correct

cout<<"4) "<<( ((unsigned int)(-1)) >> 1 )<<endl;
cout<<"5) "<<( ((unsigned int)(0xFFFFFFFF)) >> 1 )<<endl;
// 4) 2147483647   - correct
// 5) 2147483647   - correct

cout<<"6) "<<( I >> 1 )<<endl;
cout<<"7) "<<( C >> 1 )<<endl;
// 6) -1           - correct
// 7) 2147483647   - correct

cout<<"8) "<<( ((int)(I)) >> 1 )<<endl;
cout<<"9) "<<( ((unsigned int)(I)) >> 1 )<<endl;
// 8) -1           - correct
// 9) 2147483647   - correct

cout<<"A) "<<( ((int)(C)) >> 1 )<<endl;
cout<<"B) "<<( ((unsigned int)(C)) >> 1 )<<endl;
// A) -1           - correct
// B) 2147483647   - correct

cout<<"C) "<<( shrI(-1,1) )<<endl;
cout<<"D) "<<( shrC(0xFFFFFFFF,1) )<<endl;
// C) -1           - correct
// D) 2147483647   - correct

cout<<"E) "<<( sraI(-1,1) )<<endl;
cout<<"F) "<<( srlI(-1,1) )<<endl;
// E) -1           - correct
// F) 2147483647   - correct

cout<<"G) "<<( sraC(0xFFFFFFFF,1) )<<endl;
cout<<"H) "<<( srlC(0xFFFFFFFF,1) )<<endl;
// G) 4294967295   - correct
// H) 2147483647   - correct

cout<<"K) "<<( sraI(I,1) )<<endl;
cout<<"L) "<<( srlI(I,1) )<<endl;
// K) -1           - correct
// L) 2147483647   - correct

cout<<"M) "<<( sraC(C,1) )<<endl;
cout<<"N) "<<( srlC(C,1) )<<endl;
// M) 4294967295   - correct
// N) 2147483647   - correct

}

Antes de publicar aquí, intenté buscar este problema y no encontré ninguna mención de este error. También miré aquí: ¿Cuál es el comportamiento de shl y shr para los operandos de tamaño no registrado? y aquí: Aritmética Shift Right en vez de Logical Shift Right - pero se discutieron otros problemas (que el compilador internamente arroja cualquier tipo al número de 32 bits antes de hacer el cambio real, o cambiar más de 31 bits), pero no el error de la mina.

Pero espera, aquí está mi problema: http://galfar.vevb.net/wp/2009/shift-right-delphi-vs-c/ !

Con un comentario: dicen:

En Delphi, el SHR siempre es una operación SHR: nunca tiene en cuenta el signo.

Pero mi ejemplo muestra que Delphi sí tiene en cuenta el signo, pero solo cuando el número fuente es una expresión constante, no una variable. Entonces "-10 shr 2" es igual a "-3", pero "x shr 2" es igual a "1073741821" cuando "x: = - 10".

Entonces creo que esto es un error, y no un "comportamiento" que "shr" siempre es lógico. Ya ves, no siempre.
Intentar habilitar / deshabilitar cualquier opción del compilador, como una verificación de rango u optimizaciones, no cambió nada.

Además, aquí publiqué ejemplos de cómo eludir este problema y tener el correcto cambio aritmético correcto. Y mi pregunta principal es: ¿estoy en lo cierto?

Parece que el desplazamiento a la izquierda siempre es bueno en Delphi (nunca usa el bit de signo original, y no "indefinido": para los enteros con signo se comporta como casting a cardinal antes de cambiar y devuelve el resultado a entero; un número puede convertirse de repente en negativo de curso). Pero ahora me pregunto, ¿hay algún otro error similar en Delphi? Este es el primer error realmente significativo que he descubierto en Delphi 7. Me encanta Delphi más que C ++ exactamente porque siempre estaba seguro de que mi código siempre hacía lo que quería, sin probar la depuración de cada nueva pieza inusual de código que soy a punto de escribir (en mi humilde opinión).

PD Aquí hay algunos enlaces útiles que el sistema StackOverflow me sugiere cuando escribí mi título antes de publicar esta pregunta. De nuevo, información interesante, pero no sobre este error:

Desplazamiento de bits aritmético en un entero con signo
Firmado a la derecha shift = resultado extraño?
Operadores de desplazamiento bit a bit en tipos con signo
¿Debería siempre usar ''int'' para los números en C, incluso si no son negativos?
¿Se definen los resultados de las operaciones bit a bit en los enteros con signo?
¿Verificando que el desplazamiento a la derecha con signo C / C ++ es aritmético para un compilador en particular?
¿Emula el cambio de bit variable usando solo cambios constantes?

PPS Muchas gracias al equipo de Stack Exchange por su asistencia para publicar este artículo. Chicos, ¡Rock!

Answer 1

Hay un error, pero no es lo que piensas. Aquí está la documentation para shr :

Si x es un entero negativo, las operaciones shl y shr se aclaran en el siguiente ejemplo:

var
  x: integer;
  y: string;

...
begin
  x := -20;
  x := x shr 1;
  //As the number is shifted to the right by 1 bit, the sign bit''s value replaced is
  //with 0 (all negative numbers have the sign bit set to 1). 

  y := IntToHex(x, 8);
  writeln(y);
  //Therefore, x is positive.
  //Decimal value: 2147483638
  //Hexadecimal value: 7FFFFFF6
  //Binary value: 0111 1111 1111 1111 1111 1111 1111 0110
end.

Entonces, shr y shl son siempre cambios lógicos y no son cambios aritméticos.

El defecto está realmente en el manejo de constantes verdaderas negativas:

Writeln(''0) '', -1 shr 1 );

Aquí, -1 es un valor firmado. En realidad, tiene Type Shortint , un entero de 8 bits con signo. Pero los operadores de turno operan con valores de 32 bits, por lo que el signo se extiende a un valor de 32 bits. Entonces eso significa que este extracto debería producir dos líneas con salida idéntica:

var
  i: Integer;
....
i := -1;
Writeln(-1 shr 1);
Writeln( i shr 1);

y que la salida debería ser:

2147483647
2147483647

En las versiones modernas de Delphi, ciertamente desde la versión 2010 y posteriores, pero posiblemente incluso versiones anteriores, ese es el caso.

Pero según su pregunta, en Delphi 7, -1 shr 1 evalúa a -1 cual es incorrecto, porque shr es un cambio lógico.

Podemos adivinar la fuente del defecto. El compilador evalúa -1 shr 1 porque es un valor constante, y el compilador simplemente lo hace incorrectamente, usando shift aritmético en lugar de shift lógico.

Por cierto, la documentación contiene otro error. Dice:

Las operaciones x shl y y x shr y desplazan el valor de x hacia la izquierda o la derecha en y bits, que (si x es un entero sin signo) es equivalente a multiplicar o dividir x por 2 ^ y; el resultado es del mismo tipo que x.

La parte final no es verdad. La expresión x shl y es un tipo de 32 bits, si x es un tipo de 8, 16 o 32 bits, de otro modo un tipo de 64 bits.

Dado que su objetivo real es implementar cambios aritméticos, nada de esto le importa a usted. No puedes usar shl o shr . Tendrá que implementar el desplazamiento aritmético usted mismo. Sugiero que lo haga utilizando el ensamblador en línea, ya que sospecho que, en última instancia, podría ser más fácil de leer y verificar.

Answer 2

Probé en Delphi 7 y parece que el simple uso de "div 2" en una variable entera se compila directamente en una operación de ensamblador SAR (como se ve en la ventana de la CPU).

Actualización: Div no funciona correctamente como un reemplazo para SAR como expliqué en mi comentario en esta respuesta. El compilador genera una declaración SAR, pero luego prueba el bit de signo y ajusta la respuesta agregando el bit que se desplazó a la derecha si se establece el bit de signo. Esto proporciona el comportamiento correcto para el operador div en los números negativos, pero anula nuestro objetivo de obtener el comportamiento SAR correcto.

Answer 3

Si estás atascado con las versiones asm de los cambios aritméticos, aquí hay un código que funcionaría:

Tenga en cuenta que de acuerdo con: http://docwiki.embarcadero.com/RADStudio/XE8/en/Program_Control
Los primeros 3 parámetros se pasan en los registros de la siguiente manera: EAX, EDX, ECX

En 64 bit, la orden de registro es: RCX, RDX, R8, R9

El resultado de las funciones se pasa en EAX

unit SARL;

interface

  function sar(const base: integer; shift: byte): integer; 
  function sal(const base: integer; shift: byte): integer;

implementation

  function sar(const base: integer; shift: byte): integer;
  asm
    {$IFDEF CPU64BIT}
    mov eax,ecx
    mov ecx,edx
    sar eax,cl
    {$ELSE}
    mov ecx,edx
    sar eax,cl  //shr is very different from sar
    {$ENDIF}
  end;

  function sal(const base: integer; shift: byte): integer; 
  asm
    {$IFDEF CPU64BIT}
    mov eax,ecx
    mov ecx,edx
    shl eax,cl
    {$ELSE}
    mov ecx,edx
    shl eax,cl   //Note that sal and shl are the same thing.
    {$ENDIF}
  end;

end.