Phép trừ số nguyên với bọc xung quanh cho N bit

Question

Về cơ bản, hành vi bạn nhận được khi tràn các số nguyên trừ, nhưng đối với một số bit nhất định. Cách rõ ràng, giả sử một ký số nguyên:

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ó cách gọn gàng để làm việc đó có nghĩa là ít xấu xí và tốt nhất là nhanh hơn so với một ở trên?

CẬP NHẬT: Xin lỗi về sự nhầm lẫn. Tôi vô tình bao gồm các ký hiệu khó hiểu về việc sử dụng số lượng bit không bao gồm tiếng thở dài. Vì vậy, ở trên, thay thế 5 bit với 6 bit cho rất nhiều sanity.

Answer 1

Tôi cho rằng điều này sẽ làm việc:

struct bits 
{ 
    signed int field : 5; 
}; 

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

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

Tôi chắc rằng chiều rộng lĩnh vực sẽ không làm việc với một mẫu đối số const ... và do đó đây là ít chung. Nó nên, tuy nhiên, tránh tinkering thủ công. Sẽ đăng bài kiểm tra sớm

Cập nhật Cuối cùng, câu trả lời của tôi không đúng. Nó chỉ là đầu vào mẫu (28) không thể được đại diện trong 5 bit (đã ký). Kết quả của phần trên là -12 (xem http://ideone.com/AUrXy).

Đây là, cho đầy đủ, một phiên bản templated sau khi tất cả:

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

Answer 2

Đối với số học unsigned, và mặt nạ kết quả, ví dụ:

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

Tổng quát hơn, bạn có thể sử dụng toán tử modulo :

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

(Gói trên n bit tương đương với modulo 2^n.)

Đối với số học đã ký, nó phức tạp hơn một chút; bằng cách sử dụng mặt nạ, bạn sẽ phải đăng ký mở rộng kết quả (giả sử bổ sung 2).

EDIT: Sử dụng gợi ý sehe cho số học ký:

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

Vì điều này, sub_wrap<5>(-16, 28) cho -12 (đó là chính xác — lưu ý rằng 28 không thể được biểu diễn dưới dạng ký int trong 5 bit); sub_wrap<6>(-16, 28) cấp 20.

Answer 3

này mô phỏng một n bit số nguyên hoạt động:

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

Kết quả:

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

Có vẻ bạn tính nhầm kích thước kiểu của bạn bằng 1 bit.

Answer 4

Đây là cách tôi muốn làm điều đó w/o chi nhánh và nhân có điều kiệ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; 
} 

Output:

-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