☎️ 🆗 🧑🏼‍🤝‍🧑🏼 フォードを知らない、水に入ってはいけない。パート3 💟 🕛 👨🏻‍🏫

プログラマがそれを知らなくても、どのように端を歩き回るかについての話を続けます。シフト操作<<、>>について説明しましょう。シフト演算子の原理は明らかであり、多くのプログラマーは、C / C ++標準に従って使用すると未定義または未指定の動作（未定義の動作/未指定の動作）につながることさえ知りません。

以前の記事はここから入手できます：[ 1 ]、[ 2 ]。

歴史的遠足

初めに、少し歴史。ビットシフト操作の必要性は、プログラマーにとって明らかです。遅かれ早かれ、誰もが個々のビットとビットマスクを使用する必要に直面しています。ただし、せん断操作は本来あるべきよりもはるかに一般的です。その理由は、シフトを使用すると、数値を2の累乗で乗算および除算できるからです。たとえば、操作 "X << 3"はXに8を乗算します。この乗算および除算の方法の利点は、過去の作業の速度でした。

今、私は8086から80486で終わる、ほこりだらけの棚からプロセッサーのアセンブラー命令の説明を含む本を取りました。そして、さまざまな命令を完了するのに必要なクロックサイクル数の表を見つけました。

8086プロセッサでMUL命令を使用して16ビットレジスタとメモリセルを乗算するには、約124〜139クロックサイクルが必要です。

8086プロセッサでSHL命令を使用して16ビットレジスタをNポジションだけシフトするには、8 + 4 * Nサイクルが必要です。つまり、最悪の場合、72のメジャーが取得されます。

ビット演算を操作するときにさまざまなトリックを使用して算術式を計算すると、大幅な加速が得られました。これが、最初にアセンブラーで、次にCおよびC ++でシフトが広く使用される理由でした。最初のC / C ++コンパイラは単純でした。人は、乗算または除算命令ではなく、ここでシフトを使用する必要があることをコンパイラに明確に伝えることで速度を上げることができます。

プロセッサーの開発により、シフトを使用する利点は長く維持されています。 80486プロセッサでは、乗算に約26クロックサイクルかかりました。はるかに良いようです。しかし、シフトはたった3つの手段を取り始め、再び、乗算よりも魅力的でした。

幸いなことに、これらの強制された最適化の大部分は、忘却に陥りました。まず、コンパイラーはスマートになり、最適な命令セットを使用して算術式を計算します。第二に、プロセッサも大きく変化しました。パイプライン、遷移予測、レジスタの名前変更などがあります。そのため、普通のプログラマーは、1つまたは別の命令を実行するのにかかる時間を言うことができなくなりました。しかし、一部の場所でコードが完全でない場合、これに気付かないこともあります。プロセッサは、命令をマイクロ命令に分割し、それらを並行して実行し始めます。正直に言うと、私は今、すべてがそこで起こっていることを理解していません。 Intel Pentiumプロセッサから始めて、複雑さを理解するのは無意味であることに気付きました。そして彼は、可能な限り、最適化コードの記述方法、シフトとビット操作の使用方法をよく知っていると考えるべきではないと結論付けました。その結果、コンパイラのオプティマイザーよりもコードが高速になるという事実からはほど遠いです。しかし、あなたは間違いなくプログラムが混乱して理解しにくくなると言うことができます。

ご注意上記は、ビット演算の使用がもはや有益でないことを意味しません。多くの興味深い便利なトリックがあります[ 3 ]。主なことは、関与しないことです。

未定義の動作

すべては、未定義の動作[ 4 ]および未指定の動作[ 5 ]に関連するPVS-Studioアナライザーの警告の数を増やすことにしたという事実から始まりました。むしろ迅速かつ簡単に、シフト操作の不正使用を明らかにするルールが実装されました。その後、私は立ち止まって考えなければなりませんでした。

プログラマーは非常にシフトが好きであることがわかりました。そして、可能な限りあらゆる方法で使用され、多くの場合、標準の観点から未定義の動作に至ります。しかし、理論は一つのことであり、実践は別のことです。何十年も忠実に提供され、複数のコンパイラーを生き延びたコードを誓うことは理にかなっていますか？これは難しい質問です。コードが正しくないという事実にもかかわらず、コンパイラーはある種の暗黙の合意に従い、統一された方法で処理します。

よく考えた結果、この診断ルールを例外なくPVS-Studioに残すことにしました。ユーザーからの苦情が多すぎる場合は、気が変わるかもしれません。ただし、ユーザーはこの診断をオフにしたり、他の方法を使用してアラートを抑制したりする機能に満足していると思われます。

