C++ Bit Manipulation: Bitmasks, std::bitset, Bit Fields and Bitmask DP

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 typically map to single CPU instructions and are extremely fast.

Speed is rarely the real reason to use them in modern code, though — compilers already turn x * 8 into a shift and x % 2 on unsigned values into a mask. The reasons that hold up are representation: packing many booleans into one integer (flags stored in a file header, a network packet, or a database column), treating a set of up to 64 small elements as a single value you can copy, hash, and compare in one operation (the basis of bitmask DP), and talking to hardware or protocols whose formats are defined bit by bit. The costs are readability and a set of undefined-behavior traps around signed integers and shift counts, which this guide covers in “Common Issues”.

Bit Operators

Basic Operators

#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:

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

Two properties of these operators cause most real bugs. First, precedence: &, ^, and | bind more loosely than == and !=, so if (x & MASK == 0) parses as x & (MASK == 0) — almost always wrong, and GCC/Clang warn with -Wparentheses (“suggest parentheses around comparison in operand of ’&’”). Always parenthesize: if ((x & MASK) == 0). Second, integer promotion: operands narrower than int are promoted to int before the operation, so ~ on a uint8_t with value 0x0F produces the int 0xFFFFFFF0, not 0xF0. That is why ~a prints as 11110101 here only because it is truncated to 8 bits by bitset<8>; the actual value is the 32-bit -11. Cast back (static_cast<uint8_t>(~a)) when you need the narrow result.

The “×2” and “÷2” descriptions of shifts are also approximations: shifting left by k multiplies by 2ᵏ only while the result fits, and right-shifting a negative number rounds toward negative infinity (-5 >> 1 == -3), while integer division rounds toward zero (-5 / 2 == -2).

---

Bitmasks

Flag Management

#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:

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

The four idioms — |= to set, &= ~ to clear, & to test, ^= to toggle — are worth memorizing as units, because each one leaves every other bit untouched. That is the point of a bitmask: permissions &= ~FLAG_WRITE clears one permission without needing to know which others are present. Toggling is the one to use sparingly; it makes the result depend on the previous state, which is rarely what business logic means (“grant execute” should set, not flip). For flag types in real code, prefer unsigned or a fixed-width type like std::uint32_t over int, so that the highest bit is an ordinary flag rather than a sign bit.

---

Practical Examples

Example 1: Permission System

#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:

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

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

Note the has() implementation: (permissions & perm) == perm checks that all requested bits are set, so has(PERM_READ | PERM_WRITE) is true only when both are granted. The looser (permissions & perm) != 0 means “any of them”, and mixing the two semantics up is a classic authorization bug. The example uses a plain enum because its values convert to int implicitly, which is what makes PERM_READ | PERM_WRITE compile. With a type-safe enum class, | is not defined and you get no match for 'operator|'; the usual solution is to define operator|, operator&, and operator~ for the enum (using std::underlying_type_t), which keeps flags from being mixed with unrelated integers.

Example 2: Bit Tricks

#include <bitset>
#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;
}

Why the tricks work: n - 1 flips the lowest set bit and every zero below it, so n & (n - 1) clears exactly the lowest set bit — zero only if there was one bit to begin with, hence the power-of-two test. In two’s complement, -n equals ~n + 1, which flips every bit above the lowest set bit, so n & -n keeps only that bit. These identities are the foundation of structures like Fenwick trees.

They also have edge cases that the int signatures above hide. countBits(-1) never terminates on typical compilers: right-shifting a negative number keeps copying the sign bit, so n stays -1 forever. lowestBit(INT_MIN) negates INT_MIN, which overflows (undefined behavior). highestBitPos(0) and highestBitPos(1) both return 0. And setBit(n, 31) or any pos >= 32 hits the shift rules below. Writing these helpers for unsigned types removes most of the problems. Better still, since C++20 the <bit> header provides tested versions: std::popcount, std::has_single_bit (power of two), std::countr_zero (index of the lowest set bit), std::bit_width(x) - 1 (index of the highest), and std::rotl/std::rotr — all for unsigned types, and all compiling to single instructions where the CPU has them.

---

std::bitset

Basic Usage

#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:

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

std::bitset<N> is the safer default when the number of bits is fixed at compile time and may exceed 64, or when you mostly want readability. Indexing is from the least significant bit: bits.set(0) changes the rightmost character of the printed string, which confuses people who expect string order. The constructor from a string throws std::invalid_argument for characters other than 0/1, to_ulong() throws std::overflow_error if set bits don’t fit in an unsigned long (a real risk with bitset<64> on Windows, where unsigned long is 32 bits — use to_ullong()), and test(pos) throws std::out_of_range while operator[] does not check. The size cannot change at runtime; for that, std::vector<bool> or boost::dynamic_bitset are the options, each with its own quirks. See std::bitset for more.

---

Bit Fields

