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.

CodePudding user response：

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.

CodePudding user response：

If you look at a number written in decimal, you can know quickly whether it is odd or even:

• if it ends with 0, 2, 4, 6, or 8, then it is even;
• if it ends with 1, 3, 5, 7, or 9, then it is odd.

Numbers on a computer are stored in binary. Binary is almost the same as decimal, except it uses base-2 instead of base-10, and thus uses only bits 0 or 1 instead of digits 0 to 9.

To check whether a number written in binary is odd or even, look at its last bit:

• if it ends with 0, then it is even;
• if it ends with 1, then it is odd.

When you write n % 2 == 0 is C , your compiler optimises the code and doesn't perform a division at all. Instead, it simply looks at the last bit of n and checks whether it is a 0 or a 1.