将有符号整数除以2的幂 [英] Divide a signed integer by a power of 2

问题描述

我正在研究一种仅使用二进制运算符(<< >> >> + ^〜& |！)将有符号整数除以2的幂的方法，结果必须取整为0.我在Stackoverflow上也遇到了这个问题，但是，我不明白为什么会起作用.解决方法如下:

I'm working on a way to divide a signed integer by a power of 2 using only binary operators (<< >> + ^ ~ & | !), and the result has to be round toward 0. I came across this question also on Stackoverflow on the problem, however, I cannot understand why it works. Here's the solution:

int divideByPowerOf2(int x, int n)
{
    return (x + ((x >> 31) & ((1 << n) + ~0))) >> n;
}

我理解x >> 31部分(仅在x为负数时添加下一部分，因为如果它为正数，x会自动舍入为0).但是困扰我的是(1 << n) + ~0部分.如何运作?

I understand the x >> 31 part (only add the next part if x is negative, because if it's positive x will be automatically round toward 0). But what's bothering me is the (1 << n) + ~0 part. How can it work?

推荐答案

假定2补码，仅对红利进行位移运算就等于某种除法:不是传统的除法，我们将红利四舍五入到下一个整数倍.除数趋于零.但是另一种形式是，我们将股息向负无穷大舍入.我在Smalltalk中重新发现了它，请参见 http://smallissimo.blogspot.fr/2015/03/is-bitshift-equivalent-to-division-in.html .

Assuming 2-complement, just bit-shifting the dividend is equivalent to a certain kind of division: not the conventional division where we round the dividend to next multiple of divisor toward zero. But another kind where we round the dividend toward negative infinity. I rediscovered that in Smalltalk, see http://smallissimo.blogspot.fr/2015/03/is-bitshift-equivalent-to-division-in.html.

例如，让我们将-126除以8.传统上，我们会写

For example, let's divide -126 by 8. traditionally, we would write

-126 = -15 * 8 - 6

但是，如果我们向无穷大舍入，我们将得到正余数并将其写成:

But if we round toward infinity, we get a positive remainder and write it:

-126 = -16 * 8 + 2

就位模式而言​​，移位正在执行第二个操作(假设为8位长int为简短起见):

The bit-shifting is performing the second operation, in term of bit patterns (assuming 8 bits long int for the sake of being short):

1000|0010 >> 3 = 1111|0000
1000|0010      = 1111|0000 * 0000|1000 + 0000|0010

那么，如果我们要让商除为零的传统除法，并且余数与股息相同，该怎么办?很简单，我们只需要在商中加1-当且仅当股息为负且除法不精确时.

So what if we want the traditional division with quotient rounded toward zero and remainder of same sign as dividend? Simple, we just have to add 1 to the quotient - if and only if the dividend is negative and the division is inexact.

您看到x>>31对应于第一个条件，假设int具有32位，则除数为负.

You saw that x>>31 corresponds to first condition, dividend is negative, assuming int has 32 bits.

如果除法不精确，则第二项对应于第二个条件.

The second term corresponds to the second condition, if division is inexact.

查看如何在两个补码中对-1，-2，-4，...进行编码:1111 | 1111、1111 | 1110、1111 | 1100.因此，n的2的幂次幂的取反有n个尾随零.

See how are encoded -1, -2, -4, ... in two complement: 1111|1111 , 1111|1110 , 1111|1100. So the negation of nth power of two has n trailing zeros.

当被除数有n个尾随零并且我们除以2 ^ n时，则无需在最终商上加1.在其他情况下，我们需要添加1.

When the dividend has n trailing zeros and we divide by 2^n, then no need to add 1 to final quotient. In any other case, we need to add 1.

(((1<< n)+〜0)正在创建带有n个尾随掩码的掩码.

What ((1 << n) + ~0) is doing is creating a mask with n trailing ones.

最后n位无关紧要，因为我们将向右移动并扔掉它们.因此，如果除法是精确的，则除数的n个尾随位为零，我们只需添加将跳过的n个1.相反，如果除法不精确，则被除数的n个尾随位中的一个或多个为1，因此我们确定对n + 1个位进行进位运算:这就是将商加1的方法(我们将2 ^ n加到股息中).可以解释更多吗?

The n last bits don't really matter, because we are going to shift to the right and just throw them away. So, if the division is exact, the n trailing bits of dividend are zero, and we just add n 1s that will be skipped. On the contrary, if the division is inexact, then one or more of the n trailing bits of the dividend is 1, and we are sure to cause a carry to the n+1 bit position: that's how we add 1 to the quotient (we add 2^n to the dividend). Does that explain it a bit more?

这篇关于将有符号整数除以2的幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！