按位除法舍入到最接近的零 [英] bitwise division rounding to nearest zero

问题描述

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

I want to perform an signed integer bitwise division by a power of 2. However, I encounter several problem. I just wonder if anyone can help me.

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

First, I try to use bit shifting alone:

int result = number >> n;

但是，当我尝试对负数进行除法时遇到问题.(它总是以更大的数字取整.例如:-9/4 = -3而不是-2.因此，我在互联网上看到了这个问题，最终得到了以下解决方案:

However, I got a problem when I try to divide a negative number. (it always round with a number with bigger magnitude. example: -9/4=-3 instead of -2. So, I look this problem in the internet, that end me up with this solution:

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

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

However, when I try 11/4 = 3 instead of 2

有什么建议吗?我只能用！〜&^ |+<<>>(无循环或是否允许/切换)

Any suggestions? I can only use ! ~ & ^ | + << >> (no loop or if/switch allowed)

推荐答案

以下方法是错误的，因为它依赖于:

The following method is bad because it relies on:

• 负整数的右移是算术移位(可能不是这种情况)
• 带符号的整数以2的补码表示(极少数情况可能并非如此)
• 没有任何填充位的整数(尽管标准允许存在填充位，但在现代CPU上，如今这些日子都找不到)

由于有符号整数溢出，它可能导致某些除数(例如 INT_MIN )上的不确定行为.

And it may cause undefined behavior on some dividends (e.g. INT_MIN) due to signed integer overflow.

因此，它不是便携式的并且不能保证始终工作.您已被警告.

Therefore it isn't portable and isn't guaranteed to work always. You have been warned.

#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)是一个编译时常量，因此 * 和-可以被允许.

Note that ((sizeof(int) * CHAR_BIT) - 1) is a compile-time constant and therefore * and - can be allowed.

另一种版本，非常相似，但是不需要将负整数右移就可以算术移位，并且没有带符号整数溢出(2的补码和填充位仍然是局限性，但是在今天的版本中实际上已不存在练习):

Another version, which is very similar, but does not require right shifts of negative integers to be arithmetic shifts and is free of signed integer overflow (2's complement-ness and padding bits are still limitations, but virtually in-existent in today's practice):

#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 ..正确地提醒您，可以通过添加0u(无符号0)来完成从 signed int 到 unsigned int 的转换.

@R.. rightfully reminds that the conversion from a signed int to an unsigned int can be done by adding 0u (unsigned 0).

他还提醒说，可以直接返回 un 而不是对 n 执行 memcpy().转换应该是实现定义的，但是在C的2的补码实现中，按位复制实际上总是这种情况.

And he also reminds that un can be returned directly instead of doing memcpy() to n. The conversion should be implementation-defined, but in 2's complement implementations of C, bit-for-bit copy is practically always the case.

这篇关于按位除法舍入到最接近的零的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！