22

減算する必要がある 2 つの unsigned int (x と y) があります。x は常に y より大きくなります。ただし、x と y はどちらもラップアラウンドできます。たとえば、両方ともバイトの場合、0xff の後に 0x00 が続きます。問題のケースは、x がラップ アラウンドし、y がラップしない場合です。x は y よりも小さいように見えます。幸いなことに、x は 2 回ラップアラウンドしません (1 回だけが保証されます)。バイトを仮定すると、x はラップされて現在 0x2 ですが、y はラップされておらず、0xFE です。x - y の正解は 0x4 のはずです。

多分、

( x > y) ? (x-y) : (x+0xff-y);

しかし、私は別の方法があると思います.2sの補数を含むものですか?そして、この組み込みシステムでは、xとyが最大のunsigned int型であるため、0xffを追加することはできません.

ステートメントを記述する最良の方法は何ですか (ターゲット言語は C です)。

4

8 に答える 8

35

2 つの符号なし整数を想定すると、次のようになります。

  • 一方が他方よりも「大きい」はずであることがわかっている場合は、差し引いてください。2回以上ラップしていなければ機能します（明らかに、ラップした場合はわかりません）。
  • 一方が他方よりも大きいことがわからない場合は、結果を減算して、同じ幅の符号付き int にキャストします。2 つの違いが signed int の範囲内であれば機能します (そうでない場合は、わかりません)。

明確にするために：元のポスターによって説明されたシナリオは人々を混乱させるようですが、ハードウェアのティックカウンターやプロトコルのシーケンス番号など、単調に増加する固定幅カウンターの典型です。カウンタは (たとえば 8 ビットの場合) 0xfc、0xfd、0xfe、0xff、0x00、0x01、0x02、0x03 などになります。x と y の 2 つの値のうち、x は後で来ることがわかります。x==0x02 および y==0xfe の場合、計算 xy (8 ビットの結果として) は、2 つのnビット値の減算が modulo 2 nをラップすると仮定すると、4 の正しい答えを返します。符号なしの値。(注: C 標準では、符号付き値の減算に対するこの動作は保証されていません。)

于 2010-01-14T00:13:09.863 に答える
22

「大きい」から「小さい」を差し引いたときに「うまくいく」理由をもう少し詳しく説明します。

これにはいくつかの要素があります...<br> 1. ハードウェアでは、減算は加算を使用します。適切なオペランドは、加算される前に単純に否定されます。
2. 2 の補数 (ほぼすべてが使用) では、整数はすべてのビットを反転してから 1 を追加することによって否定されます。

ハードウェアは、上記の説明から聞こえるよりも効率的にこれを実行しますが、これが減算の基本アルゴリズムです (値が符号なしの場合でも)。

では、8 ビットの符号なし整数を使用して 2 – 250 を計算してみましょう。バイナリでは、

  0 0 0 0 0 0 1 0  
- 1 1 1 1 1 0 1 0

減算されるオペランドを否定してから加算します。否定するには、すべてのビットを反転してから 1 を加算することを思い出してください。2 番目のオペランドのビットを反転すると、次のようになります。 

0 0 0 0 0 1 0 1

次に、1を追加すると、 

0 0 0 0 0 1 1 0

次に、追加を実行します...

  0 0 0 0 0 0 1 0   
+ 0 0 0 0 0 1 1 0

= 0 0 0 0 1 0 0 0 = 8, which is the result we wanted from 2 - 250
于 2010-05-27T14:43:10.340 に答える
13

わからないかもしれませんが、何が問題なのですか？

unsigned r = x - y;

于 2010-01-14T00:02:19.993 に答える
3

述べたように、質問は紛らわしいです。あなたは符号なしの値を減算していると言いました。あなたが言ったように、xが常に よりも大きい場合は、ラップアラウンドまたはオーバーフローすることはできません。だからあなたは（それがあなたが必要とするものなら）それをするだけです。yx - yx - y

于 2010-01-14T00:16:28.010 に答える
2

これは、循環バッファ内の空き領域の量を決定したり、ウィンドウのフロー制御をスライディングしたりする効率的な方法です。とunsigned intに s を使用します - それらをインクリメントしてラップさせます! バッファー長は 2 の累乗でなければなりません。headtail

free = ((head - tail) & size_mask)、ここsize_maskで 2^n-1 はバッファまたはウィンドウ サイズです。

于 2011-09-22T06:47:14.863 に答える
1

すでに正しい答えをコードに入れるだけです：

x の方が小さいことがわかっている場合は、次の計算が機能します。

int main()
{
    uint8_t x = 0xff;
    uint8_t y = x + 20;
    uint8_t res = y - x;
    printf("Expect 20: %d\n", res); // res is 20

    return 0;
}

どちらが小さいかわからない場合:

int main()
{
    uint8_t x = 0xff;
    uint8_t y = x + 20;
    int8_t res1 = (int8_t)x - y;
    int8_t res2 = (int8_t)y - x;
    printf("Expect -20 and 20: %d and %d\n", res1, res2);

    return 0;
}

この場合、差は の範囲内にある必要がありますuint8_t。

コードの実験は、ソリューションをよりよく理解するのに役立ちました。

于 2017-08-15T11:27:55.810 に答える
0

他の全員の返信に合わせて、2 つを差し引いて結果を署名なしと解釈すれば問題ありません。

明確な反例がない限り。

の例はx = 0x2、 にy= 0x14はなりません。数学に明示されていない制約がない限り、 になります0x4。0xEE

于 2010-01-14T00:54:54.530 に答える