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

Mental Model

Bit manipulation changes numbers by flipping or moving their tiny on/off switches called bits.

Analogy: Imagine a row of light switches where each switch can be on (1) or off (0). Bit operations turn switches on, off, flip them, or slide the whole row left or right.

Number 13 in bits (8 bits):
0 0 0 0 1 1 0 1
Positions:          ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
                    7 6 5 4 3 2 1 0

Dry Run Walkthrough

Input: number1 = 13 (00001101), number2 = 10 (00001010)

Goal: Show how AND, OR, XOR, NOT, left shift, and right shift change bits of these numbers

Step 1: Perform AND between 13 and 10

00001101 (13) AND 00001010 (10) = 00001000 (8)

Why: AND keeps bits ON only if both numbers have that bit ON

Step 2: Perform OR between 13 and 10

00001101 (13) OR 00001010 (10) = 00001111 (15)

Why: OR turns bits ON if either number has that bit ON

Step 3: Perform XOR between 13 and 10

00001101 (13) XOR 00001010 (10) = 00000111 (7)

Why: XOR turns bits ON only if bits differ between numbers

Step 4: Perform NOT on 13

NOT 00001101 (13) = 11110010 (in 8-bit, equals 242 unsigned or -14 signed)

Why: NOT flips every bit from ON to OFF or OFF to ON

Step 5: Left shift 13 by 2 bits

00001101 (13) << 2 = 00110100 (52)

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

Step 6: Right shift 13 by 2 bits

00001101 (13) >> 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 result: 11110010 (242 unsigned)
Left shift result: 00110100 (52)
Right shift result: 00000011 (3)

Annotated Code

DSA C#

using System;

class BitManipulation {
    public static void Main() {
        byte number1 = 13; // 00001101
        byte number2 = 10; // 00001010

        byte andResult = (byte)(number1 & number2); // AND
        byte orResult = (byte)(number1 | number2);  // OR
        byte xorResult = (byte)(number1 ^ number2); // XOR
        byte notResult = (byte)(~number1);          // NOT
        byte leftShiftResult = (byte)(number1 << 2); // Left shift by 2
        byte rightShiftResult = (byte)(number1 >> 2); // Right shift by 2

        Console.WriteLine("AND result: " + Convert.ToString(andResult, 2).PadLeft(8, '0') + " (" + andResult + ")");
        Console.WriteLine("OR result: " + Convert.ToString(orResult, 2).PadLeft(8, '0') + " (" + orResult + ")");
        Console.WriteLine("XOR result: " + Convert.ToString(xorResult, 2).PadLeft(8, '0') + " (" + xorResult + ")");
        Console.WriteLine("NOT result: " + Convert.ToString(notResult, 2).PadLeft(8, '0') + " (" + notResult + ")");
        Console.WriteLine("Left shift result: " + Convert.ToString(leftShiftResult, 2).PadLeft(8, '0') + " (" + leftShiftResult + ")");
        Console.WriteLine("Right shift result: " + Convert.ToString(rightShiftResult, 2).PadLeft(8, '0') + " (" + rightShiftResult + ")");
    }
}

byte andResult = (byte)(number1 & number2);

perform AND to keep bits ON only if both bits are ON

byte orResult = (byte)(number1 | number2);

perform OR to turn bits ON if either bit is ON

byte xorResult = (byte)(number1 ^ number2);

perform XOR to turn bits ON only if bits differ

byte notResult = (byte)(~number1);

flip all bits using NOT

byte leftShiftResult = (byte)(number1 << 2);

shift bits left by 2, adding zeros on right

byte rightShiftResult = (byte)(number1 >> 2);

shift bits right by 2, dropping bits on right

Output

AND result: 00001000 (8)

OR result: 00001111 (15)

XOR result: 00000111 (7)

NOT result: 11110010 (242)

Left shift result: 00110100 (52)

Right shift result: 00000011 (3)

Complexity Analysis

Time: O(1) because bit operations happen in constant time regardless of number size

Space: O(1) because only a fixed number of variables are used

vs Alternative: Bit manipulation is much faster and uses less memory than arithmetic operations for these tasks

Edge Cases

number is zero

AND, OR, XOR with zero behave normally; NOT flips all bits; shifts produce zero

DSA C#

N/A - no special code needed as bit ops handle zero naturally

left shift causes bits to move out of byte range

bits shifted out are lost, result fits in byte with overflow

DSA C#

byte leftShiftResult = (byte)(number1 << 2);

right shift on zero

result remains zero

DSA C#

byte rightShiftResult = (byte)(number1 >> 2);

When to Use This Pattern

When you need to quickly check, flip, or move individual bits in numbers, use bit manipulation because it is fast and memory efficient.

Common Mistakes

