Bit Manipulation Basics AND OR XOR NOT Left Right Shift in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the AND (&) bitwise operator do between two bits?

The AND operator returns 1 only if both bits are 1; otherwise, it returns 0.
Example: 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0.

beginner

Explain the OR (|) bitwise operator with an example.

The OR operator returns 1 if at least one of the bits is 1; otherwise, it returns 0.
Example: 1 | 0 = 1, 0 | 0 = 0.

beginner

What is the result of XOR (^) between two bits?

XOR returns 1 if the bits are different, and 0 if they are the same.
Example: 1 ^ 0 = 1, 1 ^ 1 = 0.

beginner

What does the NOT (~) operator do to a bit?

The NOT operator flips the bit: 0 becomes 1, and 1 becomes 0.
Example: ~0 = 1, ~1 = 0 (in single bit context).

beginner

What is the effect of left shift (<<) and right shift (>>) operators on a number?

Left shift (<<) moves bits to the left, adding zeros on the right, effectively multiplying by 2 for each shift.
Right shift (>>) moves bits to the right, discarding bits on the right, effectively dividing by 2 for each shift.
Example: 4 << 1 = 8, 8 >> 1 = 4.

What is the result of 5 & 3 in binary? (5 = 0101, 3 = 0011)

A 0010 (2)

B 0111 (7)

C 0001 (1)

D 0100 (4)

AND compares bits: 0101 & 0011 = 0001 which is 1 in decimal.

What does 6 | 3 equal? (6 = 0110, 3 = 0011)

A 0111 (7)

B 0001 (1)

C 0101 (5)

D 0010 (2)

OR compares bits: 0110 | 0011 = 0111 which is 7 in decimal.

What is the result of 4 ^ 5? (4 = 0100, 5 = 0101)

A 0001 (1)

B 0101 (5)

C 1101 (13)

D 0111 (7)

XOR compares bits: 0100 ^ 0101 = 0001 which is 1 in decimal.

If x = 8 (1000), what is x >> 2?

A 0010 (2)

B 0100 (4)

C 1000 (8)

D 0001 (1)

Right shift by 2 moves bits right twice: 1000 >> 2 = 0010 (2).

What is the result of ~0 in a 4-bit system?

A 0000 (0)

B 1111 (15)

C 1000 (8)

D 0111 (7)

NOT flips all bits: ~0000 = 1111 which is 15 in decimal.

Explain how the AND, OR, and XOR bitwise operators work with simple examples.

Think about comparing two bits and when the result is 1 or 0.

Describe what happens when you use left shift (<<) and right shift (>>) on a number in binary.

Imagine moving digits in a number to the left or 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