C++ Bit Manipulation | Complete 'Bitmask' Guide

Introduction

Bit-level operations are frequently used to represent flag sets as a single integer or compress state in algorithms. This guide clarifies operator meanings, then helps you apply examples and production tips to your own code.

Bit operations manipulate integers at the bit level. Used for flag management, memory optimization, and algorithm optimization, they execute in a single CPU cycle and are extremely fast.

---

Reality in Production

When learning development, everything seems clean and theoretical. But production is different. Wrestling with legacy code, chasing tight deadlines, facing unexpected bugs. The content covered here was initially learned as theory, but through applying it to real projects, I realized “ah, that’s why it’s designed this way.”

Particularly memorable are the trials and errors from my first project. I followed what I learned from books but couldn’t figure out why it didn’t work, spending days stuck. Eventually discovered the problem through senior developer code review, learning a lot in the process. This guide covers not just theory but also pitfalls and solutions you might encounter in practice.

1. Bit Operators

Basic Operators

Here is the main implementation:

#include <iostream>
#include <bitset>

int main() {
    // 0b: binary literal (C++14)
    int a = 0b1010;  // 10 (binary 1010)
    int b = 0b1100;  // 12 (binary 1100)
    
    // std::bitset<4>: output as 4-bit binary
    std::cout << "a: " << std::bitset<4>(a) << " (" << a << ")" << std::endl;
    std::cout << "b: " << std::bitset<4>(b) << " (" << b << ")" << std::endl;
    std::cout << std::endl;
    
    // AND (&): 1 if both 1, else 0
    // 1010 & 1100 = 1000 (8)
    std::cout << "a & b: " << std::bitset<4>(a & b) << " (" << (a & b) << ")" << std::endl;
    
    // OR (|): 1 if either 1, 0 if both 0
    // 1010 | 1100 = 1110 (14)
    std::cout << "a | b: " << std::bitset<4>(a | b) << " (" << (a | b) << ")" << std::endl;
    
    // XOR (^): 1 if different, 0 if same
    // 1010 ^ 1100 = 0110 (6)
    std::cout << "a ^ b: " << std::bitset<4>(a ^ b) << " (" << (a ^ b) << ")" << std::endl;
    
    // NOT (~): bit inversion (0→1, 1→0)
    // ~1010 = ...11110101 (negative, two's complement)
    std::cout << "~a: " << std::bitset<8>(~a) << " (" << (~a) << ")" << std::endl;
    
    // Left shift (<<): shift bits left (×2)
    // 1010 << 1 = 10100 (20)
    std::cout << "a << 1: " << std::bitset<8>(a << 1) << " (" << (a << 1) << ")" << std::endl;
    
    // Right shift (>>): shift bits right (÷2)
    // 1010 >> 1 = 0101 (5)
    std::cout << "a >> 1: " << std::bitset<8>(a >> 1) << " (" << (a >> 1) << ")" << std::endl;
    
    return 0;
}

Output:

Run the following commands:

a: 1010 (10)
b: 1100 (12)

a & b: 1000 (8)
a | b: 1110 (14)
a ^ b: 0110 (6)
~a: 11110101 (-11)
a << 1: 00010100 (20)
a >> 1: 00000101 (5)

Operator Summary

Operator	Name	Description	Example
&	AND	1 if both 1	1010 & 1100 = 1000
|	OR	1 if either 1	1010 | 1100 = 1110
^	XOR	1 if different	1010 ^ 1100 = 0110
~	NOT	Bit inversion	~1010 = ...0101
<<	Left Shift	Shift left (×2)	1010 << 1 = 10100
>>	Right Shift	Shift right (÷2)	1010 >> 1 = 0101

---

2. Bitmasks

Flag Management

Here is the main implementation:

#include <iostream>

// Flag definition: use each bit as one flag
// 1 << n: shift 1 left n times (only nth bit is 1)
const int FLAG_READ   = 1 << 0;  // 0b0001 = 1 (0th bit)
const int FLAG_WRITE  = 1 << 1;  // 0b0010 = 2 (1st bit)
const int FLAG_EXEC   = 1 << 2;  // 0b0100 = 4 (2nd bit)
const int FLAG_DELETE = 1 << 3;  // 0b1000 = 8 (3rd bit)
// Each flag uses different bit (no overlap)

