💻
Algorithm
  • README
  • Array
    • At Most To Equal
    • Count Inversions In An Array
    • Interleaving Placement
    • Kadane
    • Left To Right State Transition
    • Permutation
    • Quick Select
    • Sliding Window
    • Two Pointers
  • Binary Tree
    • Avl Tree
    • Binary Search Tree
    • Serialization And Deserialization
    • Traversal
  • Company
    • Facebook
  • Cpp
    • Array
    • Memset 3 F
    • Overflow
  • Data Structure
    • Binary Indexed Tree
    • Segment Tree And Binary Index Tree
    • Segment Tree
    • Stack
    • Trie
    • Union Find
  • Dynamic Programming
    • Knapsack
      • 0 1 Knapsack
      • Bounded Knapsack
      • Unbounded Knapsack
    • Bitmask Dp
    • Dp On Subsets
    • Dp On Tree
    • Dp With Sorting
    • Selective State Dp
    • Travelling Salesperson
  • Graph
    • Minimum Spanning Tree
      • Kruskal
      • Prim
    • Shortest Path
      • Bellman Ford
      • Dijkstra
      • Floyd Warshall
      • Johnson
      • Shortest Path Faster Algorithm
    • Bi Directional Breadth First Search
    • Bipartite
    • Breadth First Search
    • Component Coloring
    • Component Count
    • Depth First Search
    • Eulerian Path
    • Maximum Bipartite Matching
    • Tarjan
    • Topological Sort
    • Tree Diameter
    • Tree Ring Order Traversal
  • Greedy
    • Greedy Scheduling
    • Regret Greedy
  • Math
    • Catalan Number
    • Combinatorics
    • Factorial
    • Factorization
    • Fast Pow
    • Gcd
    • Geometry
    • Get Digits
    • Lcm
    • Median Minimizes Sum Of Absolute Deviations
    • Mode
    • Modular Multiplicative Inverse
    • Palindrome
    • Prime Number
    • Round Up
    • Sieve Of Eratosthenes
    • Stars And Bars
    • Sum Of Sequence
  • Miscellaneous
    • Bin Packing
    • Floyds Tortoise And Hare
    • Hungarian
    • Palindrome
  • Sort
    • Bubble Sort
    • Cycle Sort
    • Heap Sort
    • Merge Sort
    • Quick Sort
    • Sorting
  • Stl
    • Cpp Stl
    • Istringstream
    • Lower Bound Upper Bound
    • Priority Queue
  • String
    • Kmp
    • Manacher
    • Rabin Karp
    • String Processing
    • Z
  • Backtracking
  • Binary Answer
  • Binary Lifting
  • Binary Search
  • Bit Manipulation
  • Date
  • Difference Array
  • Discretization
  • Divide And Conquer
  • Gray Code
  • Great Problems For Practice
  • Interval Scheduling Maximization
  • Io Optimization
  • K Subset Partitioning
  • Line Sweep
  • Longest Common Subsequence
  • Longest Increasing Subsequence
  • Meet In The Middle
  • Minmax
  • Mono Deque
  • Monotonic Stack
  • Offline Query
  • P And Np
  • Prefix State Map
  • Prefix Sum
  • Random
  • Reservoir Sampling
  • Reverse Polish Notation
  • Sqrt Decomposition
