Divide the signed integer by 2

Question

I am working on how to split a signed integer by 2 using only binary operators (<<→ + ^ ~ and |!), And the result should be rounded to 0. I came across this question and Stackoverflow on this issue. however, I cannot understand why this works. Here's the solution:

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

I understand the part x >> 31 (add only the next part if x negative, because if it is positive, x will automatically round to 0). But the part (1 << n) + ~0 worries me. How it works?

Answer 1

Assuming 2-padding, just a dividend bit-shift is equivalent to a certain type of division: non-conditional division, where we round the dividend to the next multiple divisor to zero. But another view, where we turn the dividend to negative infinity. I rediscovered this in Smalltalk, see http://smallissimo.blogspot.fr/2015/03/is-bitshift-equivalent-to-division-in.html .

For example, let them divide -126 by 8. Traditionally, we will write

 -126 = -15 * 8 - 6 

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

 -126 = -16 * 8 + 2 

A bit shift performs a second operation with respect to bit patterns (assuming 8 bits of int length for short):

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

So, what if we want the traditional division with rounding to be rounded to zero and remain the same sign as a dividend? Simply, we just need to add 1 to the quotient - if and only if the dividend is negative and the division is inaccurate.

You saw that x>>31 matches the first condition, the dividend is negative if int has 32 bits.

The second term corresponds to the second condition if the division is inaccurate.

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

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

Which ((1 <n) + ~ 0) makes creating a mask with n finite.

The last n bits do not matter much because we are going to move to the right and just throw them away. So, if the division is accurate, the n final bits of the dividends are zero, and we just add n 1s to be skipped. Conversely, if the division is inaccurate, then one or more of the n final bits of the dividend is equal to 1, and we will necessarily cause the transfer to the position n + 1 bits: how do we add 1 to the quotient (we add 2 ^ n to the dividend). Does this explain a little more?

Answer 2

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

For example, let it divide the number by 8 (shift right by 3). If the number is negative, normal right shifts in the wrong direction. Let it “fix” it by adding a number:

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

Here you can find a mathematical formula for whatever or perform a trial and trial version. Anyway, here whatever = 7 :

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

How to combine 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 bit sign of x : all 0 or all 1. So, stuff is

 (x >> 31) & 7 

Combining all this and replacing 8 and 7 with a more general power of 2, you will get the code you requested.

---

Note: in the above description, I assume that int represents a 32-bit hardware register, and the hardware uses two additional representations to shift to the right.

Answer 3

The OP reference has C# code and there are so many subtle differences that cause it to have bad C code because this message is tagged.

int not necessarily 32 bits, so using a magic number of 32 does not provide a reliable solution.

In particular, (1 << n) + ~0 leads to the implementation of a certain behavior when n causes the bit to move to the place of the sign. Incorrect coding.

Code restriction only when using binary operators << >> + ^ ~ & | ! << >> + ^ ~ & | ! prompts the encoder to assume things about int that are not portable or compatible with the C specification. Thus, the OP code does not work at all, although it can work in many common implementations.

OP code does not work if int not 2 padding and does not use the range [-2147483648 .. 2147483647] or when 1 << n uses implementation behavior that was not as expected.

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

The following is a simple alternative, assuming long long exceeds int range. I doubt that this meets a certain angle of the objectives of the OP, but the OP sets goals, encourages unreliable coding.

 int divideByPowerOf2(int x, int n) { long long ill = x; if (x < 0) ill = -ill; while (n--) ill >>= 1; if (x < 0) ill = -ill; return (int) ill; }