This question already has an answer here:

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?

marked as duplicate by NirIzr, Community Aug 24 at 21:29

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

up vote 2 down vote accepted

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? – Biswapriyo Aug 24 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 – NirIzr Aug 24 at 21:25
  • But, diving by 9 and multiplying by 0xE38... will not be same as the second one 1/9 isn't finite. – Biswapriyo Aug 24 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. – NirIzr Aug 24 at 21:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.