Modulo operation in C#, C and OCaml -

i wanted confirm modulo operation expensive operation tested piece of code checks if given number even:

bool is_even(int n) {     return (n & 1) == 0; } 

then one:

bool is_even_bis(int n) {     return (n % 2) == 0; } 

i used c# @ first , indeed, code using logical & faster other one, 3 times faster. using ilspy saw there no optimization done when compiled msil, code strictly same.

however spotted friend of mine in c, using gcc -o3 code compiled to:

is_even:     mov     eax, dword ptr [esp+4]  # tmp63, n     ,     eax, 1  # tmp63,     xor     eax, 1  # tmp63,     ret 

and:

is_even_bis:     mov     eax, dword ptr [esp+4]  # tmp63, n     ,     eax, 1  # tmp63,     xor     eax, 1  # tmp63,     ret 

so strictly same thing. when using -o0 optimization operation doesn't appear:

is_even:     push    ebp     #     mov     ebp, esp        #,     mov     eax, dword ptr [ebp+8]  # tmp63, n     ,     eax, 1  # d.1837,     test    eax, eax        # d.1837     sete    al      #, d.1838     movzx   eax, al # d.1836, d.1838     pop     ebp     #     ret 

needlessly compiled code same between is_even , is_even_bis in -o0 well.

even more funny if may say, friend of mine tried same using ocaml:

let is_even x = ((x land 1) == 0)  let _ =    let = ref 100000000 in   while !i > 0     ignore (is_even !i);     decr   done 

and:

let is_even_bis x = ((x mod 2) == 0)  let _ =    let = ref 100000000 in   while !i > 0     ignore (is_even_bis !i);     decr   done 

and appears modulo version faster when running bytecode slower in native code! maybe can explain mystery?

then started wondering why not behave in c# (where there obvious gap of performance between 2 functions) , why jit compiler not apply same optimization gcc. don't know if there's way intercept output of jit compiler, maybe understand?

bonus question : guess modulo based on division , since division done in o(n²) time (n being number of digits) can modulo has quadratic time complexity?

firstly, there no concept of speed these operations, in portable sense. assertions might true your system, they're invalid all systems. reason, it's quite pointless speculating on micro-optimisations. can find far more significant optimisations producing program solves meaningful problem, profiling find parts of code take execution time , introducing faster algorithms times. faster algorithms, mean better data structures (or less operations), opposed different operators. stop focusing on micro-optimisations!

your c version of is_even isn't well-defined. might produce negative zeros or trap representations, particularly negative numbers. using trap representation undefined behaviour.

it seems though difference might seeing caused signed integer representation on system. consider if -1 represented using ones complement 11111111...11111110. you'd expect -1 % 2 result in -1, not 0, wouldn't you? (edit: ... expect -1 & 1 result in, if -1 represented 11111111...11111110?) there needs overhead, handle implementations use ones complement signed integer representation.

perhaps c compiler has noticed % expression used , & expression used equivalent on system, , result made optimisation, optimisation hasn't been performed c# or ocaml compilers whatever reason.

bonus question : guess modulo based on division , since division done in o(n²) time (n being number of digits) can modulo has quadratic time complexity?

there no point contemplating time complexity of these 2 basic operations, because they'll differ system system. covered in first paragraph.