guest@cp-base:~/home/bit-manipulation$
templates/bit-utilities.cpp
compilable
$cat templates/bit-utilities

Bit Utilities

Common bit manipulation operations — check, set, clear, toggle, popcount, subset enumeration.

[Bit Manipulation]|
Jul 9, 2026
|explanatory_notes.md|
#bit-manipulation#bitmask#subset#popcount
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool checkBit(ll n, int i) { return (n >> i) & 1; }
ll setBit(ll n, int i) { return n | (1LL << i); }
ll clearBit(ll n, int i) { return n & ~(1LL << i); }
ll toggleBit(ll n, int i) { return n ^ (1LL << i); }
bool isPow2(ll n) { return n > 0 && (n & (n - 1)) == 0; }
int popcount(ll n) { return __builtin_popcountll(n); }
ll lowbit(ll n) { return n & (-n); }
ll clearLow(ll n) { return n & (n - 1); }
bool isSubset(ll a, ll b) { return (a & b) == a; }
int msbPos(ll n) { return n ? 63 - __builtin_clzll(n) : -1; }
int lsbPos(ll n) { return n ? __builtin_ctzll(n) : -1; }
int bitLen(ll n) { return n ? msbPos(n) + 1 : 1; }

vector<vector<int>> allSubsets(vector<int>& s) {
    int n = s.size();
    vector<vector<int>> res;
    for (int msk = 0; msk < (1 << n); msk++) {
        vector<int> sub;
        for (int i = 0; i < n; i++)
            if (msk >> i & 1) sub.push_back(s[i]);
        res.push_back(sub);
    }
    return res;
}
28 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

Bit Utilities

Common bit manipulation primitives, all O(1)O(1).

Operations

OperationFormula
Check bit ii`(n >> i) & 1`
Set bit ii`n \(1LL << i)`
Clear bit ii`n & ~(1LL << i)`
Toggle bit ii`n ^ (1LL << i)`
Lowest set bit`n & (-n)`
Clear lowest bit`n & (n - 1)`
Is power of 2`n > 0 && (n & (n-1)) == 0`
Is a⊆ba \subseteq b`(a & b) == a`

Builtin Functions

  • __builtin_popcountll(n) — count set bits

  • __builtin_clzll(n) — count leading zeros

  • __builtin_ctzll(n) — count trailing zeros

    • When to Use

  • Bitmask DP, subset enumeration

  • State compression (encoding sets as integers)

  • Game theory / Sprague-Grundy (XOR operations)

    • Complexity

  • All operations — O(1)O(1)