Bit Manipulation
Bit manipulation involves operations on individual bits and is fundamental for low-level programming, optimization, and solving specific algorithmic problems efficiently.
Bitwise Operators
Understanding the fundamental bitwise operations:
#include <iostream>
#include <bitset>
int main() {
int a = 12; // Binary: 1100
int b = 10; // Binary: 1010
// AND (&): 1 only if both bits are 1
cout << "a & b = " << (a & b) << endl; // 8 (1000)
// OR (|): 1 if at least one bit is 1
cout << "a | b = " << (a | b) << endl; // 14 (1110)
// XOR (^): 1 if bits are different
cout << "a ^ b = " << (a ^ b) << endl; // 6 (0110)
// NOT (~): Flip all bits
cout << "~a = " << (~a) << endl; // -13 (two's complement)
// Left shift (<<): Multiply by 2^n
cout << "a << 2 = " << (a << 2) << endl; // 48 (multiply by 4)
// Right shift (>>): Divide by 2^n
cout << "a >> 2 = " << (a >> 2) << endl; // 3 (divide by 4)
// Visualize with bitset
cout << "a in binary: " << bitset<8>(a) << endl;
cout << "b in binary: " << bitset<8>(b) << endl;
return 0;
}
Basic Bit Operations
Essential bit manipulation techniques:
// Check if i-th bit is set
bool isBitSet(int num, int i) {
return (num & (1 << i)) != 0;
}
// Set i-th bit
int setBit(int num, int i) {
return num | (1 << i);
}
// Clear i-th bit
int clearBit(int num, int i) {
return num & ~(1 << i);
}
// Toggle i-th bit
int toggleBit(int num, int i) {
return num ^ (1 << i);
}
// Clear all bits from i-th bit to 0
int clearBitsFromIto0(int num, int i) {
return num & (~((1 << (i + 1)) - 1));
}
// Clear all bits from MSB to i-th bit
int clearBitsFromMSBtoI(int num, int i) {
return num & ((1 << i) - 1);
}
// Update i-th bit to value
int updateBit(int num, int i, int value) {
return (num & ~(1 << i)) | (value << i);
}
int main() {
int num = 12; // Binary: 1100
cout << "Original: " << bitset<8>(num) << " (" << num << ")" << endl;
cout << "Bit 1 set? " << isBitSet(num, 1) << endl;
cout << "Set bit 1: " << bitset<8>(setBit(num, 1)) << endl;
cout << "Clear bit 2: " << bitset<8>(clearBit(num, 2)) << endl;
cout << "Toggle bit 0: " << bitset<8>(toggleBit(num, 0)) << endl;
return 0;
}
Counting Set Bits
Different methods to count the number of 1s in binary representation:
// Method 1: Brian Kernighan's algorithm
int countSetBits1(int n) {
int count = 0;
while (n) {
n &= (n - 1); // Remove rightmost set bit
count++;
}
return count;
}
// Method 2: Simple bit checking
int countSetBits2(int n) {
int count = 0;
while (n) {
count += n & 1;
n >>= 1;
}
return count;
}
// Method 3: Built-in function (GCC)
int countSetBits3(int n) {
return __builtin_popcount(n);
}
// Method 4: Lookup table (for optimization)
int popcount_table[256];
void precompute_popcount() {
for (int i = 0; i < 256; i++) {
popcount_table[i] = (i & 1) + popcount_table[i / 2];
}
}
int countSetBits4(int n) {
return popcount_table[n & 0xff] +
popcount_table[(n >> 8) & 0xff] +
popcount_table[(n >> 16) & 0xff] +
popcount_table[(n >> 24) & 0xff];
}
int main() {
int num = 45; // Binary: 101101
cout << "Number: " << bitset<8>(num) << " (" << num << ")" << endl;
cout << "Set bits: " << countSetBits1(num) << endl; // 4
return 0;
}
XOR Properties and Applications
XOR has unique properties that make it very useful:
// XOR Properties:
// 1. a ^ a = 0
// 2. a ^ 0 = a
// 3. XOR is commutative and associative
// 4. a ^ b ^ a = b
// Find the unique number (all others appear twice)
int findUnique(vector<int>& nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result; // All duplicates cancel out
}
// Find two unique numbers (all others appear twice)
vector<int> findTwoUnique(vector<int>& nums) {
int xor_all = 0;
for (int num : nums) {
xor_all ^= num;
}
// Find rightmost set bit
int rightmost_bit = xor_all & (-xor_all);
int num1 = 0, num2 = 0;
for (int num : nums) {
if (num & rightmost_bit) {
num1 ^= num;
} else {
num2 ^= num;
}
}
return {num1, num2};
}
// Swap two numbers without temporary variable
void swapWithoutTemp(int& a, int& b) {
if (a != b) { // Avoid issues when a and b are same
a ^= b;
b ^= a;
a ^= b;
}
}
// Check if number is power of 2
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
int main() {
vector<int> nums = {1, 2, 3, 2, 1};
cout << "Unique number: " << findUnique(nums) << endl; // 3
int a = 5, b = 7;
cout << "Before swap: a=" << a << ", b=" << b << endl;
swapWithoutTemp(a, b);
cout << "After swap: a=" << a << ", b=" << b << endl;
cout << "8 is power of 2? " << isPowerOfTwo(8) << endl; // true
cout << "6 is power of 2? " << isPowerOfTwo(6) << endl; // false
return 0;
}
Bit Masking and Subset Generation
Use bit masks to represent and manipulate subsets:
// Generate all subsets using bit masking
void generateSubsets(vector<int>& arr) {
int n = arr.size();
// 2^n possible subsets
for (int mask = 0; mask < (1 << n); mask++) {
cout << "Subset: { ";
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
cout << arr[i] << " ";
}
}
cout << "}" << endl;
}
}
// Check if subset with given sum exists
bool hasSubsetSum(vector<int>& arr, int target) {
int n = arr.size();
for (int mask = 0; mask < (1 << n); mask++) {
int sum = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
sum += arr[i];
}
}
if (sum == target) {
return true;
}
}
return false;
}
// DP with bitmask - Traveling Salesman Problem
int tsp(vector<vector<int>>& dist) {
int n = dist.size();
vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
dp[1][0] = 0; // Start from city 0
for (int mask = 0; mask < (1 << n); mask++) {
for (int u = 0; u < n; u++) {
if (!(mask & (1 << u)) || dp[mask][u] == INT_MAX) continue;
for (int v = 0; v < n; v++) {
if (mask & (1 << v)) continue; // Already visited
int new_mask = mask | (1 << v);
dp[new_mask][v] = min(dp[new_mask][v],
dp[mask][u] + dist[u][v]);
}
}
}
int result = INT_MAX;
for (int i = 1; i < n; i++) {
result = min(result, dp[(1 << n) - 1][i] + dist[i][0]);
}
return result;
}
int main() {
vector<int> arr = {1, 2, 3};
cout << "All subsets:" << endl;
generateSubsets(arr);
cout << "Has subset with sum 4? " << hasSubsetSum(arr, 4) << endl; // true (1+3)
return 0;
}
Advanced Bit Tricks
Useful bit manipulation tricks for optimization:
// Get rightmost set bit
int getRightmostSetBit(int n) {
return n & (-n);
}
// Turn off rightmost set bit
int turnOffRightmostSetBit(int n) {
return n & (n - 1);
}
// Check if only one bit is set
bool isOnlyOneBitSet(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
// Position of rightmost set bit (1-indexed)
int positionOfRightmostSetBit(int n) {
return __builtin_ctz(n) + 1; // Count trailing zeros + 1
}
// Reverse bits
unsigned int reverseBits(unsigned int n) {
unsigned int result = 0;
for (int i = 0; i < 32; i++) {
result <<= 1;
result |= (n & 1);
n >>= 1;
}
return result;
}
// Fast multiplication/division by powers of 2
int multiplyBy8(int n) {
return n << 3; // Left shift by 3
}
int divideBy4(int n) {
return n >> 2; // Right shift by 2
}
// Check if number is odd/even
bool isOdd(int n) {
return n & 1;
}
// Absolute value without branching
int absoluteValue(int n) {
int mask = n >> 31; // Sign bit
return (n ^ mask) - mask;
}
// Min/Max without branching
int minWithoutBranch(int a, int b) {
return b ^ ((a ^ b) & -(a < b));
}
int maxWithoutBranch(int a, int b) {
return a ^ ((a ^ b) & -(a < b));
}
int main() {
int n = 12; // Binary: 1100
cout << "Number: " << bitset<8>(n) << " (" << n << ")" << endl;
cout << "Rightmost set bit: " << getRightmostSetBit(n) << endl; // 4
cout << "Position of rightmost set bit: " << positionOfRightmostSetBit(n) << endl; // 3
cout << "Turn off rightmost set bit: " << bitset<8>(turnOffRightmostSetBit(n)) << endl;
return 0;
}
Performance Benefits
Why Use Bit Manipulation?
- Speed: Bitwise operations are extremely fast
- Memory: Can pack boolean flags efficiently
- Elegance: Some problems have beautiful bit-based solutions
- Mathematics: Many number theory problems use bit properties
Common Pitfalls
- Sign extension: Be careful with negative numbers
- Overflow: Left shifts can cause overflow
- Operator precedence: Use parentheses with bit operators
- Portability: Some tricks depend on architecture