ところで、記事を書くように促したのは、これらの精神的苦痛でした。私が示す情報が興味深く、役に立つことを願っています。

それでは、シフト演算子に関するC ++ 11標準で書かれていることを見てみましょう。

シフト演算子<<および>>は、左から右にグループ化します。

シフト式<<加算式

シフト式>>加算式

オペランドは整数またはスコープなしの列挙型である必要があり、整数のプロモーションが実行されます。

1.結果の型は、昇格した左オペランドの型です。 右のオペランドが負の場合、または昇格した左のオペランドのビット長以上の場合、動作は未定義です。

2. E1 << E2の値は、E1を左にシフトしたE2ビット位置です。 空きビットはゼロで埋められます。 E1に符号なしの型がある場合、結果の値はE1 * 2 ^ E2で、結果の型で表現可能な最大値よりも1多いモジュロです。 それ以外の場合、E1に符号付きの型と負でない値があり、E1 * 2 ^ E2が結果の型で表現できる場合、それが結果の値です。 それ以外の場合、動作は未定義です。

3. E1 >> E2の値は、E1を右シフトしたE2ビット位置です。 E1に符号なしの型がある場合、またはE1に符号付きの型と負でない値がある場合、結果の値はE1 / 2 ^ E2の商の整数部になります。 E1に符号付きタイプと負の値がある場合、結果の値は実装定義です。

そのようなテキストを読むことは悲しいです。でも心配しないで。次に、例を使用してさまざまな誤った状況を検討します。

未定義の動作につながる最も単純なケースは、右側のオペランドの値が負の場合です。例：

  int A = 10;
 int B = A << -5;

だから誰も神に感謝しません。少なくとも、70を超えるオープンソースプロジェクトを分析した結果、このようなエラーは発生しませんでした。

次のケースは、はるかに興味深いものです。これはNビットのシフトです。ここで、Nは左オペランドのビット数よりも大きくなります。最も簡単な例：

  int A = 10;
 int B = A << 100;

そのような間違いが実際にどのように見えるかを見てみましょう。次のコードフラグメントは、Lib7zライブラリで発見されました。

  SZ_RESULT
 SafeReadDirectUInt64（ISzInStream * inStream、UInt64 *値）
 {
   int i;
   *値= 0;
   for（i = 0; i <8; i ++）
   {
    バイトb;
     RINOK（SafeReadDirectByte（inStream、＆b））;
     *値| =（（UInt32）b <<（8 * i））;
   }
   return SZ_OK;
 }

PVS-Studio診断メッセージ：V610未定義の動作。シフト演算子 '<<を確認してください。右側のオペランド（ '（8 * i）' = [0..56]）は、昇格した左側のオペランドのビット単位の長さ以上です。 lib7z 7zin.c 233

関数は、64ビット値をバイト単位で読み取ろうとします。残念ながら、数値が0x00000000FFFFFFFFFFより大きい場合、彼女は成功しません。シフト「（UInt32）b <<（8 * i）」に注意してください。左オペランドのサイズは32ビットです。この場合、シフトは0〜56ビットで発生します。実際には、64ビット値の古い部分がゼロで埋められたままになるという事実につながります。理論的には、ここには一般に未定義の動作があり、結果は予測できません。

正しいコードは次のようになります。

  *値| =（（UInt64）b <<（8 * i））;

読者は尋ねるかもしれませんが、以下のコードは正しいですか？

  char A = 1;
 int B = A << 20;

はい、正しいです。演算子<<の左側には、8ビットのみで構成される変数Aがあります。ただし、シフト操作の開始前に、左側がint型に展開されます。したがって、タイプ 'int'の値は20ビットシフトできます。

そして今、最も興味深い瞬間。これは負の値のシフトです。最も簡単な例：

  int A = -1 << 5;  //未定義の動作
 int B = -1 >> 5;  //不特定の動作

このコードでは、未定義および未指定の動作が発生します。実用的な観点からは違いはありません。結論は1つだけです。そのように書くことはできません。

これに終止符を打ち、いくつかの例を挙げることができます。残念ながら、世界の完全な絵を台無しにする2つのニュアンスがあります。

世界の完璧な絵を台無しにするニュアンス

ニュアンスN1。 1998年の古いC ++言語標準では、動作が未定義の状況は回避されます。符号なしの値をシフトするとき、演算子<<がどのように動作するかと言われています。しかし、象徴的な意味については何も言われていません。一般的に、これは標準を読んでも明確さを増さない場合です。そのような場合とはみなされず、それだけです。

