Sottrazione di interi con wrap around per N bit

Question

Fondamentalmente, il comportamento si ottiene quando si superano gli interi con sottrazione, ma per un dato numero di bit. Il modo più ovvio, assumendo una firmato intero:

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 

C'è un modo pulito di farlo che è meno brutto e preferibilmente più veloce di quello di cui sopra?

AGGIORNAMENTO: Mi dispiace per la confusione. Ho incluso senza pensieri la notazione confusa dell'uso del numero di bit escludendo il bit di sigh. Quindi, in precedenza, sostituisci 5 bit con 6 bit per una maggiore sanità mentale.

Answer 1

Suppongo che questo dovrebbe funzionare:

struct bits 
{ 
    signed int field : 5; 
}; 

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

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

Sono abbastanza sicuro che la larghezza del campo non funziona con un argomento di template const ... e quindi questo è meno generico. Dovrebbe, tuttavia, evitare di armeggiare manualmente. Presto manderò presto il test

Aggiornamento Alla fine la mia risposta non è stata errata. È solo che l'input di esempio (28) non può essere rappresentato in 5 bit (firmato). Il risultato di quanto sopra è -12 (vedi http://ideone.com/AUrXy).

Ecco, per completezza, una versione su modelli, dopo tutto:

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

Answer 2

per l'aritmetica senza segno, e mascherare i risultati, ad esempio:

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

Più in generale, è possibile utilizzare l'operatore modulo :

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

(Wrapping su n bit è l'equivalente di modulo 2^n.)

Per l'aritmetica firmata, è un po 'più complesso; usando la maschera, dovrai firmare estendere i risultati (supponendo il complemento a 2).

EDIT: Usando il suggerimento di sehe per aritmetica firmata:

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

Detto questo, sub_wrap<5>(-16, 28) dà -12 (che è corretto — nota che 28 non può essere rappresentato come int firmato a 5 bit); sub_wrap<6>(-16, 28) dà 20.

Answer 3

Questo simula un n un'operazione bit integer:

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

Risultati:

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

Sembra che tu calcolato male la dimensione tipo di 1 bit.

Answer 4

Ecco come lo farei w/o rami condizionali e la moltiplicazione:

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

uscita:

-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