Bitwise Operations in C/C++
in Blog / Algorithms and Programming Languages , Tags: C++
A comprehensive guide to bitwise operations in C and C++, covering operators, practical applications, and common patterns for efficient programming.
Table of Contents
- 1. Why Bits Matter
- 2. The Six Bitwise Operators
- 3. Practical Applications
- 4. Embedded Systems Applications
- 5. Common Patterns
- 6. Practice Problems
- 7. Best Practices
1. Why Bits Matter
Computers store and process data as binary digits (bits). Bitwise operations allow direct manipulation of individual bits, providing efficiency gains that high-level operations cannot match.
graph TD
A[High-Level Code] --> B[Compiler]
B --> C[Assembly/Machine Code]
C --> D[Binary Operations]
D --> E[Hardware Execution]
style D fill:#ffeb3b
style E fill:#4caf50
Why Learn Bitwise Operations?
| Benefit | Example |
|---|---|
| Speed | 10-100x faster than arithmetic operations |
| Memory | Store 8 boolean flags in 1 byte instead of 8 |
| Hardware Control | Direct manipulation of registers in embedded systems |
| Efficiency | Essential for graphics, cryptography, compression |
| Problem Solving | Efficient solutions to complex problems |
Bitwise operations are powerful tools. Use them where they provide clear benefits in performance or memory efficiency, but prioritize code readability when the gains are marginal.
Real-World Impact:
- Embedded Systems: Control LEDs, read sensors, configure hardware
- Graphics: Fast pixel manipulation, color blending
- Networking: IP address manipulation, packet parsing
- Algorithms: Fast mathematical operations, optimization tricks
All the Core Bitwise Operations you need to know …
2. The Six Bitwise Operators
2.1 AND Operator (&)
Rule: Output is 1 only if BOTH bits are 1
1 0 1 0 (10 in decimal)
& 1 1 0 0 (12 in decimal)
---------
1 0 0 0 (8 in decimal)
Truth Table:
| A | B | A & B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 ← Only this case! |
Code Example:
int a = 10; // 1010 in binary
int b = 12; // 1100 in binary
int result = a & b; // 1000 = 8
cout << result; // Output: 8
Common Uses:
- Check if a bit is set:
if (x & (1 << n)) - Clear bits:
x = x & 0xF0(keep upper 4 bits) - Extract specific bits (masking)
2.2 OR Operator (|)
Rule: Output is 1 if EITHER bit is 1
1 0 1 0 (10 in decimal)
| 1 1 0 0 (12 in decimal)
---------
1 1 1 0 (14 in decimal)
Truth Table:
| A | B | A | B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Code Example:
int a = 10; // 1010
int b = 12; // 1100
int result = a | b; // 1110 = 14
cout << result; // Output: 14
Common Uses:
- Set specific bits:
x = x | (1 << n) - Combine flags:
options = FLAG_A | FLAG_B - Turn bits ON
2.3 XOR Operator (^)
Rule: Output is 1 if bits are DIFFERENT
1 0 1 0 (10 in decimal)
^ 1 1 0 0 (12 in decimal)
---------
0 1 1 0 (6 in decimal)
Truth Table:
| A | B | A ^ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 ← Different! |
| 1 | 0 | 1 ← Different! |
| 1 | 1 | 0 |
Code Example:
int a = 10; // 1010
int b = 12; // 1100
int result = a ^ b; // 0110 = 6
cout << result; // Output: 6
Key Property: x ^ x = 0 and x ^ 0 = x
Common Uses:
- Toggle bits:
x = x ^ (1 << n) - Swap without temp variable:
a^=b; b^=a; a^=b; - Find unique element in array
- Encryption (basic XOR cipher)
2.4 NOT Operator (~)
Rule: Flips all bits (0→1, 1→0)
~ 1 0 1 0 (10 in decimal)
---------
0 1 0 1 (-11 in two's complement)
Code Example:
unsigned char a = 10; // 00001010
unsigned char result = ~a; // 11110101 = 245
cout << (int)result; // Output: 245
Important: Result depends on data type size!
unsigned char: 8 bitsint: typically 32 bits- Watch out for sign extension!
Common Uses:
- Clear specific bits:
x = x & ~(1 << n) - Create bit masks:
~0xFF= all 1s except lower 8 bits
2.5 Left Shift («)
Rule: Shift bits left, fill right with zeros
0 0 1 0 1 0 (10 in decimal)
<< 2
---------------
1 0 1 0 0 0 (40 in decimal)
Visual:
Original: [0][0][1][0][1][0]
↓ ↓ ↓ ↓
Shift left 2: [1][0][1][0][0][0]
↑ ↑
Fill with 0
Code Example:
int x = 10; // 1010
int result = x << 2; // 101000 = 40
cout << result; // Output: 40
Mathematical Formula:
x << k = x × 2^k
Examples:
10 << 1 = 10 × 2¹ = 10 × 2 = 20
10 << 2 = 10 × 2² = 10 × 4 = 40
5 << 3 = 5 × 2³ = 5 × 8 = 40
7 << 4 = 7 × 2⁴ = 7 × 16 = 112
Common Uses:
- Fast multiplication by powers of 2
- Create bit masks:
1 << n - Set specific bit positions
2.6 Right Shift (»)
Rule: Shift bits right, discard rightmost bits
1 0 1 0 0 0 (40 in decimal)
>> 2
---------------
0 0 1 0 1 0 (10 in decimal)
Visual:
Original: [1][0][1][0][0][0]
↓ ↓ ↓
Shift right 2: [0][0][1][0][1][0]
↑ ↑
Fill with 0
(for unsigned)
Code Example:
int x = 40; // 101000
int result = x >> 2; // 1010 = 10
cout << result; // Output: 10
Mathematical Formula:
x >> k = x ÷ 2^k (integer division, rounds down)
Examples:
40 >> 1 = 40 ÷ 2¹ = 40 ÷ 2 = 20
40 >> 2 = 40 ÷ 2² = 40 ÷ 4 = 10
100 >> 3 = 100 ÷ 2³ = 100 ÷ 8 = 12
17 >> 2 = 17 ÷ 2² = 17 ÷ 4 = 4 (remainder discarded)
Signed vs Unsigned:
unsigned int a = 200;
int b = -200;
cout << (a >> 2); // 50 (fills with 0)
cout << (b >> 2); // -50 (arithmetic shift, fills with sign bit)
Common Uses:
- Fast division by powers of 2
- Extract bit fields
- Parse bit patterns
3. Common Techniques
Technique 1: Check if Number is Even or Odd
bool isOdd(int n) {
return n & 1; // Check least significant bit
}
// Why it works:
// Even: ...0010 (LSB = 0)
// Odd: ...0011 (LSB = 1)
Performance:
Traditional: n % 2 → 10-20 CPU cycles
Bitwise: n & 1 → 1 CPU cycle ⚡
Technique 2: Multiply/Divide by Powers of 2
int multiplyBy4(int n) {
return n << 2; // Same as n * 4
}
int divideBy8(int n) {
return n >> 3; // Same as n / 8
}
// Benchmark:
int x = 100;
x * 32; // ~10 cycles
x << 5; // ~1 cycle (32x faster)
Technique 3: Swap Without Temp Variable
void swap(int& a, int& b) {
a = a ^ b; // a = a^b, b = b
b = a ^ b; // a = a^b, b = (a^b)^b = a
a = a ^ b; // a = (a^b)^a = b, b = a
}
// Example:
int x = 5, y = 10;
swap(x, y);
cout << x << " " << y; // 10 5
Step-by-Step:
Initial: a=5 (0101), b=10 (1010)
Step 1: a = a^b = 0101 ^ 1010 = 1111
a=15, b=10
Step 2: b = a^b = 1111 ^ 1010 = 0101 = 5
a=15, b=5
Step 3: a = a^b = 1111 ^ 0101 = 1010 = 10
a=10, b=5
Result: a=10, b=5
Technique 4: Check if Power of 2
bool isPowerOf2(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
// Why it works:
// Power of 2: 1000 (8)
// n - 1: 0111 (7)
// n & (n-1): 0000
// Not power of 2: 1010 (10)
// n - 1: 1001 (9)
// n & (n-1): 1000 (not 0)
Visual:
n = 8 (power of 2):
1 0 0 0
& 0 1 1 1 (n-1)
---------
0 0 0 0 (result is 0)
n = 10 (not power of 2):
1 0 1 0
& 1 0 0 1 (n-1)
---------
1 0 0 0 (result is not 0)
Technique 5: Count Set Bits (Brian Kernighan’s Algorithm)
int countSetBits(int n) {
int count = 0;
while (n) {
n = n & (n - 1); // Remove rightmost set bit
count++;
}
return count;
}
// Example: n = 13 (1101)
// Step 1: 1101 & 1100 = 1100, count=1
// Step 2: 1100 & 1011 = 1000, count=2
// Step 3: 1000 & 0111 = 0000, count=3
// Result: 3 set bits
Visualization:
n = 13: 1 1 0 1
↓
Step 1: 1 1 0 0 (removed rightmost 1)
↓
Step 2: 1 0 0 0 (removed another 1)
↓
Step 3: 0 0 0 0 (removed last 1)
Total: 3 iterations = 3 set bits
4. Embedded Systems Applications
Example 1: LED Control
Controlling 8 LEDs connected to a single port:
// LED positions
#define LED0 (1 << 0) // 00000001
#define LED1 (1 << 1) // 00000010
#define LED2 (1 << 2) // 00000100
#define LED3 (1 << 3) // 00001000
// ... and so on
unsigned char PORTB = 0x00; // All LEDs OFF
// Turn ON LED2
PORTB |= LED2; // Set bit 2
// Result: 00000100
// Turn OFF LED2
PORTB &= ~LED2; // Clear bit 2
// Result: 00000000
// Toggle LED2
PORTB ^= LED2; // Flip bit 2
// Result: 00000100 → 00000000 → 00000100
// Check if LED2 is ON
if (PORTB & LED2) {
cout << "LED2 is ON!";
}
// Turn ON multiple LEDs
PORTB |= (LED0 | LED2 | LED5);
// Result: 00100101
Visual Port State:
PORTB: [LED7][LED6][LED5][LED4][LED3][LED2][LED1][LED0]
0 0 1 0 0 1 0 1
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
OFF OFF ON OFF OFF ON OFF ON
Example 2: Reading Sensor Status
// Sensor register bits
#define SENSOR_READY (1 << 0)
#define SENSOR_ERROR (1 << 1)
#define SENSOR_OVERFLOW (1 << 2)
#define SENSOR_BUSY (1 << 3)
unsigned char sensorStatus = 0b00001001; // Binary literal
// Check if sensor is ready
if (sensorStatus & SENSOR_READY) {
cout << "Sensor ready!";
}
// Check if there's an error
if (sensorStatus & SENSOR_ERROR) {
cout << "Error detected!";
}
// Check multiple conditions
if ((sensorStatus & SENSOR_READY) &&
!(sensorStatus & SENSOR_BUSY)) {
cout << "Safe to read data!";
}
// Wait until sensor is not busy
while (sensorStatus & SENSOR_BUSY) {
// Read status register
sensorStatus = readSensorRegister();
}
Example 3: Configuration Flags
// Configuration options
#define ENABLE_WIFI (1 << 0)
#define ENABLE_BT (1 << 1)
#define ENABLE_GPS (1 << 2)
#define LOW_POWER_MODE (1 << 3)
#define DEBUG_MODE (1 << 4)
unsigned int config = 0;
// Enable WiFi and GPS
config |= (ENABLE_WIFI | ENABLE_GPS);
// config: 00000101
// Disable GPS
config &= ~ENABLE_GPS;
// config: 00000001
// Toggle debug mode
config ^= DEBUG_MODE;
// Check configuration
if (config & ENABLE_WIFI) {
initWiFi();
}
if (config & LOW_POWER_MODE) {
enterLowPowerMode();
}
Memory Comparison:
Traditional approach (8 flags):
bool wifi, bt, gps, lowpower, debug...
Total: 8 bytes (or more)
Bitwise approach (8 flags):
unsigned char config;
Total: 1 byte
Space saved: 87.5%
5. Common Patterns
Pattern 1: Set, Clear, Toggle Bit
// SET bit n
x |= (1 << n);
// CLEAR bit n
x &= ~(1 << n);
// TOGGLE bit n
x ^= (1 << n);
// CHECK if bit n is set
if (x & (1 << n)) { /* bit is set */ }
Example:
unsigned char x = 0b00101000; // 40
// Set bit 1
x |= (1 << 1);
// Result: 00101010 (42)
// Clear bit 3
x &= ~(1 << 3);
// Result: 00100010 (34)
// Toggle bit 5
x ^= (1 << 5);
// Result: 00000010 (2)
Pattern 2: Extract Bit Field
// Extract n bits starting from position p
unsigned int extract(unsigned int x, int p, int n) {
return (x >> p) & ~(~0 << n);
}
// Example: Extract 3 bits from position 2
unsigned int value = 0b11010110; // 214
unsigned int result = extract(value, 2, 3);
// Result: 101 (5)
Visual:
Original: 1 1 0 1 0 1 1 0
Position: 6 5 4 3 2 1 0
Extract 3 bits from position 2:
Step 1: Shift right by 2
0 0 1 1 0 1 0 1
Step 2: Mask lower 3 bits
0 0 0 0 0 1 0 1
& 1 1 1 (mask)
---------------
0 0 0 0 0 1 0 1 = 5
Pattern 3: Set Multiple Bits at Once
// Set bits 2, 4, and 6
x |= ((1 << 2) | (1 << 4) | (1 << 6));
// Clear bits 1, 3, and 5
x &= ~((1 << 1) | (1 << 3) | (1 << 5));
6. Practice Problems
Problem 1: Find the Only Non-Duplicate
Problem: Array has all numbers appearing twice except one. Find it.
int findUnique(vector<int>& arr) {
int result = 0;
for (int num : arr) {
result ^= num;
}
return result;
}
// Example:
vector<int> arr = {4, 2, 4, 5, 2};
cout << findUnique(arr); // Output: 5
Why It Works:
Property: x ^ x = 0, x ^ 0 = x
Step-by-step:
result = 0
result ^= 4 → 4
result ^= 2 → 4^2 = 6
result ^= 4 → 6^4 = 2 (4 cancelled!)
result ^= 5 → 2^5 = 7
result ^= 2 → 7^2 = 5 (2 cancelled!)
Result: 5
Problem 2: Reverse Bits
unsigned int reverseBits(unsigned int n) {
unsigned int result = 0;
for (int i = 0; i < 32; i++) {
result <<= 1; // Make room
result |= (n & 1); // Copy last bit
n >>= 1; // Move to next bit
}
return result;
}
// Example: 00000101 → 10100000
Visualization:
Input: 0 0 0 0 0 1 0 1
Iteration 1:
result = 0, take rightmost bit (1)
result = 1
Iteration 2:
result = 1 << 1 = 10, take next bit (0)
result = 10
Iteration 3:
result = 10 << 1 = 100, take next bit (1)
result = 101
... continues ...
Output: 1 0 1 0 0 0 0 0
Problem 3: Count Bits to Flip
Problem: How many bits need to flip to convert A to B?
int bitsToFlip(int a, int b) {
int xorResult = a ^ b; // Different bits are 1
return countSetBits(xorResult);
}
// Example:
int a = 10; // 1010
int b = 20; // 10100
// XOR: // 11110 (4 different bits)
cout << bitsToFlip(a, b); // Output: 4
Problem 4: Power Set Using Bits
void printPowerSet(vector<int>& arr) {
int n = arr.size();
int totalSubsets = 1 << n; // 2^n subsets
for (int i = 0; i < totalSubsets; i++) {
cout << "{ ";
for (int j = 0; j < n; j++) {
if (i & (1 << j)) { // Check if jth bit is set
cout << arr[j] << " ";
}
}
cout << "}" << endl;
}
}
// Example: {1, 2, 3}
// Output: {}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}
How It Works:
Array: [1, 2, 3]
Bits: 2 1 0
i=0 (000): {}
i=1 (001): {1} (bit 0 set)
i=2 (010): {2} (bit 1 set)
i=3 (011): {1, 2} (bits 0,1 set)
i=4 (100): {3} (bit 2 set)
i=5 (101): {1, 3} (bits 0,2 set)
i=6 (110): {2, 3} (bits 1,2 set)
i=7 (111): {1, 2, 3} (all bits set)
Problem 5: Find Two Non-Repeating Elements
Problem: All elements appear twice except two. Find both.
vector<int> findTwoUnique(vector<int>& arr) {
// Step 1: XOR all elements
int xorAll = 0;
for (int num : arr) {
xorAll ^= num;
}
// xorAll = a ^ b (the two unique numbers)
// Step 2: Find rightmost set bit
int rightmostBit = xorAll & -xorAll;
// Step 3: Divide array into two groups and XOR each
int group1 = 0, group2 = 0;
for (int num : arr) {
if (num & rightmostBit) {
group1 ^= num;
} else {
group2 ^= num;
}
}
return {group1, group2};
}
// Example: {2, 3, 7, 9, 11, 2, 3, 11}
// Output: {7, 9}
How It Works:
Array: [2, 3, 7, 9, 11, 2, 3, 11]
Step 1: XOR all = 7 ^ 9 = 1110
Step 2: Rightmost set bit of 1110 is bit 1 (0010)
Step 3: Partition by bit 1:
Group with bit 1 set: 2, 3, 2, 3 → XOR = 0 ^ 0 = 0... (wait, 7 has bit 1)
Group with bit 1 clear: 9, 11, 11 → XOR = 9
Result: 7 and 9
Problem 6: Missing Number from 1 to N
Problem: Array contains n-1 numbers from 1 to n. Find missing number.
int findMissing(vector<int>& arr, int n) {
int xorAll = 0;
// XOR all numbers from 1 to n
for (int i = 1; i <= n; i++) {
xorAll ^= i;
}
// XOR all array elements
for (int num : arr) {
xorAll ^= num;
}
return xorAll; // Missing number
}
// Example: arr = {1, 2, 4, 5}, n = 5
// Output: 3
Why It Works:
Numbers 1-5: 1 ^ 2 ^ 3 ^ 4 ^ 5
Array: 1 ^ 2 ^ 4 ^ 5
XOR result: 3 (since others cancel out)
Problem 7: Check Opposite Signs
Problem: Determine if two integers have opposite signs.
bool oppositeSigns(int a, int b) {
return (a ^ b) < 0;
}
// Alternative using AND:
bool oppositeSigns2(int a, int b) {
return (a < 0) != (b < 0); // Traditional way
// Bitwise: ((a ^ b) & (1 << 31)) != 0 (for 32-bit int)
}
// Example:
oppositeSigns(10, -5); // true
oppositeSigns(-10, -5); // false
oppositeSigns(10, 5); // false
How It Works:
Positive: 0xxx...
Negative: 1xxx... (two's complement)
XOR of sign bits:
Same sign: 0 (positive result)
Different sign: 1 (negative result)
Problem 8: Swap Odd and Even Bits
Problem: Swap all odd and even bits in an integer.
unsigned int swapOddEven(unsigned int n) {
// 0xAAAAAAAA = 10101010... (odd bits)
// 0x55555555 = 01010101... (even bits)
unsigned int evenBits = n & 0x55555555; // Extract even bits
unsigned int oddBits = n & 0xAAAAAAAA; // Extract odd bits
evenBits <<= 1; // Shift even bits left
oddBits >>= 1; // Shift odd bits right
return evenBits | oddBits;
}
// Example: 00010111 (23)
// Even bits (0, 2, 4, 6): 0001_1_ (extract: 00010101, shift left: 00101010)
// Odd bits (1, 3, 5, 7): _0_0_1 (extract: 00000010, shift right: 00000001)
// Result: 00101011 (43)
Visual:
Input: [7][6][5][4][3][2][1][0]
0 0 0 1 0 1 1 1
Even: 0 _ 0 _ 0 _ 1 _ → extract → 0 0 0 0 0 1 0 1
Odd: _ 0 _ 1 _ 1 _ 1 → extract → 0 0 0 1 0 1 1 0
Shift even left: 0 0 0 1 0 1 0 0
Shift odd right: 0 0 0 0 1 0 1 1
Combine: 0 0 1 0 1 0 1 1 = 43
Problem 9: Check Duplicate Characters (Bitmask)
Problem: Check if a string has duplicate characters using only O(1) space.
bool hasDuplicates(string str) {
int checker = 0;
for (char c : str) {
int bitPos = c - 'a'; // Assuming lowercase a-z
if (checker & (1 << bitPos)) {
return true; // Already seen this character
}
checker |= (1 << bitPos); // Mark as seen
}
return false;
}
// Example:
hasDuplicates("abcdef"); // false
hasDuplicates("abcdea"); // true (a repeats)
How It Works:
String: "abac"
c='a' (bit 0): checker = 00000001
c='b' (bit 1): checker = 00000011
c='a' (bit 0): Already set! → return true
Problem 10: Case Conversion Using Bits
Problem: Toggle case of alphabetic characters using bitwise operations.
char toggleCase(char c) {
// ASCII: 'A' = 65 (0100 0001), 'a' = 97 (0110 0001)
// Difference is bit 5 (0x20 = 32)
return c ^ 32; // or c ^ 0x20
}
char toLowerCase(char c) {
return c | 32; // Set bit 5
}
char toUpperCase(char c) {
return c & ~32; // Clear bit 5
}
// Example:
toggleCase('A'); // 'a'
toggleCase('a'); // 'A'
toLowerCase('B'); // 'b'
toUpperCase('x'); // 'X'
ASCII Bit Pattern:
'A' = 01000001
'a' = 01100001
^^^^ bit 5 is the difference
XOR with 32 (00100000) flips bit 5
OR with 32 sets bit 5 (lowercase)
AND with ~32 clears bit 5 (uppercase)
Problem 11: Rotate Bits
Problem: Rotate bits of a number left or right by k positions.
Formulas:
Rotate Left by k: (n << k) | (n >> (bits - k))
Rotate Right by k: (n >> k) | (n << (bits - k))
where 'bits' = total number of bits (e.g., 32 for int)
Implementation:
unsigned int rotateLeft(unsigned int n, int k, int bits = 32) {
k = k % bits; // Handle k > bits
return (n << k) | (n >> (bits - k));
}
unsigned int rotateRight(unsigned int n, int k, int bits = 32) {
k = k % bits; // Handle k > bits
return (n >> k) | (n << (bits - k));
}
// Example (8-bit for clarity):
// n = 11010110, k = 2
// rotateLeft(n, 2): 01011011
// rotateRight(n, 2): 10110101
Visualization (8-bit):
Original: n = 11010110 (214 in decimal)
ROTATE LEFT by k=2:
Formula: (n << 2) | (n >> (8-2))
= (n << 2) | (n >> 6)
Step 1: n << 2 = 01011000 (shift left, lose leftmost 2 bits)
Step 2: n >> 6 = 00000011 (shift right, get leftmost 2 bits)
Step 3: OR them = 01011011 (combine both parts)
Result: 01011011 (91 in decimal)
ROTATE RIGHT by k=2:
Formula: (n >> 2) | (n << (8-2))
= (n >> 2) | (n << 6)
Step 1: n >> 2 = 00110101 (shift right, lose rightmost 2 bits)
Step 2: n << 6 = 10000000 (shift left, get rightmost 2 bits)
Step 3: OR them = 10110101 (combine both parts)
Result: 10110101 (181 in decimal)
Key Insight:
Rotation = Circular shift (no bits are lost)
- Left rotation: bits that fall off the left reappear on the right
- Right rotation: bits that fall off the right reappear on the left
Shift vs Rotate:
Shift: bits fall off and are replaced with 0s
Rotate: bits wrap around to the other end
Problem 12: Maximum AND Value of Pair
Problem: Find the maximum bitwise AND of any two elements in an array.
int maxAND(vector<int>& arr) {
int result = 0;
int n = arr.size();
// Check bits from MSB to LSB
for (int bit = 31; bit >= 0; bit--) {
int count = 0;
int candidate = result | (1 << bit);
// Count how many numbers have this bit pattern
for (int num : arr) {
if ((num & candidate) == candidate) {
count++;
}
}
// If at least 2 numbers have this pattern, include this bit
if (count >= 2) {
result = candidate;
}
}
return result;
}
// Example: {3, 6, 5, 10, 12, 15}
// Output: 12 (from 12 & 15)
Approach:
Build result bit by bit from MSB:
- Try to set each bit starting from MSB
- Check if at least 2 numbers have this bit pattern
- If yes, keep the bit set
Example: [12, 15]
12 = 1100
15 = 1111
AND= 1100 = 12
7. Pro Tips
✅ DO’s
| Tip | Example |
|---|---|
| Use for powers of 2 | x << 3 instead of x * 8 |
| Combine with #define | #define BIT3 (1 << 3) |
| Use unsigned for shifts | Avoid sign extension issues |
| Comment bit manipulations | Code can be cryptic! |
| Test edge cases | 0, -1, max values |
❌ DON’Ts
| Mistake | Why |
|---|---|
| Shift by negative | Undefined behavior! |
| Shift >= type width | int x; x << 32 ⚠️ |
| Mix with arithmetic | -1 >> 1 depends on implementation |
| Forget parentheses | x & 1 << 2 vs x & (1 << 2) |
| Overuse for clarity | Sometimes x * 2 is clearer than x << 1 |
Quick Reference Card
// Basic Operations
x & y // AND
x | y // OR
x ^ y // XOR
~x // NOT
x << n // Left shift
x >> n // Right shift
// Common Patterns
x |= (1 << n) // Set bit n
x &= ~(1 << n) // Clear bit n
x ^= (1 << n) // Toggle bit n
x & (1 << n) // Check bit n
x & (x - 1) // Clear rightmost set bit
x & -x // Isolate rightmost set bit
x | (x - 1) // Set all bits right of rightmost set bit
~x & (x + 1) // Isolate rightmost 0 bit
// Quick Checks
x & 1 // Is odd?
!(x & (x - 1)) // Is power of 2?
x ^ x // Always 0
x ^ 0 // Always x
x ^ ~x // Always -1
Summary
Key Takeaways:
- Performance: Bitwise operations are 10-100x faster than arithmetic
- Memory efficiency: Pack multiple flags into single bytes
- Hardware control: Essential for embedded systems and low-level programming
- Clean solutions: Efficient approaches to complex problems
When to Use Bitwise:
- Embedded systems (registers, ports, hardware control)
- Performance-critical code (graphics, cryptography)
- Flag management (multiple boolean states)
- Algorithmic techniques (unique element, power of 2)
- Bit field manipulation
When NOT to Use:
- When it hurts readability for minimal gain
- When compiler optimizations do it automatically
- When team members don’t understand it
