(!(n&1)) or n%2==0

1

Is adding (!(n&1)) more efficient than adding n%2==0.
Both are one and the same thing but does the time complexity reduces if i use !(n&1) instead of n%2==0

1 Like
2

since computer use binary(0 or1) so !(n&1) is more effiecient as it works on bit
whereas while doing modulus first it convert both numbers into binary then do modulus then again convert back into decimal which took some time

2 Likes
3

yes both are same but bitwise & operator is faster than modulo …
in cf there is a very simple question to check whether n is odd or even …when i try with modulo operator it take 30ms but when i use bitwise & it takes only 15ms.

1 Like
4

I guess i have to use binary then !

5

yeah if u r comfortable :slight_smile:

1 Like
6

With g++ 7.5 on my laptop, I get:

[simon@simon-laptop][20:19:59]
[~/devel/hackerrank/otherpeoples]>cat check-even-bitwise.cpp 
#include <iostream>

using namespace std;

int main()
{
    int x;
    int numEven = 0;
    while (cin >> x)
    {
        if (!(x & 1))
            numEven++;
    }
    cout << numEven << endl;

}
[simon@simon-laptop][20:20:06]
[~/devel/hackerrank/otherpeoples]>cat check-even-modulus.cpp 
#include <iostream>

using namespace std;

int main()
{
    int x;
    int numEven = 0;
    while (cin >> x)
    {
        if (x % 2 == 0)
            numEven++;
    }
    cout << numEven << endl;

}
[simon@simon-laptop][20:20:11]
[~/devel/hackerrank/otherpeoples]>g++ check-even-bitwise.cpp -O3 -S -Wall -Wextra
[simon@simon-laptop][20:20:17]
[~/devel/hackerrank/otherpeoples]>g++ check-even-modulus.cpp -O3 -S -Wall -Wextra
[simon@simon-laptop][20:20:20]
[~/devel/hackerrank/otherpeoples]>diff check-even-modulus.s check-even-bitwise.s 
1c1
<       .file   "check-even-modulus.cpp"
---
>       .file   "check-even-bitwise.cpp"

so no difference with this particular example at -O3.

Edit:

Ah, I missed that you were adding the resulting values, so this doesn’t really show anything.

4 Likes
7

So basically when I am using bitwise it becomes very confusing , that is why I want to know whether the efforts are worth it ? Does using bitwise reduce time ?

8

In the example I’ve given above, it doesn’t seem to, but @ssrivastava990’s experience suggests otherwise :man_shrugging:

People have done similar experiments here:

My opinion - not really worth caring about - in the hundreds of problems I’ve done, I’ve never encountered one where using n & 1 vs n % 2 is the difference between TLE and AC :slight_smile:

2 Likes
9

What if we use big numbers as large as
10^9

10

Again, in the example I’ve used, it makes no difference - the code generated is identical no matter which you use.

2 Likes
11

no no…@ssjgz i just said there will be a littile bit difference …but not as much that using modulo it will get TLE and by using & it will AC :slight_smile:

2 Likes