delphi - 使用存储在变量中的有符号整数进行算术按位右移 "a shr b"– 结果错误!内部Delphi的错误？

Question

我有一个关于 Delphi 中位移行为的问题(或更可能是一个错误报告)(在 Borland Delphi 7 中测试)。

目标:对任意数字执行“算术”按位右移。

这意味着必须扩展符号位 - 如果设置了数字的最高有效位，则二进制数将从左侧填充 1 而不是 0。

因此，算术右移后的数字“-1”必须保持相同的数字(所有位 = 1)，但“逻辑移位”(始终用零填充数字)必须给出最大正整数(最大正符号整数) , 正确)

我只在 32 位系统 (Windows) 上测试过；此外，我需要它明确地处理 32 位整数。

当源编号存储在变量中时，Delphi 中似乎有一个带有“shr”的内部错误。

我的示例代码:

program bug;

{$APPTYPE CONSOLE}

var
I:Integer;
C:Cardinal;

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

(这只是开始)。接下来，让我们尝试一些“shr”:

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

“-1”与“$FFFFFFFF”等价。似乎“shr”行为(算术或逻辑)基于源数字是否有符号(整数或基数)这一事实。

输出是:

0) -1
1) 2147483647

相当正确。然后我需要尝试手动将这些数字转换为整数或基数:

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

结果:

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

还是正确的。因此，我认为如果需要算术移位，我可以将任何内容转换为“整数”；或者当我想要逻辑转变时转换为“基数”。可是等等!变量示例(如上声明):

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

突然:

6) 2147483647
7) 2147483647

不正确。我的“I”是一个有符号整数，我期待算术移位!那么，也许类型转换会有所帮助？

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

不，还是一样……

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

如果我尝试创建一个函数“a shr b”并使用它，事情会更糟:

// 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;

现在:

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

– 即使使用常量表达式，它也停止工作:(这是有道理的，因为数字再次存储在函数内的变量中)

C) 2147483647
D) 2147483647

由于无论如何我都需要进行正确的算术移位，因此我编写了这些公式来执行此操作(将“a”向右移位“b”位)。首先是逻辑转换:

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

我只需要按位和结果与“32 - b”(从右侧)清除“b”左位，以防“shr”失败并进行算术移位(没有示例显示这一点，但只是为了使当然)。然后算术移位:

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

我需要按位或从左侧使用“b”的结果，但仅当设置了最高有效位时；要做到这一点，我首先用“(a shr 31) 和 1”取符号位，然后否定这个数字以获得“-1”(或 $FFFFFFFF – 所有位 = 1)如果源为负，否则为 0(我把“0-x”而不仅仅是“-x”，因为在某些情况下，在我的 C 端口中，bcc32 C 编译器会报告一个警告，提示要对无符号整数进行否定)；最后我把它移到了“32 - b”位，所以即使“shr”失败并给出零，我也得到了我想要的。我为每个函数制作了两个版本来处理整数和基数(我也可以共享名称并为我“重载”它们，但在这里我不会这样做以保持示例清晰):

// 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;

测试一下:

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

并得到了完美的结果:

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

(G-case 仍然正确，因为“4294967295”是“-1”的无符号版本)

对变量的最终检查:

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

完美的:

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

对于这个错误，我还尝试将第二个数字(移位量)更改为变量和/或尝试不同的转换 - 存在相同的错误，看起来它与第二个参数无关。并且在输出之前尝试将结果转换为整数或基数也没有任何改善。

为了确保我不仅仅是一个有 bug 的人，我尝试在 http://codeforces.com/ 上运行我的整个示例。 (注册用户可以在服务器端编译和执行不同语言和编译器的一段代码)以查看输出。

“Delphi 7”编译器给了我我所拥有的 - 存在错误。替代选项“Free Pascal 2”显示更多错误输出:

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

奇怪的“9223372036854775807”在案例0-2-3(有“-1”、“Integer(-1)”和“Integer($FFFFFFFF)”谁不记得了)。

这是我在 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.

然后我很奇怪，这个错误是否也存在于 C++ 中？我写了一个 C++ 的端口并使用(Borland!)bcc32.exe 来编译它。

