我想求两个整数之间的偶数奇偶数的个数。以下是我目前所写的内容：
#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)解决方案来解决这个问题？
每对偶数/奇数整数正好包含一个偶数奇偶数。
因此，只要检查a和b是否为偶数奇偶数，看看它们是否对自己的偶数/奇数对有贡献，并计算中间对就足够了。这是O(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+parity(x)。
（您已经具有奇偶校验(x)函数）
f（a,b）=总和奇偶校验（b）-总和奇偶校验（a-1）
它只适用于正整数，但您也可以很容易地将逻辑扩展到负数。
