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

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
Bits:  0 0 0 0 1 1 0 1
Index: 7 6 5 4 3 2 1 0

Dry Run Walkthrough

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

Goal: Show how AND, OR, XOR, NOT, Left Shift, and Right Shift change bits of these numbers

Step 1: Perform AND between number1 and number2

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 number1 and number2

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

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

Step 3: Perform XOR between number1 and number2

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

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

Step 4: Perform NOT on number1

NOT 00001101 (13) = 11110010 (in 8-bit, equals -14 in two's complement)

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

Step 5: Left shift number1 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 number1 by 2 bits

00001101 (13) >> 2 = 00000011 (3)

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

Result:

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

Annotated Code

DSA Typescript

class BitManipulation {
  static and(a: number, b: number): number {
    return a & b; // bitwise AND keeps bits ON only if both bits are ON
  }

  static or(a: number, b: number): number {
    return a | b; // bitwise OR turns bits ON if either bit is ON
  }

  static xor(a: number, b: number): number {
    return a ^ b; // bitwise XOR turns bits ON only if bits differ
  }

  static not(a: number): number {
    return ~a; // bitwise NOT flips all bits
  }

  static leftShift(a: number, n: number): number {
    return a << n; // shift bits left by n, adding zeros on right
  }

  static rightShift(a: number, n: number): number {
    return a >> n; // shift bits right by n, dropping bits on right
  }
}

// Driver code
const number1 = 13; // 00001101
const number2 = 10; // 00001010

console.log("AND result:", BitManipulation.and(number1, number2));
console.log("OR result:", BitManipulation.or(number1, number2));
console.log("XOR result:", BitManipulation.xor(number1, number2));
console.log("NOT result:", BitManipulation.not(number1));
console.log("Left shift result:", BitManipulation.leftShift(number1, 2));
console.log("Right shift result:", BitManipulation.rightShift(number1, 2));

return a & b; // bitwise AND keeps bits ON only if both bits are ON

perform AND operation to keep bits ON only if both inputs have ON bits

return a | b; // bitwise OR turns bits ON if either bit is ON

perform OR operation to turn bits ON if either input has ON bit

return a ^ b; // bitwise XOR turns bits ON only if bits differ

perform XOR operation to turn bits ON only if bits differ

return ~a; // bitwise NOT flips all bits

flip every bit from ON to OFF or OFF to ON

return a << n; // shift bits left by n, adding zeros on right

move bits left by n positions, adding zeros on right

return a >> n; // shift bits right by n, dropping bits on right

move bits right by n positions, dropping bits on right

Output

AND result: 8

OR result: 15

XOR result: 7

NOT result: -14

Left shift result: 52

Right shift result: 3

Complexity Analysis

Time: O(1) because bitwise operations work directly on fixed-size bits without loops

Space: O(1) because no extra memory is needed beyond input and output variables

vs Alternative: Bitwise operations are much faster and use less memory than arithmetic or logical operations that simulate bit changes

Edge Cases

number is zero

AND, OR, XOR with zero produce predictable results; NOT flips all bits of zero

DSA Typescript

return a & b; // bitwise AND keeps bits ON only if both bits are ON

left shift by zero bits

number remains unchanged

DSA Typescript

return a << n; // shift bits left by n, adding zeros on right

right shift by more bits than number length

result becomes zero

DSA Typescript

return a >> n; // shift bits right by n, dropping bits on right

When to Use This Pattern

When you need to quickly check, flip, or move individual bits in numbers, use bit manipulation because it works directly on the binary form for speed and simplicity.

Common Mistakes

Mistake: Confusing left shift with multiplication by powers of two without considering overflow
Fix: Remember left shift multiplies by 2^n only if no bits are lost; otherwise, result may wrap or lose data

Mistake: Using NOT operator without understanding two's complement representation
Fix: Know that NOT flips bits and changes sign in two's complement, so result may be negative

Summary

Bit manipulation changes numbers by turning bits on/off or moving them left/right.

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

The key insight is that numbers are just switches (bits) that you can flip or slide to get new values.

Practice

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

easy

A. 1

B. 7

C. 6

D. 0

Solution

1. Step 1: Convert numbers to binary

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

2. Step 2: Perform bitwise AND operation

   0101 AND 0011 = 0001 (only bits set in both numbers remain set).

3. Final Answer:

   1 -> Option A

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 numbers to binary before operation
• Assuming decimal addition instead of bitwise operation

2. Which of the following is the correct TypeScript syntax to perform a bitwise XOR between variables a and b?

easy

A. let result = a && b;

B. let result = a % b;

C. let result = a | b;

D. let result = a ^ b;

Solution

1. Step 1: Identify bitwise XOR operator in TypeScript

   The bitwise XOR operator is the caret symbol (^).

2. Step 2: Check each option for correct syntax

   let result = a ^ b; uses ^ correctly. let result = a && b; uses logical AND (&&), let result = a | b; uses bitwise OR (|), let result = a % b; uses modulus (%).

3. Final Answer:

   let result = a ^ b; -> Option D

4. Quick Check:

   Bitwise XOR uses ^ operator [OK]

Hint: XOR operator is ^ in TypeScript [OK]

Common Mistakes:

• Using logical operators instead of bitwise
• Confusing OR (|) with XOR (^)
• Using modulus operator (%) by mistake

3. What is the output of the following TypeScript code?

const x = 8; // binary 1000
const y = x >> 2;
console.log(y);

medium

A. 0

B. 2

C. 1

D. 4

Solution

1. Step 1: Understand right shift operation

   Right shift (>>) moves bits to the right by the specified number, dropping rightmost bits.

2. Step 2: Apply right shift to 8 (1000 binary)

   Shifting 1000 right by 2 bits gives 0010 binary, which is 2 in decimal.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   8 >> 2 = 2 [OK]

Hint: Right shift divides by 2 for each shift [OK]

Common Mistakes:

• Confusing right shift with left shift
• Not converting binary to decimal after shift
• Assuming shift adds zeros on left without dropping bits

4. Identify the error in this TypeScript code snippet:

let a = 5;
let b = 3;
let c = a <<< b;
console.log(c);

medium

A. <<< is not a valid bitwise operator

B. Variables a and b must be strings

C. Missing semicolon after variable declarations

D. Bitwise operators cannot be used with let variables

Solution

1. Step 1: Check the bitwise operators in TypeScript

   Valid bitwise shift operators are << (left shift) and >> (right shift). There is no <<< operator.

2. Step 2: Identify the invalid operator usage

   The code uses <<< which is invalid syntax and will cause an error.

3. Final Answer:

   <<< is not a valid bitwise operator -> Option A

4. Quick Check:

   Only << and >> are valid shift operators [OK]

Hint: Use only << or >> for shifts, not <<< or >>> [OK]

Common Mistakes:

• Using triple shift operator like in some other languages
• Assuming semicolons are mandatory for correctness
• Thinking bitwise operators require specific variable types

5. Given n = 29 (binary 11101), which expression will toggle the 3rd bit (counting from 0 at right) using bitwise XOR in TypeScript?
Choose the correct code snippet.

hard

A. let result = n | (1 << 3);

B. let result = n & (1 << 3);

C. let result = n ^ (1 << 3);

D. let result = ~n ^ (1 << 3);

Solution

1. Step 1: Understand toggling a bit with XOR

   XOR with 1 flips the bit; XOR with 0 leaves it unchanged.

2. Step 2: Create mask for 3rd bit

   1 << 3 shifts 1 to the 3rd bit position (binary 1000).

3. Step 3: Apply XOR to toggle the bit

   n ^ (1 << 3) flips the 3rd bit of n.

4. Final Answer:

   let result = n ^ (1 << 3); -> Option C

5. Quick Check:

   XOR with mask toggles bit [OK]

Hint: XOR with 1 at bit toggles it, 0 leaves it same [OK]

Common Mistakes:

• Using AND or OR instead of XOR to toggle bits
• Incorrect bit position shift
• Using NOT operator incorrectly with XOR