int main() {
    int permissions = 0;  // Initial permission: none (0b0000)
    
    // Set flag (OR): set specific bit to 1
    // |=: OR then assign
    permissions |= FLAG_READ;   // 0b0000 | 0b0001 = 0b0001
    permissions |= FLAG_WRITE;  // 0b0001 | 0b0010 = 0b0011
    
    std::cout << "Permissions: " << permissions << std::endl;  // 3 (0b0011)
    
    // Check flag (AND): check if specific bit is 1
    // &: AND operation (extract that bit only)
    if (permissions & FLAG_READ) {  // 0b0011 & 0b0001 = 0b0001 (true)
        std::cout << "Read allowed" << std::endl;
    }
    
    if (permissions & FLAG_EXEC) {  // 0b0011 & 0b0100 = 0b0000 (false)
        std::cout << "Execute allowed" << std::endl;
    } else {
        std::cout << "Execute denied" << std::endl;
    }
    
    // Clear flag (AND NOT): set specific bit to 0
    // ~FLAG_WRITE: 0b0010 → 0b...11111101 (bit inversion)
    // &=: AND then assign
    permissions &= ~FLAG_WRITE;  // 0b0011 & 0b...11111101 = 0b0001
    
    std::cout << "After clearing write: " << permissions << std::endl;  // 1 (0b0001)
    
    // Toggle flag (XOR): invert specific bit (0→1, 1→0)
    // ^=: XOR then assign
    permissions ^= FLAG_EXEC;  // 0b0001 ^ 0b0100 = 0b0101
    
    std::cout << "After toggling exec: " << permissions << std::endl;  // 5 (0b0101)
    
    return 0;
}

Output:

Run the following commands:

Permissions: 3
Read allowed
Execute denied
After clearing write: 1
After toggling exec: 5

---

3. Practical Examples

Example 1: Permission System

Here is the grant implementation:

#include <iostream>
#include <string>

enum Permission {
    PERM_READ   = 1 << 0,  // 0b0001
    PERM_WRITE  = 1 << 1,  // 0b0010
    PERM_EXEC   = 1 << 2,  // 0b0100
    PERM_DELETE = 1 << 3   // 0b1000
};

class File {
    int permissions = 0;
    std::string name;
    
public:
    File(const std::string& n) : name(n) {}
    
    void grant(int perm) {
        permissions |= perm;
    }
    
    void revoke(int perm) {
        permissions &= ~perm;
    }
    
    bool has(int perm) const {
        return (permissions & perm) == perm;
    }
    
    void printPermissions() const {
        std::cout << "File: " << name << std::endl;
        std::cout << "  Read: " << (has(PERM_READ) ? "O" : "X") << std::endl;
        std::cout << "  Write: " << (has(PERM_WRITE) ? "O" : "X") << std::endl;
        std::cout << "  Execute: " << (has(PERM_EXEC) ? "O" : "X") << std::endl;
        std::cout << "  Delete: " << (has(PERM_DELETE) ? "O" : "X") << std::endl;
    }
};

int main() {
    File file("test.txt");
    
    // Grant read/write permissions
    file.grant(PERM_READ | PERM_WRITE);
    file.printPermissions();
    
    std::cout << std::endl;
    
    // Revoke write permission
    file.revoke(PERM_WRITE);
    file.printPermissions();
    
    return 0;
}

Output:

Run the following commands:

File: test.txt
  Read: O
  Write: O
  Execute: X
  Delete: X

File: test.txt
  Read: O
  Write: X
  Execute: X
  Delete: X

Example 2: Bit Tricks

Here is the isEven implementation:

#include <iostream>

// Even/odd check
bool isEven(int n) {
    return (n & 1) == 0;
}

// Power of two check
bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

