N位整数的循环减法

Question

N位整数的循环减法

5

基本上，这是指当整数减去一个给定的比特位数时会发生的行为，类似于使用减法处理溢出的整数。假设使用有符号整数，那么明显的方法是：

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个位以获得更多理智。

- porgarmingduod

你还需要检查 v >= max。 - interjay

3

-32到31的范围需要6位二进制表示，而不是5位。 - TonyK

这完全取决于你的观点。我只是习惯于在我目前使用的代码中表示除符号位外的位数，但我猜那只会让人感到困惑。 - porgarmingduod

4个回答

5

我认为这应该可以工作：

 struct bits
 {
     signed int field : 5;
 };

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

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

更新：结果表明我的答案并不是错误的。只是样本输入（28）无法用5位（有符号）表示。以上的结果是-12（请参见http://ideone.com/AUrXy）。
为了完整起见，这里还是提供一个模板版本:
~~我很确定以const为模板参数的域宽度不起作用... 因此这个代码不够通用。然而，这应该避免手动调整。将很快发布测试结果~~。

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

- sehe

另一方面，将字段分配回来，然后从“struct”返回该字段会起作用。这可能是有符号值的最简单解决方案。 - James Kanze

如所写，它不起作用，但如果您声明位域为“signed int”，将计算出的值赋回到其中，然后从位域返回该值，它应该可以工作（对我而言确实如此）。 - James Kanze

位域字段的默认符号（signed）或无符号（unsigned）取决于具体实现。 - interjay

@JamesKanze：唉。我在这里有些困惑。我已经重新分配到位域（c.field…），但是OP的示例选择得不好。 - sehe

+1 模板化位域！https://dev59.com/b3VD5IYBdhLWcg3wI3-L#1771843 - Kaz Dragon

显示剩余2条评论

2

以下是我不使用条件分支和乘法的方法：

#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

- Alexey Frunze

1

这是一个模拟 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 位。

- hochl

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- James Kanze · Accepted Answer

对于无符号算术，需要对结果进行掩码处理，例如：

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。