I always use this line in my code to find if a number is even or odd, i once find it in a book : for a given integer x
if(x & 1 == 1){//then x is odd}
But actually i’m wondering how it can be demonstrate, pls your help is wellcome.
I always use this line in my code to find if a number is even or odd, i once find it in a book : for a given integer x
if(x & 1 == 1){//then x is odd}
But actually i’m wondering how it can be demonstrate, pls your help is wellcome.
The binary representation of a number can be thought of as a binary vector, s.t., we can arrive at the decimal equivalent by simply adding up the index^{th} powers of 2 weighted by the binary values at the corresponding indices.
Here of course, the weights happen to \in \mathbb{B}
\implies include the power in your sum
if 1
and don't include the power in your sum
if 0.
We can only arrive at even numbers, by adding up a couple of 2 ^ x's, s.t., x > 0.
If the value at the 0 ^ {th} index of the binary vector is 1, it would mean:
include 2^0 in your sum as well!
If we include that, we all know what that means: even + 1 = odd. Since, 1 = 2 ^ 0 it means that, if the bit at position 0 is set, it is an odd number.
So, how do we check if the bit at position 0 is set? Well, we try to form a black box resulting in binary responses: 1 if the 0 ^ {th} bit is set and 0 otherwise.
What if we \& our binary vector with another one of the same size, with only the 0 ^ {th} bit set? It would return itself if our binary vector has its 0 ^ {th} bit set or a vector of 0's otherwise.
Now, 1 = the binary vector with only the 0 ^ {th} bit set. So, the comparison ==
would evaluate to true iff x is odd and false if it is even.
Hope this helps.
It’s very clear, maybe it’s because you used vector to explain it , Now can you tell me which one is fastest? That line or this one :
if(x % 2){// then x is odd}
I used to hear that the % operator is slow.
Thank a lot in advance
Yes, the modulo operator is sort of slow.
if (x & 1) {
// x is odd
} else {
// x is even
}
I’d suggest using these little tricks only if the modulo operator gives you a TLE or if you are just playing around, trying to make your code the fastest code submitted because,
“Clarity is no. 1 priority”.