ロールオーバーする1バイトのインデックスでソート順が正しくなる

Question

組み込みシステムでは、1バイトの長さの配列インデックス（0-255、次に0にロールバック）を使用することに限定されています。配列は追加エントリを継続的に取得し続けますが、配列の全長は固定され、255よりはるかに小さくなります（たとえば5）。古い値は単純に上書きされます（FIFOスタック）。

通常、最近の最初の（または最後の）ソート順は、単純に配列インデックスの数値ソートです（7,8,9,10,11または17,18,19,20,21または124,125,126,127,128など）。 ）。

インデックスが255に達したときを除いて、ロールオーバーします。今、値はこのような場合に

253、254、255、0、1 OR 254、255、0、1、2

ような単純な番号順（0、1、253、254、255を見て）は、最近の最初の（または最後の）ソートではありません。

このような場合、正しい並べ替え順序を見つけるにはどうすればよいでしょうか？

Answer 1

何らかの形で「ローリング」のケース（整数オーバーフロー）があるかどうかをチェックし、補正する（補正を実行する）必要があります。

可能オーバーフローのチェック：

1. さんが言わせて、より大きな配列の要素があり、240
2. をあなたは配列でaddedとremovedブールフラグを保持します。それらを同じ値に初期化します。インデックスに0のアイテムが配列に追加されると、addedが反転します。インデックス255の項目が配列から削除されると、removedが反転します。値が等しい場合、オーバーフローが発生します。

補償：

1. signed char（またはint8_t）に自分の価値観をタイプキャスト。 127-128付近のインデックスでは機能しませんが、配列が小さいため安全です。
2. 一時的な配列を作成し、128を減算または加算して値の範囲の中央にシフトすると、比較することができます。同じ警告が適用されます。

Answer 2

コードでは、1バイトの開始インデックスと1バイトの終了インデックスを追跡できます。 1バイトのインデックスに2の補数演算を使用すると、（終了インデックス） - （開始インデックス）==配列サイズ。ラップアラウンドは問題になりません。