Nビットのラップアラウンドを伴う整数減算

Question

基本的には、減算を使用して整数をオーバーフローさせたときの動作を所定のビット数で取得します。明白な方法は、を仮定すると、符号付き整数：以下醜いと上記の1よりも高速であることを行うためのきちんとした方法は、

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ビットで置き換え、より多くの正気性を確保しています。

Answer 1

私は、これは動作するはずとします

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> 
unsigned 
sub_wrap(unsigned v, unsigned s) 
{ 
    return (v - s) & ((1 << bits) - 1); 
} 

、あなたはモジュロ演算子を使用することができます。例えば、

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

Answer 2

符号なし算術演算のために、結果をマスク：

ここ結局のところテンプレートバージョン、完全を期すため、あります：

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

（2の剰余に相当するビットは、^n。）

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

はEDIT：署名された演算に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)が得られる（28は5ビットで符号付き整数として表現することができない—音符が正しい）-12。 sub_wrap<6>(-16, 28)は20となる。

Answer 3

これは、nビットの整数演算シミュレート：

#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; 
} 

結果：

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

は、あなたが1ビットであなたのタイプのサイズを誤算ようです。ここで

Answer 4

は、I/Oの条件分岐と乗算wはそれを行うだろう方法は次のとおりです。

#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