c - 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?