c - 按位除法舍入到最接近的零

Question

我想按位除以 2 的幂的有符号整数。但是，我遇到了几个问题。我只是想知道是否有人可以帮助我。

首先，我尝试单独使用位移位:

int result = number >> n;

但是，当我尝试除负数时遇到了问题。 (它总是用一个更大的数字四舍五入。例如:-9/4=-3 而不是 -2。所以，我在互联网上查看这个问题，最终得到了这个解决方案:

int result = (number + (1<<n)-1) >> n;

但是，当我尝试 11/4 = 3 而不是 2

有什么建议吗？我只能用! ~ & ^ | + << >>(不允许循环或 if/switch)

Answer 1

下面的方法不好，因为它依赖于:

• 负整数的右移是算术移位(可能不是这种情况)
• 有符号整数以 2 的补码表示(极少数可能不是这种情况)
• 没有任何填充位的整数(现在在现代 CPU 上你找不到填充位，尽管标准允许它们存在)

并且由于有符号整数溢出，它可能会导致某些股息(例如 INT_MIN)出现未定义的行为。

因此它不可移植，也不能保证始终有效。您已收到警告。

#include <stdio.h>
#include <limits.h>

int DivByShifting1(int n, unsigned shift)
{
  int sgn = n >> ((sizeof(int) * CHAR_BIT) - 1);
  return ((((n + sgn) ^ sgn) >> shift) + sgn) ^ sgn;
}

int main(void)
{
  int n, s;
  for (n = -10; n <= 10; n++)
    for (s = 0; s <= 4; s++)
      printf("%d / %d = %d\n", n, 1 << s, DivByShifting1(n, s));
  return 0;
}

输出(ideone):

-10 / 1 = -10
-10 / 2 = -5
-10 / 4 = -2
-10 / 8 = -1
-10 / 16 = 0
-9 / 1 = -9
-9 / 2 = -4
-9 / 4 = -2
-9 / 8 = -1
-9 / 16 = 0
-8 / 1 = -8
-8 / 2 = -4
-8 / 4 = -2
-8 / 8 = -1
-8 / 16 = 0
-7 / 1 = -7
-7 / 2 = -3
-7 / 4 = -1
-7 / 8 = 0
-7 / 16 = 0
-6 / 1 = -6
-6 / 2 = -3
-6 / 4 = -1
-6 / 8 = 0
-6 / 16 = 0
-5 / 1 = -5
-5 / 2 = -2
-5 / 4 = -1
-5 / 8 = 0
-5 / 16 = 0
-4 / 1 = -4
-4 / 2 = -2
-4 / 4 = -1
-4 / 8 = 0
-4 / 16 = 0
-3 / 1 = -3
-3 / 2 = -1
-3 / 4 = 0
-3 / 8 = 0
-3 / 16 = 0
-2 / 1 = -2
-2 / 2 = -1
-2 / 4 = 0
-2 / 8 = 0
-2 / 16 = 0
-1 / 1 = -1
-1 / 2 = 0
-1 / 4 = 0
-1 / 8 = 0
-1 / 16 = 0
0 / 1 = 0
0 / 2 = 0
0 / 4 = 0
0 / 8 = 0
0 / 16 = 0
1 / 1 = 1
1 / 2 = 0
1 / 4 = 0
1 / 8 = 0
1 / 16 = 0
2 / 1 = 2
2 / 2 = 1
2 / 4 = 0
2 / 8 = 0
2 / 16 = 0
3 / 1 = 3
3 / 2 = 1
3 / 4 = 0
3 / 8 = 0
3 / 16 = 0
4 / 1 = 4
4 / 2 = 2
4 / 4 = 1
4 / 8 = 0
4 / 16 = 0
5 / 1 = 5
5 / 2 = 2
5 / 4 = 1
5 / 8 = 0
5 / 16 = 0
6 / 1 = 6
6 / 2 = 3
6 / 4 = 1
6 / 8 = 0
6 / 16 = 0
7 / 1 = 7
7 / 2 = 3
7 / 4 = 1
7 / 8 = 0
7 / 16 = 0
8 / 1 = 8
8 / 2 = 4
8 / 4 = 2
8 / 8 = 1
8 / 16 = 0
9 / 1 = 9
9 / 2 = 4
9 / 4 = 2
9 / 8 = 1
9 / 16 = 0
10 / 1 = 10
10 / 2 = 5
10 / 4 = 2
10 / 8 = 1
10 / 16 = 0

请注意 ((sizeof(int) * CHAR_BIT) - 1) 是编译时常量，因此 * 和 - 可以被允许。

另一个版本，非常相似，但不需要负整数右移算术移位，并且没有符号整数溢出(2 的补码和填充位仍然是限制，但在今天几乎不存在实践):

#include <stdio.h>
#include <limits.h>
#include <string.h>

int DivByShifting2(int n, unsigned shift)
{
  unsigned un = n;
  unsigned sgn = 1 + ~(un >> ((sizeof(int) * CHAR_BIT) - 1));
  un = ((((un + sgn) ^ sgn) >> shift) + sgn) ^ sgn;
  memcpy(&n, &un, sizeof n);
  return n;
}

int main(void)
{
  int n, s;
  for (n = -10; n <= 10; n++)
    for (s = 0; s <= 4; s++)
      printf("%d / %d = %d\n", n, 1 << s, DivByShifting2(n, s));
  return 0;
}

输出(ideone):

-10 / 1 = -10
-10 / 2 = -5
-10 / 4 = -2
-10 / 8 = -1
-10 / 16 = 0
-9 / 1 = -9
-9 / 2 = -4
-9 / 4 = -2
-9 / 8 = -1
-9 / 16 = 0
-8 / 1 = -8
-8 / 2 = -4
-8 / 4 = -2
-8 / 8 = -1
-8 / 16 = 0
-7 / 1 = -7
-7 / 2 = -3
-7 / 4 = -1
-7 / 8 = 0
-7 / 16 = 0
-6 / 1 = -6
-6 / 2 = -3
-6 / 4 = -1
-6 / 8 = 0
-6 / 16 = 0
-5 / 1 = -5
-5 / 2 = -2
-5 / 4 = -1
-5 / 8 = 0
-5 / 16 = 0
-4 / 1 = -4
-4 / 2 = -2
-4 / 4 = -1
-4 / 8 = 0
-4 / 16 = 0
-3 / 1 = -3
-3 / 2 = -1
-3 / 4 = 0
-3 / 8 = 0
-3 / 16 = 0
-2 / 1 = -2
-2 / 2 = -1
-2 / 4 = 0
-2 / 8 = 0
-2 / 16 = 0
-1 / 1 = -1
-1 / 2 = 0
-1 / 4 = 0
-1 / 8 = 0
-1 / 16 = 0
0 / 1 = 0
0 / 2 = 0
0 / 4 = 0
0 / 8 = 0
0 / 16 = 0
1 / 1 = 1
1 / 2 = 0
1 / 4 = 0
1 / 8 = 0
1 / 16 = 0
2 / 1 = 2
2 / 2 = 1
2 / 4 = 0
2 / 8 = 0
2 / 16 = 0
3 / 1 = 3
3 / 2 = 1
3 / 4 = 0
3 / 8 = 0
3 / 16 = 0
4 / 1 = 4
4 / 2 = 2
4 / 4 = 1
4 / 8 = 0
4 / 16 = 0
5 / 1 = 5
5 / 2 = 2
5 / 4 = 1
5 / 8 = 0
5 / 16 = 0
6 / 1 = 6
6 / 2 = 3
6 / 4 = 1
6 / 8 = 0
6 / 16 = 0
7 / 1 = 7
7 / 2 = 3
7 / 4 = 1
7 / 8 = 0
7 / 16 = 0
8 / 1 = 8
8 / 2 = 4
8 / 4 = 2
8 / 8 = 1
8 / 16 = 0
9 / 1 = 9
9 / 2 = 4
9 / 4 = 2
9 / 8 = 1
9 / 16 = 0
10 / 1 = 10
10 / 2 = 5
10 / 4 = 2
10 / 8 = 1
10 / 16 = 0

@R.. 正确地提醒，从 signed int 到 unsigned int 的转换可以通过添加 0u(unsigned 0)来完成。

而且他还提醒，un可以直接返回，而不是对n做memcpy()。转换应该是实现定义的，但在 C 的 2 的补码实现中，实际情况总是逐位复制。