Mistake: Forgetting to cast the result back to byte after bit operations causing type errors
Fix: Always cast the result explicitly to byte to keep the correct type

Mistake: Confusing left shift with multiplication without considering overflow
Fix: Remember left shift multiplies by powers of two but can lose bits if shifted too far

Summary

Bit manipulation changes numbers by turning bits on/off, flipping them, or shifting their positions.

Use it when you want fast, low-level control over individual bits in numbers.

Think of bits as tiny switches you can flip or slide left/right to change the number efficiently.

Practice

1. What does the bitwise AND operator (&) do when applied to two bits?

easy

A. Returns 0 only if both bits are 0

B. Returns 1 if either bit is 1

C. Flips the bits from 0 to 1 and 1 to 0

D. Returns 1 only if both bits are 1

Solution

1. Step 1: Understand bitwise AND operation

   The AND operator compares each bit of two numbers and returns 1 only if both bits are 1.

2. Step 2: Apply to example bits

   For bits 1 & 1, result is 1; for 1 & 0 or 0 & 1 or 0 & 0, result is 0.

3. Final Answer:

   Returns 1 only if both bits are 1 -> Option D

4. Quick Check:

   AND = 1 only if both bits 1 [OK]

Hint: AND returns 1 only when both bits are 1 [OK]

Common Mistakes:

• Confusing AND with OR operator
• Thinking AND flips bits
• Assuming AND returns 1 if either bit is 1

2. Which of the following is the correct syntax to perform a left shift by 2 on an integer variable x in C#?

easy

A. x >> 2;

B. x << 2;

C. x <<< 2;

D. x >> 2 <<;

Solution

1. Step 1: Recall left shift operator syntax in C#

   The left shift operator is << and used as x << n to shift bits left by n places.

2. Step 2: Identify correct syntax among options

   x << 2; uses x << 2; which is correct. x >> 2; is right shift, C uses invalid operator, D is invalid syntax.

3. Final Answer:

   x << 2; -> Option B

4. Quick Check:

   Left shift syntax is x << n [OK]

Hint: Use << for left shift, >> for right shift [OK]

Common Mistakes:

• Using >>> which is invalid in C#
• Confusing left shift with right shift
• Adding extra symbols after shift operator

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

int a = 5; // binary 0101
int b = 3; // binary 0011
int c = a ^ b;
Console.WriteLine(c);

medium

A. 2

B. 7

C. 6

D. 8

Solution

1. Step 1: Convert numbers to binary and apply XOR

   5 in binary is 0101, 3 is 0011. XOR (^) returns 1 if bits differ, else 0.

2. Step 2: Calculate XOR bit by bit

   0101 ^ 0011 = 0110 (binary), which is 6 in decimal.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   5 ^ 3 = 6 [OK]

Hint: XOR sets bits where inputs differ [OK]

Common Mistakes:

• Confusing XOR with OR or AND
• Calculating decimal sum instead of XOR
• Misreading binary values

4. Identify the error in the following C# code snippet that attempts to invert bits of an integer num:

int num = 12;
int inverted = ~num();
Console.WriteLine(inverted);

medium

A. Using parentheses after variable name num()

B. Using bitwise NOT operator incorrectly

C. Missing semicolon after int num = 12

D. Console.WriteLine cannot print integers

Solution

1. Step 1: Check usage of variable num

   The code uses num() which looks like a function call but num is an integer variable, so parentheses are invalid.

2. Step 2: Confirm bitwise NOT operator usage

   The bitwise NOT operator ~ is correctly used before the variable, so no error there.

3. Final Answer:

   Using parentheses after variable name num() -> Option A

4. Quick Check:

   Variables don't use () [OK]

Hint: Variables are not functions; no () after variable names [OK]

Common Mistakes:

• Thinking ~num() is valid syntax
• Assuming missing semicolon error
• Believing Console.WriteLine can't print integers

5. Given an integer n = 8, which expression correctly checks if n is a power of two using bit manipulation in C#?

hard

A. (n & (n - 1)) == 0

B. (n | (n - 1)) == 0

C. (n ^ (n - 1)) == 0

D. (~n & (n - 1)) == 0

Solution

1. Step 1: Understand the power of two property

   A number is a power of two if it has exactly one bit set to 1 in binary.

2. Step 2: Apply bitwise trick

   For such numbers, n & (n - 1) clears the lowest set bit. If result is 0, n was a power of two.

3. Final Answer:

   (n & (n - 1)) == 0 -> Option A

4. Quick Check:

   Power of two check uses n & (n-1) == 0 [OK]

Hint: Power of two if n & (n-1) equals zero [OK]

Common Mistakes:

• Using OR or XOR instead of AND
• Forgetting to compare result to zero
• Misunderstanding bitwise NOT usage