Bitwise Operations in C/C++

20 Oct 2025 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 LR
    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

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

---

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 bits
• int: 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:

1. Performance: Bitwise operations are 10-100x faster than arithmetic
2. Memory efficiency: Pack multiple flags into single bytes
3. Hardware control: Essential for embedded systems and low-level programming
4. 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

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.