したがって、1998年以降のC ++の観点からは、「-1 << 5」という構文は未定義の動作を引き起こしません。ただし、どのように機能するかについても説明していません。

ニュアンスN2。 プログラマは、多くのプログラムで負の値を大胆にシフトします。そして、コードが機能するため、彼らと議論することは困難です。

これらのニュアンスが原因で、新しい診断を拒否すべきかどうかを把握してみましょう。そうではないと思います。

古いC ++標準では、未定義の動作については言及されていません。新しい言う。古い基準は単に十分に正確ではなかったことが判明しました。ちなみに、新しいC言語標準（2010年6月25日のドラフトを見ました）では、負の値のシフトが未定義の動作につながるとも述べています。結論-誤ったコードを取り除く必要があります。

次に、危険なシフトの一般的な使用について。本当にたくさんあります。たとえば、JPEGライブラリでは、配列に次の値を入力する必要があります。

  1111111111111111111111111111111111111b
 1111111111111111111111111111111101101b
 1111111111111111111111111111111001b
 1111111111111111111111111111111110001b
 ...

次のように書かれています。

  / *エントリnは（-1 << n）+ 1 * /
 static const int extend_offset [16] = {0、
   （（-1）<< 1）+ 1、（（-1）<< 2）+ 1、（（-1）<< 3）+ 1、
   （（-1）<< 4）+ 1、（（-1）<< 5）+ 1、（（-1）<< 6）+ 1、
   （（-1）<< 7）+ 1、（（-1）<< 8）+ 1、（（-1）<< 9）+ 1、
   （（-1）<< 10）+ 1、（（-1）<< 11）+ 1、（（-1）<< 12）+ 1、
   （（-1）<< 13）+ 1、（（-1）<< 14）+ 1、（（-1）<< 15）+ 1
 };

JPEGライブラリを悪いと呼ぶのは難しい。そして、このコードは、時間とさまざまなコンパイラーによってテストされています。

標準の観点から、次のように書き換える必要があります。

  static const int extend_offset [16] =
 {0、
   （（〜0u）<< 1）|  1、（（〜0u）<< 2）|  1、（（〜0u）<< 3）|  1
   （（〜0u）<< 4）|  1、（（〜0u）<< 5）|  1、（（〜0u）<< 6）|  1
   （（〜0u）<< 7）|  1、（（〜0u）<< 8）|  1、（（〜0u）<< 9）|  1
   （（〜0u）<< 10）|  1、（（〜0u）<< 11）|  1、（（〜0u）<< 12）|  1
   （（〜0u）<< 13）|  1、（（〜0u）<< 14）|  1、（（〜0u）<< 15）|  1
 };

しかし、そのような編集を行う価値はありますか？私はそれをすべて同じようにアドバイスすることしかできません。それがいつ、どのように現れるかはわかりません。

異なるプログラムでの負の値のシフトの他の例を挙げることができます。しかし、それらはすべて同じタイプであるため、それらについて読むのは面白くありません。

結論

以前は、ビット演算とシフトの使用はプログラマースキルの兆候であり、高速なコードを書くことができました。今ではほとんど関係ありません。コードが理解できることがはるかに重要です。絶対に必要な場合にのみビートゲームを使用してください。
「-1 << N」という形式の式は無効と宣言され、未定義の動作が発生するようになりました。
「-1 << N」という形式の表現は、長い間頻繁に使用されてきました。したがって、そのような構造の使用に反対する真の議論をすることは困難です。引数は、CおよびC ++言語の新しい標準のみです。
負の値のシフトを修正するかどうかを自分で決めてください。しかし、修正をお勧めします。念のため。
危険なシフトに関する診断メッセージは、まもなくリリースされるバージョン4.60からPVS-Studioで利用可能になります。

追加のリソース

フォードを知らない、水に入ってはいけない。パート1 http://habrahabr.ru/post/137039/
フォードを知らない、水に入ってはいけない。パート2 http://habrahabr.ru/post/137411/
ショーン・エロン・アンダーソン。ビット調整ハック。 http://www.viva64.com/go.php?url=837
ウィキペディア未定義の動作。 http://www.viva64.com/go.php?url=663
ウィキペディア不特定の動作。 http://www.viva64.com/go.php?url=738
アレナC ++。不特定の動作と未定義の動作の違い。 http://www.viva64.com/go.php?url=739

フォードを知らない、水に入ってはいけない。 パート3

歴史的遠足

未定義の動作

世界の完璧な絵を台無しにするニュアンス

結論

追加のリソース

More articles:

フォードを知らない、水に入ってはいけない。パート3