算法模板目录 ：个人算法模板

求 l & (l + 1) & … & r的值。（1 <= l <= r <= 1e18）

int AndSum(int l, int r) {
    int ans = r, pos = 0;
    for(int i = 1; r > 0; i++) {
        if ((l & 1) ^ (r & 1)) pos = i;
        l >>= 1;
        r >>= 1;
    }
    ans >>= pos;
    ans <<= pos;
    return ans;
}

求 l | (l + 1) | … | r的值。（1 <= l <= r <= 1e18）

int OrSum(int l, int r) {
    if (l == r) return l;
    int pos = 63;
    while (!((l ^ r) & 1LL << pos)) --pos;
    while (~pos) l |= 1LL << pos--;
    return l;
}

求 l ^ (l + 1) ^ … ^ r的值。（1 <= l <= r <= 1e18）

int PreXorSum(int n) {
    int ans = 0;
    for (int i = n / 4 * 4; i <= n; i++) {
        ans ^= i;
    }
    return ans;
}
int XorSum(int l, int r) {
    return PreXorSum(r) ^ PreXorSum(l - 1);
}