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.