Bit Manipulation Basics AND OR XOR NOT Left Right Shift in DSA Typescript - Time & Space Complexity

Time Complexity: Bit Manipulation Basics AND OR XOR NOT Left Right Shift

O(b)

Understanding Time Complexity

Bit manipulation operations are basic steps computers use to handle numbers at the smallest level.

We want to know how the time to do these operations changes as the number size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function bitOpsExample(x: number, y: number): number {
  const andResult = x & y;
  const orResult = x | y;
  const xorResult = x ^ y;
  const notResult = ~x;
  const leftShift = x << 2;
  const rightShift = y >> 3;
  return andResult + orResult + xorResult + notResult + leftShift + rightShift;
}
    

This code performs basic bit operations on two numbers and combines the results.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Each bitwise operation (&, |, ^, ~, <<, >>) processes all bits of the input numbers.
• How many times: Each operation touches each bit once, so the count depends on the number of bits in the numbers.

How Execution Grows With Input

As the number size grows, the number of bits grows too, so the work grows with the bit length.

Input Size (bits)	Approx. Operations
8 (1 byte)	~8 operations per bitwise call
32 (standard int)	~32 operations per bitwise call
64 (long int)	~64 operations per bitwise call

Pattern observation: The time grows linearly with the number of bits in the input numbers.

Final Time Complexity

Time Complexity: O(b) where b is the number of bits in the input numbers.

This means the time to do bit operations grows linearly with the bit length of the numbers.

Common Mistake

[X] Wrong: "Bitwise operations take constant time no matter the number size."

[OK] Correct: Actually, the time depends on how many bits the number has, so bigger numbers take more steps.

Interview Connect

Understanding bit operation time helps you explain how low-level data handling works and shows you can think about efficiency even in simple steps.

Self-Check

"What if we used fixed-size 32-bit integers regardless of input size? How would the time complexity change?"

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