変数に格納された符号付き整数の算術ビット単位の右シフト「a shr b」 – 間違った結果! Delphi の内部バグ? 質問する

変数に格納された符号付き整数の算術ビット単位の右シフト「a shr b」 – 間違った結果! Delphi の内部バグ? 質問する

Delphi のビット シフト動作 (Borland Delphi 7 でテスト済み) について質問 (またはバグ レポート) があります。

ターゲット: 任意の数値で「算術」ビット単位の右シフトを実行します。

これは、符号ビットを拡張する必要があることを意味します。数値の最上位ビットが設定されている場合、2 進数は左から 0 ではなく 1 で埋められます。

したがって、算術右シフト後の数値「-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)

「shr」が失敗して代わりに算術シフトを実行した場合に備えて、結果を「32 - b」個のビット(右から)でビット単位の論理積をとり、「b」個の左ビットをクリアする必要があります(これを示す例はありませんが、念のため)。次に算術シフトを実行します。

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

結果のビット単位の論理和を左から「b」個取る必要がありますが、これは最上位ビットが設定されている場合に限ります。これを行うには、まず「(a shr 31) and 1」で符号ビットを取得し、次にこの数値を反転して、ソースが負の場合は「-1」(または $FFFFFFFF – すべてのビット =1)、それ以外の場合は 0 を取得します (「-x」ではなく「0-x」と入力したのは、C ポートで bcc32 C コンパイラが符号なし整数を反転しようとしているという警告をレポートする場合があるためです)。最後に、これを「32 - b」ビット左にシフトしました。これにより、「shr」が失敗してゼロが返された場合でも、必要な結果が得られます。整数と基数の両方を処理するために、各関数の 2 つのバージョンを作成しました (名前を共有して「オーバーロード」することもできますが、ここでは例をわかりやすくするためにこれを行いません)。

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

(「4294967295」は「-1」の符号なしバージョンなので、G ケースは依然として正しいです)

変数を使用した最終チェック:

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

このバグについては、2 番目の数値 (シフト量) を変数に変更したり、別のキャストを試したりしてみましたが、同じバグが発生し、2 番目の引数とは関係がないようです。また、出力前に結果をキャスト (整数または基数に) しようとしても、何も改善されませんでした。

このバグに遭遇したのは私だけではないことを確かめるために、私は全体の例を次のように実行してみました。出典: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

0-2-3 の場合に奇妙な「9223372036854775807」(覚えていない「-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

}

ここに投稿する前に、この問題を検索してみましたが、このバグに関する言及は見つかりませんでした。また、こちらも調べました:レジスタサイズ以外のオペランドに対する shl と shr の動作は何ですか?そしてここ:論理右シフトではなく算術右シフト– ただし、他の問題 (コンパイラが実際のシフトを行う前に任意の型を内部的に 32 ビットの数値にキャストする、または 31 ビットを超えてシフトする) についても議論されましたが、私のバグについては議論されませんでした。

しかし、待ってください。ここに問題があります:http://galfar.vevb.net/wp/2009/shift-right-delphi-vs-c/

一つの発言:彼らは言う –

Delphi では、SHR は常に SHR 演算であり、符号は考慮されません。

しかし、私の例では、Delphiする符号を考慮しますが、ソース番号が変数ではなく定数式の場合のみです。したがって、「-10 shr 2」は「-3」に等しくなりますが、「x:=-10」の場合、「x shr 2」は「1073741821」に等しくなります。

したがって、これはバグであり、「shr」が常に論理的であるという「動作」ではないと思います。常にそうとは限りません。
範囲チェックや最適化などのコンパイラ オプションを有効/無効にしようとしても、何も変わりませんでした。

また、この問題を回避して正しい算術シフトを右に行う方法の例をここに投稿しました。そして私の主な質問は、私が正しいかどうかです。

Delphi では左シフトは常に有効であるようです (元の符号ビットは使用されず、「未定義」でもありません。符号付き整数の場合、シフトする前に基数にキャストして結果を整数にキャストし直すように動作します。もちろん、数値が突然負になることもあります)。しかし、Delphi には他にも同様のバグがあるのだろうかと疑問に思います。これは、Delphi 7 で初めて発見した本当に重大なバグです。私が C++ よりも Delphi が好きなのは、書く予定の新しい通常とは異なるコードをすべてデバッグ テストしなくても、自分のコードが常に望みどおりに動作することを常に確信していたからです (私見)。

PS: この質問を投稿する前にタイトルを入力したときに StackOverflow システムが提案してくれた便利なリンクをいくつか紹介します。これも興味深い情報ですが、このバグに関するものではありません。

符号付き整数の算術ビットシフト
符号付き右シフト = 奇妙な結果?
符号付き型のビットシフト演算子
C では、数値が負でない場合でも常に「int」を使用する必要がありますか?
符号付き整数に対するビット演算の結果は定義されていますか?
C / C++ の符号付き右シフトが特定のコンパイラの算術演算であることを確認しますか?
定数シフトのみを使用して可変ビットシフトをエミュレートしますか?

PPS この記事の投稿に協力してくれた Stack Exchange チームに感謝します。皆さん、最高です!

ベストアンサー1

バグはありますが、それはあなたが思っているようなものではありません。ドキュメンテーションのためにshr

x が負の整数の場合、shl および shr 演算は次の例で明確になります。

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 ビット値に符号拡張されます。つまり、この抜粋では、同じ出力の 2 行が生成されるはずです。

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定数値であるため評価しますが、コンパイラは論理シフトではなく算術シフトを使用して単純に誤って評価します。

ちなみに、このドキュメントには別の誤りがあります。それは、次のとおりです。

x shl y および x shr y の演算は、x の値を y ビット左または右にシフトします。これは (x が符号なし整数の場合)、x を 2^y で乗算または除算することと同等であり、結果は x と同じ型になります。

最後の部分は正しくありません。式は、8、16、または 32 ビット型のx shl y場合は 32 ビット型、それ以外の場合は 64 ビット型です。x


実際の目標は算術シフトを実装することなので、これはどれも重要ではありません。shlまたは は使用shrできません。算術シフトは自分で実装する必要があります。最終的には読みやすく検証しやすいと思われるので、インライン アセンブラを使用して実装することをお勧めします。

おすすめ記事