求两个整数之间的偶校验数的个数

Question

我想找出两个整数之间的偶校验数的个数。以下是我到目前为止写的内容：

#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;
}

这可以很好地工作。但是，两个整数a和b之间的差异可以高达10^11，这意味着像这样的O(n)解决方案将无法工作。对于这个问题，有没有更有效的解决方案，比如O(1)？

Answer 1

您只需要一个函数来计算0-x区间的偶数奇偶校验数，让我们称它为sumParity，然后简单地返回sumParity(b)-sumParity(a-1)。(如果我理解正确的话，您正在寻找a，b闭合区间。)

如果从零开始计算奇偶校验，并将数字(0-1)、(2,3)、(4,5)配对，则这些对中的每一对恰好具有1个偶数和1个奇数。(这些对仅在最低位不同)。

因此，如果x是奇数，则sumParity(x) = (x+1)/2，否则x/2 +奇偶校验(X)。

(您已经有了奇偶校验(X)函数)

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

它只适用于正整数，但您也可以很容易地将逻辑扩展到负数。

Answer 2

每对偶数/奇数整数恰好包含一个偶奇偶数。

因此，只需检查a和b是否为偶奇偶数，并查看它们是否构成自己的偶/奇数对，并对中间对进行计数就足够了。这是O(1)。