// Bit count (number of 1s)
int countBits(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

// Extract lowest bit
int lowestBit(int n) {
    return n & -n;
}

// Highest bit position
int highestBitPos(int n) {
    int pos = 0;
    while (n >>= 1) ++pos;
    return pos;
}

// Set bit
int setBit(int n, int pos) {
    return n | (1 << pos);
}

// Clear bit
int clearBit(int n, int pos) {
    return n & ~(1 << pos);
}

// Toggle bit
int toggleBit(int n, int pos) {
    return n ^ (1 << pos);
}

// Test bit
bool testBit(int n, int pos) {
    return (n & (1 << pos)) != 0;
}

int main() {
    std::cout << "isEven(10): " << isEven(10) << std::endl;  // 1
    std::cout << "isEven(11): " << isEven(11) << std::endl;  // 0
    
    std::cout << "isPowerOfTwo(16): " << isPowerOfTwo(16) << std::endl;  // 1
    std::cout << "isPowerOfTwo(15): " << isPowerOfTwo(15) << std::endl;  // 0
    
    std::cout << "countBits(0b1011): " << countBits(0b1011) << std::endl;  // 3
    
    std::cout << "lowestBit(0b1010): " << lowestBit(0b1010) << std::endl;  // 2
    
    std::cout << "highestBitPos(0b1000): " << highestBitPos(0b1000) << std::endl;  // 3
    
    int n = 0b1010;
    std::cout << "setBit(n, 0): " << std::bitset<4>(setBit(n, 0)) << std::endl;  // 1011
    std::cout << "clearBit(n, 1): " << std::bitset<4>(clearBit(n, 1)) << std::endl;  // 1000
    std::cout << "toggleBit(n, 2): " << std::bitset<4>(toggleBit(n, 2)) << std::endl;  // 1110
    std::cout << "testBit(n, 3): " << testBit(n, 3) << std::endl;  // 1
    
    return 0;
}

---

4. std::bitset

Basic Usage

Here is the main implementation:

#include <bitset>
#include <iostream>

int main() {
    // Creation
    std::bitset<8> bits1("10101010");
    std::bitset<8> bits2(170);  // 10101010
    
    std::cout << "bits1: " << bits1 << std::endl;
    std::cout << "bits2: " << bits2 << std::endl;
    
    // Bit manipulation
    bits1.set(0);     // 10101011
    bits1.reset(1);   // 10101001
    bits1.flip(2);    // 10101101
    
    std::cout << "After modification: " << bits1 << std::endl;
    
    // Bit check
    if (bits1.test(0)) {
        std::cout << "Bit 0 is set" << std::endl;
    }
    
    // Count
    std::cout << "Set bits: " << bits1.count() << std::endl;
    
    // All/none check
    std::cout << "All set: " << bits1.all() << std::endl;
    std::cout << "Any set: " << bits1.any() << std::endl;
    std::cout << "None set: " << bits1.none() << std::endl;
    
    // Conversion
    std::cout << "Integer: " << bits1.to_ulong() << std::endl;
    std::cout << "String: " << bits1.to_string() << std::endl;
    
    return 0;
}

Output:

Run the following commands:

bits1: 10101010
bits2: 10101010
After modification: 10101101
Bit 0 is set
Set bits: 5
All set: 0
Any set: 1
None set: 0
Integer: 173
String: 10101101

---

5. Bit Fields

Struct Bit Fields

Here is the main implementation:

#include <iostream>

struct Flags {
    unsigned int read : 1;
    unsigned int write : 1;
    unsigned int exec : 1;
    unsigned int reserved : 29;
};

int main() {
    Flags f = {1, 0, 1, 0};
    
    std::cout << "Read: " << f.read << std::endl;   // 1
    std::cout << "Write: " << f.write << std::endl;  // 0
    std::cout << "Execute: " << f.exec << std::endl;   // 1
    
    std::cout << "Size: " << sizeof(f) << " bytes" << std::endl;  // 4 bytes
    
    // Modification
    f.write = 1;
    f.exec = 0;
    
    std::cout << "\nAfter modification:" << std::endl;
    std::cout << "Read: " << f.read << std::endl;   // 1
    std::cout << "Write: " << f.write << std::endl;  // 1
    std::cout << "Execute: " << f.exec << std::endl;   // 0
    
    return 0;
}

---

6. Common Issues

Issue 1: Signed Shift

Here is the main implementation:

#include <iostream>

int main() {
    // ❌ Negative right shift (implementation-defined)
    int x = -8;
    int y = x >> 1;  // -4 (arithmetic shift) or other value
    
    std::cout << "Negative shift: " << y << std::endl;
    
    // ✅ Unsigned type
    unsigned int ux = 8;
    unsigned int uy = ux >> 1;  // 4 (logical shift, guaranteed)
    
    std::cout << "Unsigned shift: " << uy << std::endl;
    
    return 0;
}

Issue 2: Shift Overflow

Here is the main implementation:

#include <iostream>

int main() {
    // ❌ Shift into sign bit (undefined behavior)
    int x = 1 << 31;  // UB
    
    std::cout << "Signed shift: " << x << std::endl;
    
    // ✅ Unsigned type
    unsigned int ux = 1u << 31;  // OK
    
    std::cout << "Unsigned shift: " << ux << std::endl;
    
    return 0;
}

Issue 3: Bit Field Portability

Here is the main implementation:

#include <iostream>

// ❌ Bit order undefined (compiler-dependent)
struct BadFlags {
    unsigned int a : 1;
    unsigned int b : 1;
    unsigned int c : 1;
};

// ✅ Use bitmask (portable)
const unsigned int FLAG_A = 1 << 0;
const unsigned int FLAG_B = 1 << 1;
const unsigned int FLAG_C = 1 << 2;

int main() {
    unsigned int flags = 0;
    flags |= FLAG_A;
    flags |= FLAG_C;
    
    std::cout << "Flags: " << flags << std::endl;  // 5 (0b101)
    
    return 0;
}

---

7. Practical Example: Bitmask DP

Here is the solve implementation:

#include <iostream>
#include <vector>
#include <algorithm>

// Traveling Salesman Problem (TSP) - Bitmask DP
class TSP {
    int n;
    std::vector<std::vector<int>> dist;
    std::vector<std::vector<int>> dp;
    
public:
    TSP(const std::vector<std::vector<int>>& distances) 
        : n(distances.size()), dist(distances) {
        dp.assign(1 << n, std::vector<int>(n, -1));
    }
    
    int solve(int visited, int current) {
        // All visited
        if (visited == (1 << n) - 1) {
            return dist[current][0];  // Back to start
        }
        
        // Memoization
        if (dp[visited][current] != -1) {
            return dp[visited][current];
        }
        
        int minCost = 1e9;
        
        // Choose next city
        for (int next = 0; next < n; ++next) {
            // Not yet visited
            if (!(visited & (1 << next))) {
                int cost = dist[current][next] + 
                          solve(visited | (1 << next), next);
                minCost = std::min(minCost, cost);
            }
        }
        
        return dp[visited][current] = minCost;
    }
    
    int findMinPath() {
        return solve(1, 0);  // Start from city 0
    }
};

int main() {
    std::vector<std::vector<int>> dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    
    TSP tsp(dist);
    std::cout << "Minimum path cost: " << tsp.findMinPath() << std::endl;
    
    return 0;
}

---

Summary

Key Takeaways

1. Bit operators: &, |, ^, ~, <<, >>
2. Bitmasks: Flag management (set, clear, check, toggle)
3. Bit fields: Memory optimization (low portability)
4. bitset: Convenient bit manipulation
5. Bit tricks: Even check, power of two, bit count
6. Performance: Single CPU cycle (very fast)

Bit Operation Usage

Usage	Technique	Example
Set flag	|=	flags |= FLAG_READ
Clear flag	&= ~	flags &= ~FLAG_WRITE
Check flag	&	if (flags & FLAG_EXEC)
Toggle flag	^=	flags ^= FLAG_DELETE
Even check	& 1	if ((n & 1) == 0)
Power of two	& (n-1)	if (n & (n-1) == 0)

Practical Tips

Usage principles:

• Flag management: bitmasks
• Memory optimization: bit fields
• Convenient manipulation: bitset
• Algorithms: bit tricks

Performance:

• Bit operations are very fast (1 cycle)
• Compiler auto-optimizes
• bitset slightly slower (convenience tradeoff)
• Bitmask DP optimizes to O(2ⁿ·n)

Cautions:

• Signed shift is implementation-defined
• Watch for shift overflow
• Bit fields have low portability
• Consider readability (add comments)

Next Steps

• C++ Bitset
• C++ Bit Operations
• Algorithm Bitmask DP

---

Related Articles

• C++ Bit Manipulation Complete Guide | Bitmask DP, XOR, Hamming Distance, Bitset [Practical]