resta entera con envoltura para N bits

Question

Básicamente, el comportamiento que se obtiene al desbordar enteros con sustracción, pero para un número determinado de bits. La manera obvia, asumiendo una firmaron entero:

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 

¿Hay una clara forma de hacerlo que es menos feo y preferiblemente más rápida que la de arriba?

ACTUALIZACIÓN: Perdón por la confusión. Inconscientemente incluí la notación confusa de usar la cantidad de bits excluyendo el bit de suspiro. Entonces, en lo anterior, reemplace 5 bits con 6 bits para una mayor cordura.

Answer 1

supongo que esto debería funcionar:

struct bits 
{ 
    signed int field : 5; 
}; 

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

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

Estoy bastante seguro de la anchura del campo no funcionará con un argumento de plantilla const ... y por lo tanto esto es menos genérico. Sin embargo, debería evitar retoques manuales. Fijará prueba pronto

actualización Resulta que mi respuesta no era incorrecta después de todo. Es solo que la entrada de muestra (28) no se puede representar en 5 bits (firmado). El resultado de lo anterior es -12 (ver http://ideone.com/AUrXy).

Aquí es decir, por la totalidad, una versión de plantilla después de todo:

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

Answer 2

para la aritmética sin signo, y la máscara de los resultados, por ejemplo:

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

De manera más general, se puede utilizar el operador de módulo :

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

(Envoltura en n bits es el equivalente de módulo 2^n.)

Para la aritmética con signo, es un poco más complejo; usando la máscara, tendrás que firmar extender los resultados (suponiendo complemento de 2).

EDIT: El uso de la sugerencia de sehe para la aritmética firmado:

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

Dado esto, sub_wrap<5>(-16, 28) da -12 (que es correcta — nota que 28 no se puede representar como int firmado en 5 bits); sub_wrap<6>(-16, 28) da 20.

Answer 3

Esto simula una operación poco entero 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; 
} 

Resultados:

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

parece que calculó mal el tamaño de su tipo en 1 bit.

Answer 4

Así es como yo lo haría w/o saltos condicionales y multiplicación:

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

Salida:

-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