I'm a bit confused. So I need to iterate all shift values, but how can I check if the condition holds if I don't know the value of N? Should I assume the highest value possible for it that it can have? I mean, N is a runtime value, only the divisor is at compile time.

And also if I divide 2^32 by 641, the remainder is 640, not 1, so how come it works?
(...)
EDIT: I'm guessing P is not the remainder, but rather D-remainder, am I right? I looked before at your example with 10, and you said P = 4, which fits just as well as on 641. (i.e. 10-6 = 4, and 641-640 = 1)

test al, 1
jnz .no
imul eax, eax, 0xAAAAAAAB
cmp eax, 0x55555555
ja .no    

Code:

        imul    edx,19h
        mov     ecx,edx
        mov     edx,09999999Ah    

imul ecx,edx,19h    

Tomasz Grysztar wrote:

Code:

        imul    edx,19h
        mov     ecx,edx
        mov     edx,09999999Ah    

Why give edx the value and move to ecx rather than

Code:

imul ecx,edx,19h    

?

A related question. What's the best (fastest, in general) way to check if a number is divisible by a constant? Sure, I can use the division here, and see if the result multiplied with the divisor is equal to the original value... but that's 2 muls. So I found this here: https://math.stackexchange.com/questions/1251327/is-there-a-fast-divisibility-check-for-a-fixed-divisor

MACRO DisplayNumber in
  LOCAL number  
  number = in scale 0  
    IF number < 0  
      DISPLAY '-'  
      number = -number  
    END IF  
    REPEAT 1, n:number  
      DISPLAY `n  
    END REPEAT  
END MACRO 

virtual at 0
        HexDigits:: db '0123456789ABCDEF'
end virtual
macro DisplayHex val*,bytes:0
        local chars
        if bytes
                chars = 2*bytes
        else
                chars = 2 + 2*((bsr (val))/8)
        end if
        repeat chars
                load digit:byte from HexDigits: ((val) shr ((%%-%) shl 2)) and 0Fh
                display digit
        end repeat
end macro

struc egcd: a,b
        local t
        if a = 0
                .gcd = b
                .x = 0
                .y = 1
        else
                . egcd (b mod a),a
                t := .x
                .x = (.y - (b / a) * .x)
                .y = t
        end if
end struc

macro fast_div d*,w*
        local m,j, _d,t

        m = 1 shl w

        j = bsf d
        _d = d shr j

        if j > 0
                display 'n << '
                DisplayNumber w-j
                display ' == 0',13,10
        end if
        if _d > 1
                t egcd _d,m
                display 'n * '
                DisplayHex t.x mod m, w shr 3
                display ' <= '
                DisplayHex m / _d, w shr 3
                display 13,10
        end if
end macro

fast_div 76,64    

A related question. What's the best (fastest, in general) way to check if a number is divisible by a constant? Sure, I can use the division here, and see if the result multiplied with the divisor is equal to the original value... but that's 2 muls. So I found this here: https://math.stackexchange.com/questions/1251327/is-there-a-fast-divisibility-check-for-a-fixed-divisor

And today I found a publication about an even better method of divisibility checking:
https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/
The "lkk_divisible" method from the paper works for even divisors as well as for the odd ones.

return n * c <= c - 1;    

return n * c < c;    

revolution, transforming n * c <= c - 1 to n*c < c has problems when c = 0. Apparently the code is supposed to work in the very important case of testing divisibility by 1
In seriousness, if c a compile time constant, compilers can figure out the validity of the transformation and apply it.