Count Set Bits (Popcount) & Applications

1. Algorithm & Complexity

To count the number of set bits (ones) in the binary representation of an integer x, the two most common methods are:

1. Built‐in / Table Lookup
   In C++, __builtin_popcount(x) runs in hardware‐optimized instructions (O(1) per call). For 64-bit you can use __builtin_popcountll(x).
2. Brian Kernighan’s algorithm
   Repeatedly clear the lowest set bit:

   while (x) {
       x &= (x - 1);
       cnt++;
   }
       

   Each iteration removes one 1‐bit, so it runs in O(k) time where k = number of 1s.

Time Complexity

• Built‐in: O(1) per call
• Kernighan: O(k) per call, k = popcount(x), at most O(log x)

Memory Complexity

O(1) extra memory beyond input.

---

2. Two Easy Codeforces Problems

2.1 A. Bits (484A)

Given many queries [l, r], for each find the smallest x in [l…r] with the maximum number of set bits.

Input:
3
1 2
2 4
1 10

Output:
1
3
7

#include <iostream>
using namespace std;
// For each query, greedily turn on lower zero‐bits of l until you exceed r.
long long bestX(long long l, long long r) {
    long long x = l;
    for (int b = 0; b < 63; ++b) {
        long long mask = 1LL<<b;
        if ((x & mask) == 0 && (x | mask) <= r) {
            x |= mask;
        }
    }
    return x;
}

int main() {
    int q; 
    cin >> q;
    while (q--) {
        long long l, r;
        cin >> l >> r;
        cout << bestX(l, r) << "\n";
    }
    return 0;
}

2.2 A. Little Elephant and Bits (220A)

Given a binary string, remove exactly one character to make the resulting string lexicographically largest. Counting bits helps you compare outcomes.

Input:
101
Output:
11

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    // remove the first '0' to maximize lex order; if none, remove first '1'
    int pos = -1;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '0') { pos = i; break; }
    }
    if (pos < 0) pos = 0;
    s.erase(pos, 1);
    cout << s << "\n";
    return 0;
}

---

3. Two Intermediate Codeforces Problems

3.1 B. Little Pony and Sort by Shift (454B)

Determine if by cyclically shifting a permutation you can sort it ascending. Each shift is like adding 1<<k in a circular bit‐mask sense.

Input:
5
3 4 5 1 2
Output:
YES

#include <iostream>
#include <vector>>
using namespace std;

int main() {
    int n; 
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    // find how many shifts to bring '1' to front
    int idx = -1;
    for (int i = 0; i < n; ++i)
        if (a[i] == 1) idx = i;
    bool ok = true;
    for (int i = 0; i < n; ++i) {
        if (a[(idx + i) % n] != i+1) {
            ok = false; break;
        }
    }
    cout << (ok ? "YES\n" : "NO\n");
    return 0;
}

3.2 D. Pashmak and Parmida’s Problem (459D)

Count pairs (i,j) where freq(a[i] up to i) > freq(a[j] from j to end). We precompute counts (= popcounts over frequencies).

Input:
6
1 1 2 2 1 3
Output:
3

#include <iostream>
#include <vector>>
#include <map>>
using namespace std;
using ll = long long;

int main() {
    int n; 
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    vector<int> pre(n), suf(n);
    map<int,int> cnt;
    for (int i = 0; i < n; ++i) {
        cnt[a[i]]++;
        pre[i] = cnt[a[i]];
    }
    cnt.clear();
    for (int i = n-1; i >= 0; --i) {
        cnt[a[i]]++;
        suf[i] = cnt[a[i]];
    }
    ll ans = 0;
    // for each i, count j>i with pre[i] > suf[j]
    map<int,ll> freq;
    for (int j = 1; j < n; ++j)
        freq[suf[j]]++;
    for (int i = 0; i < n-1; ++i) {
        // remove suf[i+1] from map
        freq[suf[i+1]]--;
        if (freq[suf[i+1]] == 0) freq.erase(suf[i+1]);
        // sum all counts for keys < pre[i]
        for (auto &p : freq) {
            if (p.first < pre[i]) ans += p.second;
            else break;
        }
    }
    cout << ans << "\n";
    return 0;
}

---

4. One Hard Codeforces Problem

E. Beautiful Subarrays (1555E)

Count subarrays whose XOR has an even number of set bits. We use prefix‐xor and popcount to detect parity classes, then count pairs.

Input:
7
1 2 3 2 1 2 3
Output:
10

#include <iostream>
#include <vector>>
#include <map>>
using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    map<int,ll> cnt;
    cnt[0] = 1;
    int px = 0;
    ll ans = 0;
    for (int x : a) {
        px ^= x;
        int b = __builtin_popcount(px) & 1; // parity of bits
        // If parity is 0, subarray [0..i] is “beautiful”
        ans += cnt[b];
        cnt[b]++;
    }
    cout << ans << "\n";
    return 0;
}