Powered by GitBook
On this page
  • Bitwise NOT
  • Set the ith bit
  • Unset the ith bit
  • Toggle the ith bit
  • Check if ith bit is set
  • Set the ith bit with x
  • Get the lowest bit
  • Count bit 1s
  • Count trailing zeros
  • Count leading zeros
  • Check if n is power of 2
  • Traverse all the subsets
  • Complement of a subset
  • Traverse subsets of a set mask
  • Given N elements, traverse subsets of size K (Gosper's Hack)
  • Traverse subsets of subsets
  • Calculate subset sums
  • Generate logs array
  • Reference

Was this helpful?

Bit Manipulation

Bitwise NOT

~val
NOT 0111 (decimal 7)
= 1000 (decimal 8)

~val is also equivalent to val != -1, since -1 is the only one number whose bitwise NOT is 0.

So if val is some non-negative number, the following:

for (int i = val; ~i; --i)

is equivalent to

for (int i = val; i >= 0; --i)

Set the ith bit

mask |= 1 << i

Unset the ith bit

mask &= ~(1 << i)

Toggle the ith bit

mask ^= 1 << i

Check if ith bit is set

mask & (1 << i)
// Or
mask >> i & 1 // less typing

Set the ith bit with x

mask = (mask & ~(1 << i)) | (x << i)

Get the lowest bit

function lowbit(int x) {
    return x & -x;
}

Example:

        12 = (01100)2
       -12 = (10100)2
12 & (-12) = (00100)2

Count bit 1s

__builtin_popcount(n);

Note that the pop in this function means population.

Count trailing zeros

__builtin_ctz(n);

Count leading zeros

__builtin_clz(n);

Check if n is power of 2

__builtin_popcount(n) == 1
// or
(n & (n - 1)) == 0 // & has lower precedence than ==. Must add the parenthesis.

Traverse all the subsets

for (int mask = 0; mask < (1 << N); ++mask)

Complement of a subset

// Assume `sub` is a subset of `mask`
int complement = mask ^ sub;
// Or
int complement = mask - sub;

Traverse subsets of a set mask

for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // `sub` is a non-empty subset of `mask`
}

Sample output:

// mask = 0b1011
1011
1010
1001
1000
0011
0010
0001

Or the other direction:

for (int other = mask; other; other = (other - 1) & mask) {
    int sub = mask - other;
    // `other` is a non-empty subset of `mask`. `sub` is the complement of `other`.
}

Sample output:

0000
0001
0010
0011
1000
1001
1010

Given N elements, traverse subsets of size K (Gosper's Hack)

// Time Complexity: O(C(N, K))
int sub = (1 << k) - 1;
while (sub < (1 << N)) {
    // Access `sub` here. `sub` has `K` elements and is a subset of `N` elements.
    int c = sub & - sub, r = sub + c;
    sub = (((r ^ sub) >> 2) / c) | r;
}

Traverse subsets of subsets

Given an array of N elements, traverse all its subsets. For each of the subsets, traverse its all non-empty subsets as well.

// Time: O(3^N)
for (int mask = 0; mask < (1 << N); ++mask) {
    // `mask` is a subset of `N` elements
    for (int sub = mask; sub; sub = (sub - 1) & mask) {
        // `sub` is a subset of `mask`.
    }
}

Note that the time complexity is O(3^N) instead of O(2^N * 2^N) = O(4^N).

Math proof:

For a subset mask with K bits of 1s, there are 2^K subsets of it.

For N elements, there are C(N, K) subsets with K bits of 1s.

So the total number is SUM( C(N, K) * 2^K | 0 <= K <= N ).

Since (1 + x)^N = C(N, 0) * x^0 + C(N, 1) * x^1 + ... + C(N, N) * x^N, let x = 2, we have 3^N = SUM( C(N, K) * 2^K | 0 <= K <= N ).

Intuitive proof:

For each bit index i (0 <= i < N), the i-th bits of mask and sub must be one of 11, 10, 00, and can't be 01. So each bit has 3 possibilities, the total complexity is O(3^N).

Calculate subset sums

// Time: O(N * 2^N)
for (int mask = 0; mask < (1 << N); ++mask) {
    for (int i = 0; i < N; ++i) {
        if (mask >> i & 1) sum[mask] += A[i];
    }
}

Or

// DP solution
// Time: O(2^N)
for (int mask = 1; mask < (1 << N); ++mask) {
    sum[mask] = sum[mask - lowbit(mask)] + A[__builtin_ctz(lowbit(mask))];
}

where lowbit(x) = x & -x, and __builtin_ctz(x) counts the trailing zeros in x. Since lowbit(mask) is a power of two, __builtin_ctz(lowbit(mask)) == log2(lowbit(mask)).

Generate logs array

logs[n] is floor(log2(n)).

logs[1] = 0
logs[2] = 1
logs[3] = 1
logs[4] = 2
logs[5] = 2
logs[6] = 2
logs[7] = 2
logs[8] = 3
...
// Time: O(2^N)
for (int mask = 2; mask < (1 << N); ++mask) {
    logs[mask] = logs[mask >> 1] + 1;
}

Reference

PreviousBinary SearchNextDate

Last updated 3 years ago

Was this helpful?

https://oi-wiki.org/math/bit/