How to distinguish odd and even for big numbers more efficiently?

Please let me know by comments if there are already some similar questions.

When we usually try to distinguish odd and even numbers we can try the following code,
in C++.

    int main() {
        int n=10;
        
        for(n; n>0; n--){
            
            if(n%2==0) std::cout<< "even" << '\n';
            if(n%2==1) std::cout<< "odd" << '\n';      
        }   
    }

I’m sure more than 99% of undergraduates, even professionals, would use condition as "if (n%2==0)…else" to distinguish between odd and even.

However, when the range of number gets big enough, it seems to me that "if (n%2==0)…else" method could be quite inefficient. Let me reason them why.

 int main() {
        int n=100000;
        
        for(n; n>0; n--){
            
            if(n%2==0) std::cout<< "even" << '\n';
            if(n%2==1) std::cout<< "odd" << '\n';      
        }   
    }

when the integer "n" was small then dividing each of positive integer smaller than it wasn’t a big deal.

However, when it becomes big, wouldn’t there be some more efficient way than just dividing them?

We, humans, usually don’t calculate modulo 2 to know whether "10^1000 + 1" is odd or even.
It goes same for ""10^1000 + 2", "10^1000 + 3", and so on. We can just know the answer by looking at the last digit of integer.

I’m not an expert in CS, so even though I’m not sure about this information, I heard machines are much more friendly to binary numbers than humans do. If so, wouldn’t computers can distinguish between odd and even numbers more faster just by looking at the last digit of their inputs, whether they are 0 or 1?

If there is some direct answer to this, I’m sure many of intermediate level of numerical algorithms could benefit from the answer. Looking forward for someone’s help.

Thanks.

>Solution :

Is the performance time for 50000000%2 and 5%2 really the same?

This is making the assumption that the compiler "looks at the number" and "knows" how big its value is. Thats not the case for divisions. The compiler sees an int and performs some operations on that int. Different values are merely different bits set in that int which always has the same number of bytes that need to be considered when carrying out a division.

On the other hand, %2 is such a common operation that the compiler indeed "knows where to look": The last bit.

Consider this two functions:

bool is_odd1(int n) { return (n%2);} 
bool is_odd2(int n) { return (n&1);}

Both return true when n is odd.

is_odd1 uses % which is defined as remainder after division. Though, just because it is defined like that does not imply that it must be implemented like this. The compiler will emit code that produces the result in accordance with the definition, and that code can be expected to be very efficient.

is_odd2 only considers the lowest bit of n to check if it is set or not.

With optimizations turned on gcc produces exact same output for both:

is_odd1(int):
        mov     eax, edi
        and     eax, 1
        ret
is_odd2(int):
        mov     eax, edi
        and     eax, 1
        ret

Both function do nothing but check if the lowest bit of n is set.

Live Demo.

Conclusion: Do not worry about such micro optimizations. If possible they are implemented in the compiler. Rather write code for clarity and readability.

However, do not introduce inefficiencies on the large scale. For example if you had written your code like this, there would be no need to rely on compiler optimizations:

    for(; n>0; n-=2){
        std::cout<< "even" << '\n';
        std::cout<< "odd" << '\n';      
    } 

Though, this is anyhow not a good example, because printing something to the console is magnitudes more expensive than checking if a single bit is set or not.