按位除法取整到最近的零

Question

我希望进行一个有符号整数的按位除法，除数是2的幂次方。然而，我遇到了一些问题。我想知道是否有人能够帮助我。

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

int result = number >> n;

然而，当我尝试除以负数时出现了问题（它总是舍入为绝对值更大的数字。例如：-9/4=-3而不是-2）。于是，我在互联网上寻找解决方案，最终得到以下解决方案：

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

然而，当我尝试11/4 = 3而不是2时。有什么建议吗？我只能使用! ~ & ^ | + << >>（不允许使用循环或if / switch）。

- Jo Skorsev

---

你是在使用 / 来获得结果 还是 使用 >> 来执行等价的除法？ - Koushik Shetty

@Koushik，他说他只能使用这些运算符：！~&^|+<<>>。此外，不能使用循环或if条件/switch语句。 - Anish Ramaswamy

@Koushik 我正在调用函数 div(11,2) 来执行 11/4。 - Jo Skorsev

@AnishRam 我只是想确保他没有漏掉 /。现在我明白了。 - Koushik Shetty

一个有用的链接：https://dev59.com/92gt5IYBdhLWcg3w8h7e - Grijesh Chauhan

Answer 1

以下方法是不好的，因为它依赖于以下内容：

• 负整数的右移是算术右移（可能不是这种情况）
• 有符号整数采用二进制补码表示法（极少情况下可能不是这种情况）
• 整数没有填充位（现代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's complement-ness和填充位仍然存在局限性，但在今天的实践中几乎不存在）：

#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's complement 实现中，几乎总是以位对位复制的方式进行的。

- Alexey Frunze

---

你能解释一下你的 DivByShifting1 函数中的 n >> ((sizeof(int) * CHAR_BIT) - 1) 是什么意思吗？ - Anish Ramaswamy

@AnishRam 算术移位。当n >= 0时，它会给你0，当n < 0时，它会给你-1。 - Alexey Frunze

个人而言，我会使用在 return 语句中发生的从 unsigned 到 int 的实现定义转换，而不是 memcpy... - R.. GitHub STOP HELPING ICE

Answer 2

只需使用/运算符：

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

任何一个像样的编译器都会将其编译为最佳位移运算，并进行"四舍五入"负结果的修正。

- R.. GitHub STOP HELPING ICE

---

这个练习的目的是避免在源代码中使用显式除法。 - Alexey Frunze

或者它将使用 idiv，以确保更高的效率。 - Aki Suihkonen

是的，刚刚添加了一个版本，不依赖于 >> 的实现定义行为。 - Alexey Frunze

我在允许的运算符列表中没有看到强制转换。您可以使用 +0U 进行无符号转换，但是这样就没有办法进行转换而不需要强制转换或赋值了... - R.. GitHub STOP HELPING ICE

是的，我考虑过添加无符号0，但它是等价的，所以不是真正的问题。 - Alexey Frunze

Answer 3

也许这可以帮到你。

1) 如果你使用的是 / 运算符，则标准（ISO/IEC TR3 中的6.5.5乘法运算符）规定，/ 运算符的结果 是第一个操作数除以第二个操作数所得到的商。

2) 如果你使用的是 >>，则标准（ISO/IEC TR3 中的6.5.7）规定，在 LHS 操作数为有符号类型且为负数时，>> 的结果为 implementation defined。

因此，/ 将给出您所需的结果。

但是，在有符号和负数的情况下，对于 >>，取决于您的编译器。

- Koushik Shetty

Answer 4

从 int div(int a){return a/4;} 的反汇编来看：

leal 3(%rdi), %eax
testl %edi, %edi
cmovns %edi, %eax
sarl $2, %eax

只有当操作数为负数时，才需要通过 (1<<n)-1 调整操作数。

一个无条件的方法是使用 sgn(a)*(abs(a)>>n)；这两种方法都可以依靠实现定义行为的非分支位操作来实现。

- Aki Suihkonen