结果:

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

一切都好。这是 C++ 版本，以防有人还想看:

#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

}

在发帖之前，我试图搜索这个问题，并没有发现任何提到这个错误的地方。我也在这里看了: What is the behaviour of shl and shr for non register sized operands?在这里: Arithmetic Shift Right rather than Logical Shift Right – 但还讨论了其他问题(编译器在进行实际移位之前在内部将任何类型转换为 32 位数字；或移位超过 31 位)，但不是我的错误。

但是等等，这是我的问题: http://galfar.vevb.net/wp/2009/shift-right-delphi-vs-c/ !

有一句话:他们说——

In Delphi the SHR is always a SHR operation: it never takes into account the sign.

但我的例子表明 Delphi 考虑符号，但仅当源编号是常量表达式而不是变量时。所以“-10 shr 2”等于“-3”，但当“x:=-10”时，“x shr 2”等于“1073741821”。

所以我认为这是一个错误，而不是“shr”总是合乎逻辑的“行为”。你看，并非总是如此。
尝试启用/禁用任何编译器选项(例如范围检查或优化)并没有改变任何东西。

此外，我在这里发布了如何绕过这个问题并正确算术右移的示例。我的主要问题是:我是对的吗？

似乎左移在 Delphi 中总是好的(它从不使用原始符号位，而不是“未定义”:对于有符号整数，它在移位并将结果转换回整数之前表现为转换为基数 – 一个数字可能突然变为负数类(class))。但是现在我想知道，Delphi 中还有其他类似的错误吗？这是我在 Delphi 7 中发现的第一个真正重要的错误。我喜欢 Delphi 多过 C++ 正是因为我总是确信我的代码每次都在做我想做的事，而不用调试测试我正在使用的每一个新的不寻常的代码段即将写(恕我直言)。

附言这里有一些有用的链接，当我在发布这个问题之前输入我的标题时，StackOverflow 系统会向我建议这些链接。同样，有趣的信息，但不是关于这个错误:

Arithmetic bit-shift on a signed integer
Signed right shift = strange result?
Bitwise shift operators on signed types
Should you always use 'int' for numbers in C, even if they are non-negative?
Are the results of bitwise operations on signed integers defined?
Verifying that C / C++ signed right shift is arithmetic for a particular compiler?
Emulating variable bit-shift using only constant shifts?

P.P.S.非常感谢 Stack Exchange 团队在发布本文时提供的帮助。伙计们，你摇滚!

Answer 1

有一个错误，但不是你想的那样。这是documentation为 shr :

If x is a negative integer, the shl and shr operations are made clear in the following example:

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.

所以， shr和 shl总是逻辑移位而不是算术移位。

缺陷其实在于对负真常数的处理:

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

在这里， -1是一个有符号的值。它实际上有类型 Shortint , 一个有符号的 8 位整数。但是移位运算符对 32 位值进行操作，因此它被符号扩展为 32 位值。所以这意味着这段摘录应该产生两行具有相同输出的行:

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

并且输出应该是:

2147483647
2147483647

在 Delphi 的现代版本上，当然是 2010 版及更高版本，但可能是更早的版本，情况就是如此。

但是根据您的问题，在 Delphi 7 中， -1 shr 1计算结果为 -1这是错误的，因为 shr是逻辑转移。

我们可以猜测缺陷的来源。编译器评估 -1 shr 1因为它是一个常量值，编译器只是错误地使用了算术移位而不是逻辑移位。

顺便说一句，该文档包含另一个错误。它说:

The operations x shl y and x shr y shift the value of x to the left or right by y bits, which (if x is an unsigned integer) is equivalent to multiplying or dividing x by 2^y; the result is of the same type as x.

最后一部分是不正确的。表达式 x shl y是 32 位类型，如果 x是 8、16 或 32 位类型，否则为 64 位类型。

由于您的实际目标是实现算术移位，因此这些对您来说都不重要。您不能使用 shl或 shr .您必须自己实现算术移位。我建议您使用内联汇编器来执行此操作，因为我怀疑这最终可能更易于阅读和验证。