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

Overview - Bit Manipulation Basics AND OR XOR NOT Left Right Shift

What is it?

Bit manipulation is a way to work directly with the tiny pieces inside numbers called bits. Bits are like tiny switches that can be on (1) or off (0). Using special operations like AND, OR, XOR, NOT, and shifting bits left or right, we can change or check these bits quickly. This helps computers do tasks faster and use less memory.

Why it matters

Without bit manipulation, computers would have to handle numbers and data in bigger chunks, which is slower and uses more space. Bit manipulation lets us solve problems like checking flags, encrypting data, or optimizing performance in games and apps. It makes programs faster and more efficient, which is important in real-world software and devices.

Where it fits

Before learning bit manipulation, you should understand basic number systems like binary and decimal. After this, you can learn about advanced algorithms that use bits, like fast math tricks, compression, or cryptography.

Mental Model

Core Idea

Bit manipulation is about flipping, combining, and moving tiny on/off switches inside numbers to control data efficiently.

Think of it like...

Imagine a row of light switches in your house, each switch can be ON or OFF. Bit manipulation is like flipping these switches on or off, combining their states, or sliding the whole row left or right to change the pattern.

Number bits example (8 bits):

  Bit positions: 7 6 5 4 3 2 1 0
  Number:        0 1 1 0 1 0 1 1

Operations:
  AND: 1 & 0 = 0 (both must be ON)
  OR:  1 | 0 = 1 (either ON)
  XOR: 1 ^ 0 = 1 (only one ON)
  NOT: ~1 = 0 (flip switch)
  Left Shift: move bits left, add 0 on right
  Right Shift: move bits right, add 0 or copy sign on left

Build-Up - 7 Steps

1

Foundation

Understanding Binary Numbers

Concept: Learn how numbers are stored as bits using binary (0s and 1s).

Every number in a computer is stored as a sequence of bits. Each bit is a 0 or 1. For example, the number 13 in binary is 00001101 (8 bits). Each bit position represents a power of 2, starting from the right (2^0). Adding bits together gives the number's value.

Result

You can read and write numbers in binary, understanding how each bit contributes to the total value.

Understanding binary is the foundation for all bit manipulation because bits are the building blocks of data in computers.

2

Foundation

Basic Bitwise Operators Explained

Concept: Introduce AND, OR, XOR, and NOT operators that work on bits.

Bitwise AND (&) compares two bits and returns 1 only if both are 1. Bitwise OR (|) returns 1 if at least one bit is 1. Bitwise XOR (^) returns 1 if bits are different. Bitwise NOT (~) flips each bit (1 becomes 0, 0 becomes 1). Example: 5 (0101) & 3 (0011) = 1 (0001).

Result

You can combine or flip bits to create new bit patterns.

Knowing these operators lets you control individual bits, which is faster and more memory-efficient than working with whole numbers.

3

Intermediate

Using Left and Right Bit Shifts

🤔Before reading on: do you think shifting bits left multiplies or divides the number? Commit to your answer.

Concept: Learn how shifting bits left or right moves bits and changes the number's value.

Left shift (<<) moves bits to the left, adding zeros on the right. This usually multiplies the number by 2 for each shift. Right shift (>>) moves bits to the right, dropping bits on the right and adding zeros or copying the sign bit on the left. This usually divides the number by 2 for each shift. Example: 4 (0100) << 1 = 8 (1000), 8 >> 2 = 2 (0010).

Result

You can quickly multiply or divide numbers by powers of two using shifts.

Understanding shifts helps optimize math operations and manipulate bits efficiently.

4

Intermediate

Combining Operators for Bit Masks

🤔Before reading on: do you think you can use AND and OR together to select and change specific bits? Commit to your answer.

Concept: Use bitwise operators to create masks that select or change specific bits in a number.

A bit mask is a number where certain bits are set to 1 to select or change bits in another number. Use AND with a mask to check if bits are set. Use OR with a mask to turn bits on. Use XOR with a mask to flip bits. Example: To check if the 3rd bit is on in 13 (1101), AND with 4 (0100): 1101 & 0100 = 0100 (non-zero means bit is on).

Result

