按位除法向最接近零的舍入

12 浏览
0 Comments

按位除法向最接近零的舍入

我想对一个2的次幂进行有符号整数位除法。 但是，我遇到了几个问题。 我想知道是否有人可以帮助我。

首先，我尝试仅使用位移：

int result = number >> n;

但是，当我尝试除以负数时，我遇到了一个问题。（它总是舍入为具有更大数值的数字。例如：-9/4=-3而不是-2。因此，我在互联网上查找了这个问题，这是我最终的解决方案：

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

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

有什么建议吗？ 我只能使用！~&^|+<< >>（不允许使用循环或if / switch）

admin 更改状态以发布 2023年5月24日
0

2 答案

0 Comments

只需使用/运算符：

int result = number / (1 << n);

任何好的编译器都会将其编译为优化的位移（bitshift）并进行"四舍五入"负结果的修正。

0
0 Comments

以下方法是糟糕的，因为它依赖于以下因素：

  • 负整数的右移位是算术右移（可能不是这种情况）
  • 有符号整数处于2的补码表示中（极其罕见可能不是这种情况）
  • 整数没有任何填充位（在现代CPU上，您不会找到填充位，尽管标准允许它们的存在）

并且由于有符号整数溢出，它可能会导致一些除数（例如INT_MIN）的未定义行为。

因此，它不是可移植的，并且不保证始终有效。您已被警告。

#include 
#include 
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 
#include 
#include 
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..正确地提醒，可以通过添加0u（无符号0）来将signed int转换为unsigned int。

他还提醒可以直接返回un，而不是对n执行memcpy()。转换应该是实现定义的，但在C的2的补码实现中，几乎总是按位复制。

0