c++ - N 位环绕的整数减法

Question

基本上，您在减法溢出整数时得到的行为，但对于给定的位数。显而易见的方法，假设一个有符号整数:

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

有没有比上面的方法更简洁、速度更快的巧妙方法？

更新:对于造成的困惑，我们深表歉意。我不假思索地包含了令人困惑的符号，即使用不包括叹息位的位数。所以在上面，用 6 位替换 5 位以获得更多的理智。

Answer 1

对于无符号算术，屏蔽结果，例如:

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 位的有符号整数)； sub_wrap<6>( -16, 28 )给出 20 .