Unfortunately we don't seem to have MathJax turned on in this stackexchange so the math parts below are pretty horribly formatted. I'm also far from a mathematician so the notation may be off in some places.
Understanding the magic number and code
The goal of the code above is to rewrite a division into a multiplication because division takes more clock cycles than a multiplication. It's in the area of about twice as many cycles, depending very much on CPU. So we need to find a nice branchless way of doing that. If we branch we're very likely to lose to simply doing division.
One way is to simply realize that division is the same as multiplication with the inverse of the number, i.e . The problem is that is a pretty poor number to store as an integer. So we need to multiply both the divisor and dividend by some number. Since we're operating on 32-bit numbers and we get multiplication results in 64-bit numbers we get the best precision with and we also avoid overflow issues. So we basically get . Now that fractional part is what causes us issues because it will cause rounding errors.
So let's try to formalize this:
Where is our multiplicand, e.g , or really any number but works very well with our register sizes as we can simply discard the lower 32-bit register. is the number you must add to make evenly divisible by . is the number we wish to divide.
We can rewrite the equation above, as
Which illustrates the point that we have our dividend divided by our divisor and then an error factor of .
Studying our original equation of it's clear that we can affect very little. needs to be a power of 2, can't be too large or we risk an overflow and can't be too small as it has a direct negative effect on our error factor . directly depends on and .
So let's try which gives a maximum error fraction of with the maximum value of being , so , unfortunately this is not less than so we can get rounding errors.
We'll increase the exponent of to , which gives , maximum error fraction which is less than . This means that our multiplicand is which is not less than or equal to the maximum signed value we can store in a 32-bit register (). So we instead make the multiplicand . As a side note, thanks to the magic of two's complement when we subtract the number is which is when interpreted as an unsigned number. But we're doing signed arithmetic here. So we need to fix the final expression by adding . This also only solves the problem for , for negative numbers we will be off by 1 so we need to add 1 if we have a negative number.
That's the explanation for the constant in the multiplication and how to arrive at it. Now let's look at the code:
; Load -1840700269
; Load n
; n * -1840700269
; add n to compensate for 2^32 subtraction
; check the sign bit of our result
; divide by 2^2 to compensate for us using y=2^34 instead of 2^32
; add the value of the sign bit to the final result
Calculating divisor from magic number and code
I have not proven this mathematically, however if you want to recover the divisor from an assembly dump such as the one you showed we can do some simple mental excercises. First we need to realize that the following holds
Where is the adjustment we made in order to bring the value into the range of a 32-bit value. From the code we can devise the following, the right shift by two means that we have , , , is unknown. This means that we're missing one variable in order to perform a perfect solution. However the effect of if negligible as its purpose is to bring the divisor as close to its integer value as possible. This means that the solution can be found by solving
Another example with divisor 31337 which has the multiplicand magic number 140346763 and right shifts 10 bits.
For a complete mathematical breakdown of how this works, including all the appropriate proofs and algorithms for calculating the magic numbers, shifts and adds, see Hacker's Delight, chapter 10-3.