You can test, set, or flip specific bits inside numbers.

Masks let you control parts of data precisely, which is key in flags, permissions, and low-level programming.

5

Intermediate

Implementing Bit Manipulation in TypeScript

🤔Before reading on: do you think TypeScript uses the same bitwise operators as other languages? Commit to your answer.

Concept: Learn how to write bit manipulation code using TypeScript syntax.

TypeScript supports bitwise operators like &, |, ^, ~, <<, and >>. Example code: const a = 5; // 0101 const b = 3; // 0011 const andResult = a & b; // 0001 = 1 const orResult = a | b; // 0111 = 7 const xorResult = a ^ b; // 0110 = 6 const notResult = ~a; // flips bits const leftShift = a << 1; // 1010 = 10 const rightShift = a >> 1; // 0010 = 2

Result

You can write and run bit manipulation code in TypeScript.

Knowing the syntax lets you apply bit tricks in real programming tasks.

6

Advanced

Handling Signed Numbers and Shift Behavior

🤔Before reading on: do you think right shift always adds zeros on the left? Commit to your answer.

Concept: Understand how signed numbers affect bit shifts and the difference between logical and arithmetic shifts.

In signed numbers, the leftmost bit is the sign bit (0 for positive, 1 for negative). Right shift can be arithmetic (>>), which copies the sign bit to keep the sign, or logical (>>>), which adds zeros. Example: -8 in 8 bits is 11111000. -8 >> 2 = 11111110 (keeps negative sign) -8 >>> 2 = 00111110 (treats as positive number). TypeScript uses >>> for logical right shift.

Result

You can correctly shift signed numbers without changing their sign unexpectedly.

Knowing shift types prevents bugs when working with negative numbers and bit operations.

7

Expert

Optimizing Algorithms Using Bit Tricks

🤔Before reading on: do you think bit manipulation can speed up common tasks like counting or swapping? Commit to your answer.

Concept: Use bit manipulation to write faster and smaller code for common algorithmic tasks.

Examples: - Swap two numbers without a temporary variable using XOR. - Check if a number is a power of two using (n & (n-1)) === 0. - Count set bits using Brian Kernighan's algorithm. - Use masks to store multiple boolean flags in one number. These tricks reduce memory and CPU time in critical code.

Result

You can write highly efficient code using bit manipulation techniques.

Mastering bit tricks unlocks performance gains and elegant solutions in complex problems.

Under the Hood

At the hardware level, numbers are stored as sequences of bits in memory. Bitwise operations directly manipulate these bits using CPU instructions that perform AND, OR, XOR, NOT, and shifts in a single clock cycle. Shifts move bits left or right inside registers, sometimes discarding bits that fall off. Logical shifts fill empty bits with zeros, while arithmetic shifts preserve the sign bit for signed numbers. These operations are extremely fast because they work on the binary representation directly without converting to decimal.

Why designed this way?

Bit manipulation was designed to give programmers low-level control over data for efficiency and compactness. Early computers had limited memory and processing power, so manipulating bits directly saved resources. Alternatives like using arithmetic operations or arrays were slower and used more memory. The design balances speed, simplicity, and hardware capabilities, allowing both simple and complex data handling.

CPU Register (8 bits):
┌─────────────────────────┐
│ b7 b6 b5 b4 b3 b2 b1 b0 │
└─────────────────────────┘

Bitwise AND/OR/XOR/NOT:
Input A: 01011010
Input B: 00110101
Result : 00010000 (AND example)

Shift Left (<< 1):
Before: 01011010
After : 10110100

Shift Right (>> 1):
Before: 01011010
After : 00101101

Myth Busters - 4 Common Misconceptions

Quick: Does the NOT operator (~) just change 1 to 0 and 0 to 1 for the visible bits only? Commit yes or no.

Common Belief: NOT operator flips only the bits we see in the number's binary form.

Reality: NOT flips all bits in the fixed-size binary representation (e.g., 32 bits), including leading zeros, which can change the number drastically.

Why it matters: Misunderstanding this causes bugs when using NOT, especially in signed numbers, leading to unexpected negative values.

Quick: Does right shifting a negative number always add zeros on the left? Commit yes or no.

