Bit Manipulation Basics AND OR XOR NOT Left Right Shift in DSA C++

Mental Model

Bits are tiny switches that can be on or off. Bit manipulation changes these switches directly to do fast math and logic.

Analogy: Imagine a row of light switches where each switch can be turned on or off. Bit operations flip, combine, or shift these switches to create new patterns.

Bits: 0 1 0 1 1 0 0 1
Positions: 7 6 5 4 3 2 1 0
Operations: AND, OR, XOR, NOT, <<, >>

Dry Run Walkthrough

Input: a = 13 (binary 00001101), b = 10 (binary 00001010)

Goal: Show results of AND, OR, XOR, NOT, left shift, and right shift on a and b

Step 1: Calculate a AND b

a: 00001101 (13)
b: 00001010 (10)
a AND b: 00001000 (8)

Why: AND keeps bits on only if both bits are on

Step 2: Calculate a OR b

a: 00001101 (13)
b: 00001010 (10)
a OR b: 00001111 (15)

Why: OR turns bits on if either bit is on

Step 3: Calculate a XOR b

a: 00001101 (13)
b: 00001010 (10)
a XOR b: 00000111 (7)

Why: XOR turns bits on only if bits differ

Step 4: Calculate NOT a (invert bits)

a: 00001101 (13)
NOT a: 11110010 (binary inverted, -14 in two's complement)

Why: NOT flips every bit from 0 to 1 or 1 to 0

Step 5: Left shift a by 2 bits (a << 2)

a: 00001101 (13)
a << 2: 00110100 (52)

Why: Left shift moves bits left, adding zeros on right, multiplying by 4

Step 6: Right shift a by 2 bits (a >> 2)

a: 00001101 (13)
a >> 2: 00000011 (3)

Why: Right shift moves bits right, dropping bits on right, dividing by 4

Result:

AND result: 00001000 (8)
OR result: 00001111 (15)
XOR result: 00000111 (7)
NOT a result: 11110010 (-14)
Left shift a << 2: 00110100 (52)
Right shift a >> 2: 00000011 (3)

Annotated Code

DSA C++

#include <iostream>
#include <bitset>

using namespace std;

void print_bits(int n) {
    cout << bitset<8>(n) << " (" << n << ")" << endl;
}

int main() {
    int a = 13; // 00001101
    int b = 10; // 00001010

    cout << "a: "; print_bits(a);
    cout << "b: "; print_bits(b);

    int and_result = a & b;
    cout << "a AND b: "; print_bits(and_result);

    int or_result = a | b;
    cout << "a OR b: "; print_bits(or_result);

    int xor_result = a ^ b;
    cout << "a XOR b: "; print_bits(xor_result);

    int not_a = ~a;
    cout << "NOT a: "; print_bits(not_a);

    int left_shift = a << 2;
    cout << "a << 2: "; print_bits(left_shift);

    int right_shift = a >> 2;
    cout << "a >> 2: "; print_bits(right_shift);

    return 0;
}

int and_result = a & b;

compute bitwise AND to keep bits on only if both bits are on

int or_result = a | b;

compute bitwise OR to turn bits on if either bit is on

int xor_result = a ^ b;

compute bitwise XOR to turn bits on only if bits differ

int not_a = ~a;

compute bitwise NOT to flip every bit

int left_shift = a << 2;

shift bits left by 2, adding zeros on right (multiply by 4)

int right_shift = a >> 2;

shift bits right by 2, dropping bits on right (divide by 4)

Output

a: 00001101 (13)

b: 00001010 (10)

a AND b: 00001000 (8)

a OR b: 00001111 (15)

a XOR b: 00000111 (7)

NOT a: 11110010 (-14)

a << 2: 00110100 (52)

a >> 2: 00000011 (3)

Complexity Analysis

Time: O(1) because bitwise operations work on fixed-size integers directly

Space: O(1) because no extra memory grows with input size

vs Alternative: Bit manipulation is faster and uses less memory than arithmetic or logical operations done by loops

Edge Cases

a or b is zero

AND, OR, XOR behave correctly with zero bits; shifts produce zero or shifted zero

DSA C++

int and_result = a & b;

shifting by zero bits

value remains unchanged

DSA C++

int left_shift = a << 0;

NOT operation on zero

all bits become 1 (e.g., ~0 = -1 in two's complement)

DSA C++

int not_a = ~a;

When to Use This Pattern

When you need fast, low-level control of data or want to do math with bits, use bit manipulation because it works directly on binary switches.

Common Mistakes

Mistake: Confusing left shift with multiplication by 2 without considering overflow
Fix: Remember left shift multiplies by powers of two only if no bits are lost beyond the fixed size

Mistake: Using NOT without understanding two's complement representation
Fix: Know that NOT flips bits and results may be negative due to two's complement

Summary

Bit manipulation changes individual bits to perform fast logic and math.

Use it when you want efficient, low-level operations on numbers.

Think of bits as switches you can turn on, off, flip, or move left and right.

Practice

1. What is the result of the bitwise AND operation between 5 and 3? (In binary, 5 = 0101, 3 = 0011)

easy

A. 0

B. 1

C. 6

D. 7

Solution

1. Step 1: Convert numbers to binary

   5 in binary is 0101, 3 in binary is 0011.

2. Step 2: Perform bitwise AND

   0101 AND 0011 = 0001 (only bits where both are 1 remain 1).

3. Final Answer:

   1 -> Option B

4. Quick Check:

   5 & 3 = 1 [OK]

Hint: AND keeps bits set in both numbers only [OK]

Common Mistakes:

• Confusing AND with OR operation
• Not converting decimal to binary correctly
• Assuming bitwise AND adds numbers

2. Which of the following is the correct syntax for performing a left shift by 2 bits on an integer variable x in C++?

easy

A. x << 2;

B. x >> 2;

C. x <<< 2;

D. x >> 2 <<;

Solution

1. Step 1: Understand left shift operator

   In C++, left shift is done using << operator.

2. Step 2: Check syntax correctness

   x << 2; uses x << 2; which is correct syntax for left shift by 2 bits.

3. Final Answer:

   x << 2; -> Option A

4. Quick Check:

   Left shift uses << operator [OK]

Hint: Left shift uses <<, right shift uses >> [OK]

Common Mistakes:

• Using >>> which is not valid in C++
• Confusing left shift with right shift
• Adding extra symbols after operator

3. What is the output of the following C++ code?

int x = 12;  // binary 1100
int y = 5;   // binary 0101
int z = x ^ y;
std::cout << z << std::endl;

medium

A. 8

B. 15

C. 9

D. 7

Solution

1. Step 1: Convert numbers to binary

   x = 12 (1100), y = 5 (0101).

2. Step 2: Perform bitwise XOR

   1100 XOR 0101 = 1001 (bits differ become 1).

3. Step 3: Convert result back to decimal

   1001 in decimal is 9.

4. Final Answer:

   9 -> Option C

5. Quick Check:

   12 ^ 5 = 9 [OK]

Hint: XOR sets bits where inputs differ [OK]

Common Mistakes:

• Mixing XOR with OR or AND
• Not converting binary to decimal correctly
• Assuming XOR adds numbers

4. Identify the error in the following C++ code snippet:

int a = 8;
int b = a >> 2;
int c = ~b;
std::cout << c << std::endl;

medium

A. No error; code runs and prints the result

B. Using bitwise NOT (~) on an integer is invalid

C. Right shift operator (>>) is used incorrectly

D. Missing semicolon after variable declaration

Solution

1. Step 1: Check each operation

   Right shift (>>) on integer 8 by 2 bits is valid: 8 (1000) >> 2 = 2 (0010).

2. Step 2: Check bitwise NOT usage

   Bitwise NOT (~) on integer 2 flips bits; this is valid in C++.

3. Step 3: Verify syntax

   All semicolons are present; code compiles and runs.

4. Final Answer:

   No error; code runs and prints the result -> Option A

5. Quick Check:

   Bitwise NOT and shifts are valid [OK]

Hint: Bitwise NOT and shifts are valid on integers [OK]

Common Mistakes:

• Thinking ~ is invalid on integers
• Confusing shift direction
• Assuming missing semicolon without checking

5. Given an integer n = 29, which of the following expressions correctly clears (sets to 0) the 3rd bit (counting from 0, right to left) using bit manipulation?

hard

A. ~n & (1 << 3)

B. n | (1 << 3)

C. n ^ (1 << 3)

D. n & ~(1 << 3)

Solution

1. Step 1: Understand clearing a bit

   To clear a bit, use AND with NOT mask that has 1 at target bit.

2. Step 2: Analyze each option

   n & ~(1 << 3): n & ~(1 << 3) clears 3rd bit correctly.
   n | (1 << 3): n | (1 << 3) sets 3rd bit.
   n ^ (1 << 3): n ^ (1 << 3) toggles 3rd bit.
   ~n & (1 << 3): ~n & (1 << 3) isolates 3rd bit of inverted n, not clearing.

3. Final Answer:

   n & ~(1 << 3) -> Option D

4. Quick Check:

   Clear bit = AND with NOT mask [OK]

Hint: Clear bit: AND with NOT of bit mask [OK]

Common Mistakes:

• Using OR instead of AND to clear bits
• Confusing toggle (XOR) with clear
• Misunderstanding bit indexing