# Find the number of even parity numbers between two integers

I want to find the number of even parity numbers between two integers. Here is what I’ve written so far:

```#include <bits/stdc++.h>
using namespace std;
#define fastio
ios_base::sync_with_stdio(false);
cin.tie(NULL)
#define ll long long int

bool findParity(ll x)
{
ll y = x ^ (x >> 1);
y = y ^ (y >> 2);
y = y ^ (y >> 4);
y = y ^ (y >> 8);
y = y ^ (y >> 16);

if (y & 1)
return 1;
return 0;
}

void solve()
{
ll a,b; cin >> a >> b;
ll evenparity = 0;
for(ll i = a; i <= b; ++i){
if(findParity(i)==0) evenparity++;
}
cout << evenparity;
}

signed main()
{
fastio;
solve();
return 0;
}
```

This works fine. However, the difference between the two integers `a` and `b` can be as high as `10^11`, which means that an `O(n)` solution like this would not work. Is there a more efficient i.e `O(1)` solution to this problem?

## Answer

All you need is a function which calculates the even parity numbers from [0-x] interval, let’s call it sumParity, then simply return sumParity(b)-sumParity(a-1). (If I understood properly you are looking for the [a,b] closed interval.)

If start counting the parity from zero, and pair the numbers, (0-1), (2,3), (4,5) then each of these pairs has exactly 1 even and 1 odd parity. (These pairs only differ in the lowest bit).

So, if x is odd, then sumParity(x) = (x+1)/2, otherwise x/2 + parity(x).

(You already has the parity(x) function)

f(a,b) = sumParity(b)-sumParity(a-1)

It works only for positive integers, but you can easily extends the logic to negative numbers too.