[go: up one dir, main page]
Scribd
Upload
124 views2 pages

Bitwise Cheat Sheet CPP

This cheat sheet provides an overview of basic bitwise operations in C++, including AND, OR, XOR, NOT, and bit shifting. It also covers bit manipulation tricks, subset generation using bitmasks, and common use cases such as dynamic programming and optimizing graph problems. Additionally, it includes tips for efficient coding practices with bitwise operations.

Uploaded by

rock70907
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
124 views2 pages

Bitwise Cheat Sheet CPP

This cheat sheet provides an overview of basic bitwise operations in C++, including AND, OR, XOR, NOT, and bit shifting. It also covers bit manipulation tricks, subset generation using bitmasks, and common use cases such as dynamic programming and optimizing graph problems. Additionally, it includes tips for efficient coding practices with bitwise operations.

Uploaded by

rock70907
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Bitwise Operations Cheat Sheet (C++ Competitive Programming)

1. Basic Bitwise Operations

AND (&) :a&b -> Bitwise AND


OR (|) :a|b -> Bitwise OR
XOR (^) :a^b -> Bitwise XOR
NOT (~) : ~a -> Bitwise NOT (1's complement)
Left Shift : a << k -> a * 2^k
Right Shift : a >> k -> a / 2^k

2. Bit Manipulation Tricks

Check if i-th bit is set : x & (1 << i)


Set i-th bit : x |= (1 << i)
Unset i-th bit : x &= ~(1 << i)
Toggle i-th bit : x ^= (1 << i)
Turn off lowest set bit : x & (x - 1)
Isolate lowest set bit : x & -x
Set lowest unset bit : x | (x + 1)
Check power of 2 : x != 0 && (x & (x - 1)) == 0
Count set bits (int) : __builtin_popcount(x)
Count set bits (long long) : __builtin_popcountll(x)
Count trailing zeroes : __builtin_ctz(x)
Count leading zeroes : __builtin_clz(x)
Bit parity : __builtin_parity(x)

3. Subsets Using Bitmasks

for (int mask = 0; mask < (1 << n); mask++) {


for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
// i-th element is in subset
}
}
}

4. Common Use Cases

- Efficient subset enumeration


- Bitmask Dynamic Programming (e.g. TSP)
Bitwise Operations Cheat Sheet (C++ Competitive Programming)

- Representing sets using integers


- Optimizing XOR problems
- Graph problems using bitsets

5. Tips & Notes

- Use long long for large shifts to avoid overflow.


- Bitset<N> is memory efficient for large boolean arrays.
- Binary hacks improve both runtime and code compactness.
- Masking is critical in problems with subset constraints.

You might also like