时间戳

首页 > 解决方案 > 求两个整数之间的偶校验数个数

c++ - 求两个整数之间的偶校验数个数

问题描述

我想找到两个整数之间的偶校验数。这是我到目前为止所写的：

#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)解决方案将不起作用。有没有更有效的ieO(1)解决这个问题？

标签： c++algorithm

解决方案

您所需要的只是一个从 [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 + parity(x)。

（你已经有了 parity(x) 函数）

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

它仅适用于正整数，但您也可以轻松地将逻辑扩展到负数。

推荐阅读