# What does this magic number do? [duplicate]

I've opened a 64 bit DLL file in IDA. One function has this pseudocode:

``````unsigned __int64 output;
ULONG input;
output = (unsigned __int64)(input * (unsigned __int128)0xE38E38E38E38E38Fui64 >> 64) >> 5;
``````

Here is the equivalent assembly view:

``````mov     rcx, r13
mov     [rsp+56], rcx
mov     edx, [rsp+152]
mov     rax, 0E38E38E38E38E38Fh
mul     rdx
mov     r8, rdx
shr     r8, 5
mov     [r15], r8d
cmp     r8d, esi
cmova   r8d, ebx
``````

When I want to compile that same code in MSVC++, it shows:

``````warning C4293: '>>': shift count negative or too big, undefined behavior
``````

My question is, what does that long constant value do? Is there anything cryptic with that bit shifting?

although I flagged this question should be closed as duplicate, keeping it has some additional value because of the multiple different magic number values used, redirecting users encountering different magic values to the same resource.

On modern processors, integer division is one of the slowest arithmetic operations you can have a processor perform. Often orders of magnitude slower than other arithmetic operations.

It turns out that if divisor is constant you can avoid the expensive division operation using clever arithmetic tricks to a set of considerably faster operations (multiplications, additions and shifts), thus reaching overall faster performance at the expense of slightly larger code.

This is often called "division by magic numbers" because those numbers indeed often look like randomly selected numbers, that is not, however, the case. Compilers (and sometimes humans, too) use those tricks often nowadays, since size of code is less of an issue thanks to the exponential growth of storage capacity.

The general approach is that we can develop an equation like the following:

`X / Y == X * (1/Y) == sqrt((X * 2^n) * (1/Y)), 2^n) == ((x << n) * 1/Y)>>n`

In your case, `0xE38E38E38E38E38Fui64` with a shift of `3` bits is the hardcoded magic number used for division by 9 for unsigned 64 bit integers. Since your code actually shifts by 5, the actual divisor equals `9 * 2^2` = `36`.

• Somehow `0xE38E38E38E38E38Fui64 >> 64) >> 5` is equivalent with `divided by 36`. May you explain that in your answer? Aug 24, 2018 at 21:23
• Ah. Yes. I didn't notice the arithmetic shift in your code is 5 instead of the expected shift by 3. The additional shift by two bits means you're actually dividing by `9*2^2 = 9*4 = 36` Aug 24, 2018 at 21:25
• But, diving by 9 and multiplying by 0xE38... will not be same as the second one 1/9 isn't finite. Aug 24, 2018 at 21:41
• Those are close approximations that work for integers. You're correct it will not work when you assign the result into a floating point variable. Aug 24, 2018 at 21:48