5

基本的に、整数を減算でオーバーフローさせたときに得られる動作ですが、特定のビット数に対してです。符号付き整数を想定した明白な方法：

template <int BITS>
int sub_wrap(int v, int s) {
  int max = (1<<(BITS));
  v -= s;
  if (v < -max) v += max*2;
  // or if branching is bad, something like:
  // v += (max*2) * (v < -max)
  return v;
}

// For example subtracting 24 from -16 with 5 bit wrap,
// with a range of -32, 31
sub_wrap<5>(-16, 28); -> 20

上記のものよりも醜くなく、できれば高速である、それを行うためのきちんとした方法はありますか？

更新：混乱について申し訳ありません。ため息ビットを除いたビット数を使用するという紛らわしい表記を無意識に含めました。したがって、上記では、5ビットを6ビットに置き換えて、より多くの健全性を実現します。

4

4 に答える 4

8

符号なし演算の場合、結果をマスクします。例:

template<int bits>
unsigned
sub_wrap( unsigned v, unsigned s )
{
    return (v - s) & ((1 << bits) - 1);
}

より一般的には、モジュロ演算子を使用できます。

template<int modulo>
unsigned
sub_wrap( unsigned v, unsigned s )
{
    return (v - s) % modulo;
}

(ビットのラッピングnは、モジュロ 2^n と同等です。)

符号付き演算の場合は、もう少し複雑です。マスクを使用すると、結果を符号拡張する必要があります (2 の補数を想定)。

編集：符号付き算術に対するseheの提案の使用：

template<int bits>
int
sub_wrap( int v, int s )
{
    struct Bits { signed int r: bits; } tmp;
    tmp.r = v - s;
    return tmp.r;
}

これを考えると、次のようになりsub_wrap<5>( -16, 28 )ます-12(これは正しい28です。5 ビットの signed int として表現できないことに注意してください)。sub_wrap<6>( -16, 28 )を与え20ます。

于 2011-11-29T11:10:56.030 に答える
5

私はこれがうまくいくはずだと思います：

 struct bits
 {
     signed int field : 5;
 };

 bits a = { -16 };     
 bits b = {  28 };

 bits c = { a.field - b.field };
 std::cout << c.field << std::endl;

フィールド幅は const テンプレート引数では機能しないと確信しています...したがって、これはあまり一般的ではありません。ただし、手動での調整は避ける必要があります。すぐにテストを投稿します

更新結局、私の答えは間違っていなかったことがわかりました。サンプル入力 (28) を 5 ビット (符号付き) で表すことができないというだけです。上記の結果は -12 です ( http://ideone.com/AUrXyを参照)。

完全を期すために、テンプレート化されたバージョンを次に示します。

template<int bits>
int sub_wrap(int v, int s)
{
    struct helper { signed int f: bits; } tmp = { v };
    return (tmp.f -= s);
}
于 2011-11-29T10:56:42.903 に答える
2

条件分岐と乗算なしで行う方法は次のとおりです。

#include <stdio.h>

// Assumptions:
// - ints are 32-bit
// - signed ints are 2's complement
// - right shifts of signed ints are sign-preserving arithmetic shifts
// - signed overflows are harmless even though strictly speaking they
//   result in undefined behavior
//
// Requirements:
// - 0 < bits <= 32
int sub_wrap(int v, int s, unsigned bits)
{
  int d = v - s;
  unsigned m = ~0u >> (32 - bits);
  int r = d & m | -((d >> (bits - 1)) & 1) & ~m;
  return r;
}

#define BITS 2

int main(void)
{
  int i, j;
  for (i = -(1 << (BITS - 1)); i <= (1 << (BITS - 1)) - 1; i++)
    for (j = -(1 << (BITS - 1)); j <= (1 << (BITS - 1)) - 1; j++)
      printf("%d - %d = %d\n", i, j, sub_wrap(i, j, BITS));
  return 0;
}

出力：

-2 - -2 = 0
-2 - -1 = -1
-2 - 0 = -2
-2 - 1 = 1
-1 - -2 = 1
-1 - -1 = 0
-1 - 0 = -1
-1 - 1 = -2
0 - -2 = -2
0 - -1 = 1
0 - 0 = 0
0 - 1 = -1
1 - -2 = -1
1 - -1 = -2
1 - 0 = 1
1 - 1 = 0
于 2011-11-29T12:47:12.810 に答える
1

This simulates an n bit integer operation:

#include <iostream>
#include <cstdlib>

template< typename T >
T sub_wrap(T a, T b, int nBits)
{
        T topBit, mask, tmp;

        topBit=T(1) << (nBits-1);
        mask=(topBit << 1)-1;
        tmp=((a&mask)+((~b+1)&mask))&mask;
        if (tmp & topBit) tmp=-((~tmp&mask)+1);

        return tmp;
}

int main(int argc, char* argv[])
{
        std::cout << sub_wrap< int >(atoi(argv[1]), atoi(argv[2]), atoi(argv[3]))
                << std::endl;
        return 0;
}

Results:

$ ./sim 5 6 4
-1
$ ./sim 7 3 4
4
$ ./sim 7 -1 4
-8
$ ./sim -16 28 4
4
$ ./sim -16 28 5
-12
$ ./sim -16 28 6
20

Seems you miscalculated your type size by 1 bit.

于 2011-11-29T11:15:50.637 に答える