And operator

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. :sweat_smile:

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. :slightly_smiling_face:


It’s very clear, maybe it’s because you used vector to explain it :smile:, 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 :heart_eyes:

1 Like

Yes, the modulo operator is sort of slow.

Here's the code that's faster
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”. :slightly_smiling_face:

1 Like