Divide a signed integer by a power of 2

Question

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;
}

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?

Answer 1

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.

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

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

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.

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.

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.

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.

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

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?

Answer 2

This is "write-only code": instead of trying to understand the code, try to create it by yourself.

For example, let's divide a number by 8 (shift right by 3). If the number is negative, the normal right-shift rounds in the wrong direction. Let's "fix" it by adding a number:

int divideBy8(int x)
{
    if (x >= 0)
        return x >> 3;
    else
        return (x + whatever) >> 3;
}

Here you can come up with a mathematical formula for whatever, or do some trial and error. Anyway, here whatever = 7:

int divideBy8(int x)
{
    if (x >= 0)
        return x >> 3;
    else
        return (x + 7) >> 3;
}

How to unify the two cases? You need to make an expression that looks like this:

(x + stuff) >> 3

where stuff is 7 for negative x, and 0 for positive x. The trick here is using x >> 31, which is a 32-bit number whose bits are equal to the sign-bit of x: all 0 or all 1. So stuff is

(x >> 31) & 7

Combining all these, and replacing 8 and 7 by the more general power of 2, you get the code you asked about.

---

Note: in the description above, I assume that int represents a 32-bit hardware register, and hardware uses two's complement representation to do right shift.