mov ecx,2
div ecx ;for dword
div ecx ;for word
idiv eax,ecx,2 ;for immediate only idiv is available    

Are you sure about that? Intel's docs indicate a syntax like the above for IMUL, but not DIV nor IDIV. There is AAM imm8 which performs a divide of AH:AL by an immediate byte, but it doesn't work in 64-bit mode.

; eax = your number
mov edx, 0xAAAAAAAB
mul edx
shr edx, 1
; edx = output, eax/3    

An alternative to division by a constant is to do a "inverse" multiplication, since a constant is "known" and can be converted to an inverse multiplication by another constant which is faster.

If you want to divide by the odd number, and you know the number you want to divide is divisible without remainder, you can do this by multiplying by "magic" number and take the LOW half of the result, without need to do any shifts etc.

This approach is based on the theory of 2-adic numbers, if you need some elementary information on 2-adic number, you can find it in the Programming Tutorial I've once started.

For example, the 2-adic reciprocal of 3 is 110101010101... (infinite chain), if we multiply any integer N divisible by 3 by such infinite chain, we will get N/3. On computer we are able to operate only on finite chains, but note, that even when multiplying the infinite ones, the n first bits always depends only on the first n bits of both numbers we multiply. So if we take the first 32 bits of 2-adic 1/3 and multiply the 32-bit integer by it, the low 32 bits of the result will be the correct first 32 bits of the result, N/3 in this case.

The first 32 bits of infinite 1/3 expansion are 0AAAAAAABh (and the whole expansion goes as if we were adding infinite amount of A digits to the left), therefore this code:

Code:

mov eax,N
mov ebx,0AAAAAAABh
mul ebx    

will calculate the N/3 for us in EAX.

When you want to divide by even number, you can factorize it to some power of two and odd number, then make one multiplication like above and then shift by the amount of bits equal to the power of two from the factorization. Always operating on the lower half of the result! This means you can use this method also with the IMUL instruction variants, which give you only the lower half of the result, like:

Code:

imul eax,0AAAAAAABh ; divide by 3    

However this method has the substantial flow, that the number we want to divide has to be divisible by the value, whose reciprocal we use - otherwise we get the low bits of some infinite expansion of rational number.

The method discussed above doesn't have such disadvantage. But let's see how the two methods are related to each other. If you use Svin's tool to get the magic number for dividing by 3, you will see that it's actually the same as the low 32 bits of p-adic 1/3 we used above. But this time you are told to get the HIGH 32 bits of result and shift them right by one bit.

Indeed, if you check it, when you multiply by 0AAAAAAABh the 32-bit N divisible by 3, you will get N/3 in low 32 bits, and 2N/3 in the high 32 bits. To see how the 2-adic arithmetics can explain this, let's analyze in terms of p-adic rational numbers, what you exactly get, when you do such multiplication. The 0AAAAAAAB is incomplete 1/3, what we cut off is the infinite amount of A digits starting from ninth one (33rd bit), therefore:

N*0AAAAAAABh = N*(1/3 - ...AAA00000000h)

note now that ...AAA00000000h = ...AAAAh * 100000000h = ...AAAAh * (2^32)
but ...AAAAh = ...AAABh - 1 = 1/3 - 1 = -2/3, so:

N*0AAAAAAABh = N * (1/3 - (-2/3)*(2^32)) = N*3 + (2N/3)*(2^32)

so we get exactly what we expected - after multiplyng by 0AAAAAAABh we get N/3 in low 32 bits and 2N/3 in the high bits.

But how does it come, that even when N is not divisible by 3, we get the correct rounded value of N/3 starting from the 34th bit?
If N=M+r, where r<3, then we can split the N*0AAAAAAABh into sum of two products - for M we know we get 2M/3 in upper bits, so it suffices to show that r*0AAAAAAABh has zeros starting from the 34th bit - what is actually evident, since r is smaller than 2^2 and the 0AAAAAAABh is smaller than 2^32, so their product is smaller than 2^34. Well, there might be some overflow when M is very large, near to 2^32, but that's another story - I'm providing only very simplified analysis on single example, but I believe the analogous reasoning works for the general case.

Also, for the small values of M, the "middle" bits, just below the result in high bits, would even allow to recover the remainder from division - though I doubt it could be done efficiently. But if I design any nice algorithm for this, I'll let you know.

I hope I have not bored everyone with those theoretical divagations...