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                        
#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()
    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?


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.