Common Belief: Right shift always fills with zeros regardless of the number's sign.

Reality: Arithmetic right shift fills with the sign bit to preserve the number's sign, while logical right shift fills with zeros. The behavior depends on the operator used.

Why it matters: Using the wrong shift can change negative numbers to positive or vice versa, causing logic errors.

Quick: Can you use bitwise operators on decimal numbers directly without converting? Commit yes or no.

Common Belief: Bitwise operators work on decimal numbers as they are.

Reality: Bitwise operators work on the binary form of numbers, so decimal numbers are internally converted to binary before operations.

Why it matters: Not knowing this can confuse learners about how bitwise operations affect numbers and why results may seem unexpected.

Quick: Is shifting bits left always the same as multiplying by two? Commit yes or no.

Common Belief: Left shift always multiplies the number by two.

Reality: Left shift usually multiplies by two, but if bits are shifted out (overflow), the result can be incorrect or wrap around.

Why it matters: Assuming left shift always multiplies can cause bugs when numbers exceed the bit size limit.

Expert Zone

1

Bitwise operations can be combined with masks to pack multiple boolean flags into a single integer, saving memory and improving cache performance.

2

Using unsigned integers for bit shifts avoids sign extension issues, making logical shifts predictable and safer in some languages.

3

Some CPUs have specialized instructions for bit counting and manipulation, which compilers can optimize to, but understanding the bit tricks helps write portable and efficient code.

When NOT to use

Bit manipulation is not suitable when code readability and maintainability are more important than performance, or when working with complex data types like floating-point numbers. In such cases, use higher-level abstractions or libraries. Also, avoid bit tricks when dealing with very large numbers or arbitrary precision arithmetic where bit operations are not directly supported.

Production Patterns

In real-world systems, bit manipulation is used in graphics programming for color channels, network protocols for flags and headers, embedded systems for hardware control, and cryptography for fast encryption. Professionals use bit masks for permissions, feature toggles, and compact data storage. Bit tricks also appear in competitive programming and system-level code for performance.

Connections

Boolean Algebra

Bitwise operations are the digital form of Boolean algebra applied to bits.

Understanding Boolean algebra helps grasp how bitwise AND, OR, and XOR combine truth values, which is the foundation of digital logic circuits.

Digital Circuit Design

Bit manipulation operations correspond directly to logic gates in hardware circuits.

Knowing how bits are manipulated in software helps understand how CPUs and memory hardware process data at the electrical level.

Genetics and DNA Sequencing

Bit manipulation techniques are used to efficiently store and analyze genetic data encoded in bits.

Recognizing that bit patterns can represent complex biological information shows how computer science methods apply beyond traditional computing.

Common Pitfalls

#1 Confusing logical and arithmetic right shifts on signed numbers.

Wrong approach:

const result = -8 >> 2; // expects zero fill but gets sign fill

Correct approach:

const result = -8 >>> 2; // uses logical shift with zero fill

Root cause:

Misunderstanding that >> preserves sign bit while >>> fills with zeros.

#2 Using NOT operator without considering fixed bit size.

Wrong approach:

const result = ~5; // expects 2 but gets -6 due to two's complement

Correct approach:

const result = ~5 & 0xFF; // masks to 8 bits, result is 250

Root cause:

Ignoring that ~ flips all bits in the full integer size, causing negative values.

#3 Assuming left shift always multiplies correctly.

Wrong approach:

const result = 1 << 31; // expects 2147483648 but may overflow in 32-bit int

Correct approach:

Use safe checks or BigInt for large shifts: const result = BigInt(1) << 31n;

Root cause:

Not accounting for integer overflow and bit size limits.

Key Takeaways

Bit manipulation works by changing tiny on/off switches inside numbers to control data efficiently.

Basic operators AND, OR, XOR, and NOT let you combine or flip bits to create new patterns.

Shifting bits left or right moves them and can multiply or divide numbers by powers of two, but watch out for sign and overflow issues.

Bit masks help select, set, or flip specific bits, enabling precise control over data flags and permissions.

Mastering bit tricks leads to faster, smaller, and more efficient code used in many real-world applications from hardware control to cryptography.

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