Struct Bit Fields

#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;
}

Bit fields let the compiler do the masking for you, and the syntax is pleasant, but the standard leaves most of the layout to the implementation: whether fields are allocated from the low or high end of the storage unit, whether a field may straddle a unit boundary, and the padding. sizeof(f) is 4 on the common compilers here, but a struct with bit fields is not a reliable way to match a file or wire format across compilers or platforms. You also cannot take the address of a bit field or bind a non-const reference to it, and — a subtle one — adjacent bit fields share the same memory location, so two threads writing f.read and f.write concurrently is a data race even though they are “different” fields. Bit fields are best for compact in-memory structs used by one thread; for anything serialized, use explicit masks and shifts on a fixed-width integer.

---

Common Issues

Issue 1: Signed Shift

#include <iostream>

int main() {
    // ❌ Negative right shift (implementation-defined before C++20; arithmetic since C++20)
    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

#include <iostream>

int main() {
    // ❌ Shift into sign bit (UB before C++20; since C++20 it yields INT_MIN)
    int x = 1 << 31;
    
    std::cout << "Signed shift: " << x << std::endl;
    
    // ✅ Unsigned type
    unsigned int ux = 1u << 31;  // OK
    
    std::cout << "Unsigned shift: " << ux << std::endl;
    
    return 0;
}

C++20 made signed integers officially two’s complement, which turned the two cases above from implementation-defined or undefined into defined behavior. Plenty of code still compiles as C++17 or earlier, though, and one shift rule is undefined in every version: shifting by a negative amount or by a count greater than or equal to the width of the (promoted) left operand. 1 << 32 with a 32-bit int, or 1u << n where n can reach 32, is UB — and on x86 the hardware masks the count to 5 bits, so in practice 1u << 32 often yields 1, silently. This is the bug I have seen most in bitmask code that grows past 32 flags: someone adds flag 32 as 1 << 32 or 1u << 32 and gets a warning at best (shift count >= width of type). When masks can exceed 32 bits, write 1ULL << n or std::uint64_t{1} << n, and keep the shift count’s range in mind in loops like for (int i = 0; i <= 32; ++i).

Undefined behavior sanitizer (-fsanitize=undefined) reports these shifts at runtime with messages like shift exponent 32 is too large for 32-bit type 'unsigned int', which makes it cheap to catch them in tests.

Issue 3: Bit Field Portability

#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;
}

---

Practical Example: Bitmask DP

#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;  // 80 (0→1→3→2→0)
    
    return 0;
}

Here the integer visited is a set: bit i set means city i has been visited. That encoding is what makes the memoization table possible — dp[visited][current] indexes directly by the set, and “add city next” is visited | (1 << next). The state space has 2ⁿ × n entries and each state loops over n next cities, so the running time is O(n²·2ⁿ) with O(n·2ⁿ) memory. That is exponential, but vastly better than trying all (n−1)! routes: for n = 16 it is about 16 million steps versus about 1.3 × 10¹² permutations. The memory is the practical limit — with int entries, n = 20 needs roughly 80 MB for the table, and n = 25 is out of reach — which is why bitmask DP is used for problems with around 20 elements or fewer.

The -1 sentinel works because every real cost is non-negative; if costs could be negative, you would need a separate “computed” flag. 1e9 as the initial minimum is a conventional “infinity”, but adding a distance to it can overflow if the graph has missing edges represented as 1e9, so use a value comfortably below INT_MAX or a wider type.

---

Flag operations and the rules that prevent bit bugs

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 > 0 && (n & (n-1)) == 0)

Most bit bugs come from the types involved rather than the operators. Do bit work on unsigned types: shifting a negative value was implementation-defined or undefined before C++20. A shift count equal to or larger than the operand’s width is undefined in every standard, which bites when building a mask like 1 << 32 or 1u << n with n reaching the width; use 1ULL << n for 64-bit masks and check n first. Bit fields save memory, but their layout is implementation-defined, so do not use them to match an on-disk or network format.

For readability, name masks as constants or use std::bitset when the set of flags is fixed; the compiler generates the same instructions for most of these operations either way.

Next Steps

• C++ Bitset
• Undefined behavior in C++
• Dynamic programming patterns

---

Frequently Asked Questions (FAQ)

Q. Should I use __builtin_popcount or std::popcount to count set bits?

A. __builtin_popcount is a GCC/Clang extension and is not available in MSVC, and you must pick the right variant for the width (__builtin_popcountll for 64-bit values). C++20 provides std::popcount in <bit>, which is portable and works for all unsigned integer types, together with std::countl_zero, std::countr_zero and std::has_single_bit. Note that std::popcount does not accept signed types, so cast to an unsigned type first. With the right target flags, such as -mpopcnt, both usually compile down to a single instruction.

---

Related Articles

• C++ std::bitset
• C++ Undefined Behavior
• DP Patterns

---