Bit Manipulation Basics AND OR XOR NOT Left Right Shift in DSA Javascript - 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, which are 0s and 1s. It uses simple operations like AND, OR, XOR, NOT, and shifting bits left or right to change or check these bits. These operations help computers do tasks faster and use less memory. Bit manipulation is like using switches to control lights, turning them on or off quickly.

Why it matters

Without bit manipulation, computers would have to handle numbers and data in slower, bulkier ways. This would make programs less efficient, slower, and use more memory. Bit manipulation lets us solve problems like checking flags, encrypting data, or optimizing calculations in a very fast and small way. It is the secret behind many fast algorithms and low-level programming tasks.

Where it fits

Before learning bit manipulation, you should understand basic number systems, especially binary numbers. After mastering bit manipulation, you can explore topics like data compression, cryptography, and advanced algorithms that rely on fast data processing.

Mental Model

Core Idea

Bit manipulation is about using simple rules to change or check the smallest parts of numbers, the bits, to solve problems efficiently.

Think of it like...

Imagine a row of light switches where each switch can be ON (1) or OFF (0). Bit manipulation is like flipping these switches on or off, or checking which ones are on, to control a bigger system quickly.

Number in bits:  0 1 1 0 1 0 1 1
Operations:       & (AND), | (OR), ^ (XOR), ~ (NOT), << (left shift), >> (right shift)
Example:
  01101011 (number A)
& 01010101 (number B)
= 01000001 (result)

Shifts:
  01101011 << 1 = 11010110 (shift left by 1)
  01101011 >> 2 = 00011010 (shift right by 2)

Build-Up - 6 Steps

1

Foundation

Understanding Binary Numbers

Concept: Learn how numbers are represented in binary using bits 0 and 1.

Every number in a computer is stored as a series of bits, each bit is either 0 or 1. For example, the decimal number 13 is 1101 in binary. Each bit represents a power of two, starting from the right: 1, 2, 4, 8, etc. Adding these powers where bits are 1 gives the number.

Result

Decimal 13 is binary 1101.

Understanding binary is essential because bit manipulation works directly on these bits, not on decimal numbers.

2

Foundation

Basic Bitwise Operators

Concept: Introduce AND, OR, XOR, and NOT operations on bits.

AND (&) returns 1 only if both bits are 1. OR (|) returns 1 if at least one bit is 1. XOR (^) returns 1 if bits are different. NOT (~) flips bits: 0 becomes 1, 1 becomes 0. Example: 1010 & 1100 = 1000 1010 | 1100 = 1110 1010 ^ 1100 = 0110 ~1010 = 0101 (in 4 bits)

Result

Applying AND, OR, XOR, NOT changes bits according to simple rules.

Knowing these operators lets you combine or invert bits to create new values or check conditions.

3

Intermediate

Using Left and Right 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.

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. This usually divides the number by 2 for each shift. Example: 00011010 (26 decimal) << 1 = 00110100 (52 decimal) 00011010 (26 decimal) >> 2 = 00000110 (6 decimal)

Result

Shifting left doubles the number; shifting right halves it (ignoring fractions).

Understanding shifts helps optimize multiplication and division by powers of two using fast bit operations.

4

Intermediate

Combining Operators for Tasks

🤔Before reading on: do you think XOR can be used to toggle bits on and off? Commit to your answer.

Concept: Use AND, OR, XOR, NOT, and shifts together to set, clear, or toggle bits.

To set a bit: use OR with a mask that has 1 at the bit position. To clear a bit: use AND with a mask that has 0 at the bit position. To toggle a bit: use XOR with a mask that has 1 at the bit position. Example: Set 3rd bit of 01010001 mask = 00000100 result = 01010001 | 00000100 = 01010101

Result

You can control individual bits precisely using these combined operations.

Knowing how to combine operators lets you manipulate data at the bit level for flags, permissions, or compact storage.

5

Advanced

Bit Manipulation in JavaScript

🤔Before reading on: do you think JavaScript treats bitwise operations on signed or unsigned numbers? Commit to your answer.

Concept: Understand how JavaScript handles bitwise operations and number types.

JavaScript uses 32-bit signed integers for bitwise operations, even though numbers are usually 64-bit floats. This means bits are limited to 32 bits, and the sign bit affects results. Example: -1 in 32-bit is all 1s (111...111) ~-1 = 0 (all bits flipped) Be careful with shifts: >>> is unsigned right shift, >> is signed right shift.

Result

Bitwise operations in JavaScript work on 32-bit signed integers with some quirks.

Knowing JavaScript's bitwise behavior prevents bugs and helps write correct bit manipulation code.

6

Expert

Advanced Tricks and Pitfalls

🤔Before reading on: do you think shifting bits more than 31 places in JavaScript has any effect? Commit to your answer.

Concept: Explore tricky behaviors and advanced uses of bit manipulation.

In JavaScript, shifting by more than 31 bits wraps around (shift count mod 32). XOR can swap two numbers without a temporary variable. Example swap: a = a ^ b b = a ^ b a = a ^ b Beware of sign extension in right shifts. Use unsigned right shift (>>>) to avoid sign issues. Bit masks can optimize performance-critical code.

Result

Advanced bit tricks can optimize code but require careful understanding of language specifics.

Mastering these details unlocks powerful, efficient code and avoids subtle bugs in production.

Under the Hood

Bitwise operations work by applying simple logic gates (AND, OR, XOR, NOT) directly on each bit of the binary representation of numbers. Shifts move bits left or right, filling empty spots with zeros or sign bits. Internally, the CPU executes these operations in a single or few instructions, making them extremely fast compared to arithmetic operations.

Why designed this way?

Bit manipulation was designed to give programmers direct control over data at the smallest level, enabling efficient memory use and fast computation. Early computers had limited resources, so these operations helped optimize performance. Alternatives like arithmetic operations are slower and less precise for bit-level tasks.

┌───────────────┐
│  Number (bits)│
│  0 1 1 0 1 0 1 1 │
└───────┬───────┘
        │
        ▼
┌───────────────┐
│ Bitwise AND   │
│ 0 1 0 1 0 1 0 1 │
└───────┬───────┘
        │
        ▼
┌───────────────┐
│ Result bits   │
│ 0 1 0 0 0 0 0 1 │
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does XORing a bit with 1 always set it to 1? Commit to yes or no.

Common Belief: XOR with 1 always sets a bit to 1.

Reality: XOR with 1 flips the bit: if it was 0, it becomes 1; if it was 1, it becomes 0.

Why it matters: Misunderstanding XOR leads to wrong bit toggling, causing bugs in flag handling or encryption.

Quick: Does shifting bits right always divide the number by 2? Commit to yes or no.

Common Belief: Right shifting bits always divides the number by 2 exactly.

Reality: Right shift divides by 2 only for positive integers; for negative numbers, sign bits affect the result.

Why it matters: Assuming exact division can cause errors in calculations and logic when negative numbers are involved.

Quick: Do JavaScript bitwise operations work on 64-bit numbers? Commit to yes or no.

Common Belief: JavaScript bitwise operators work on full 64-bit numbers.

Reality: JavaScript converts numbers to 32-bit signed integers before bitwise operations.

Why it matters: Ignoring this causes unexpected results when working with large numbers or bit masks beyond 32 bits.

Quick: Does NOT (~) operator just flip bits without side effects? Commit to yes or no.

Common Belief: NOT operator flips bits and leaves the number positive.

Reality: NOT flips bits and changes the sign due to two's complement representation.

Why it matters: Misunderstanding NOT leads to confusion about negative numbers and incorrect bitwise logic.

Expert Zone

1

JavaScript's bitwise operators always work on 32-bit signed integers, so large numbers lose precision during these operations.

2

Unsigned right shift (>>>) is crucial to avoid sign extension when working with bits representing unsigned data.

3

XOR swapping is a neat trick but can be less readable and sometimes slower than using a temporary variable in modern engines.

When NOT to use

Avoid bit manipulation when working with floating-point numbers or very large integers beyond 32 bits in JavaScript. Use BigInt or specialized libraries instead. Also, for complex logic, higher-level abstractions or built-in functions may be clearer and less error-prone.

Production Patterns

Bit manipulation is used in graphics programming for color masks, in cryptography for fast encryption, in network protocols for flag checking, and in performance-critical code like game engines or embedded systems where speed and memory are limited.

Connections

Boolean Algebra

Bitwise operations are the digital form of Boolean logic applied to each bit.

Understanding Boolean algebra helps grasp why AND, OR, XOR, and NOT behave as they do on bits.

Digital Electronics

Bit manipulation mirrors how logic gates work in hardware circuits.

Knowing digital electronics clarifies how computers physically perform bitwise operations.

Genetics and DNA Sequencing

Bit manipulation techniques are similar to how genetic data is encoded and analyzed using binary patterns.

Recognizing this connection shows how bit-level operations help in fields far beyond computing, like biology.

Common Pitfalls

#1 Confusing XOR with OR when toggling bits.

Wrong approach:

let result = value | mask; // tries to toggle bits but actually sets bits

Correct approach:

let result = value ^ mask; // correctly toggles bits

Root cause:

Misunderstanding that OR sets bits while XOR flips bits.

#2 Using signed right shift (>>) when unsigned shift is needed.

Wrong approach:

let shifted = value >> 2; // sign bit extended, may cause wrong results for negative numbers

Correct approach:

let shifted = value >>> 2; // zero-fill right shift avoids sign extension

Root cause:

Not knowing the difference between signed and unsigned right shifts in JavaScript.

#3 Shifting bits by more than 31 places expecting zero.

Wrong approach:

let shifted = value << 35; // actually shifts by 35 % 32 = 3 bits

Correct approach:

let shifted = value << 3; // correct shift count within 0-31

Root cause:

Not realizing JavaScript masks shift counts to 5 bits (0-31).

Key Takeaways

Bit manipulation works directly on the smallest parts of numbers, bits, using simple logical rules.

AND, OR, XOR, and NOT are the basic tools to combine or flip bits, while shifts move bits left or right to multiply or divide by powers of two.

JavaScript uses 32-bit signed integers for bitwise operations, which affects how shifts and NOT behave.

Combining bitwise operations allows precise control over data, enabling fast and memory-efficient algorithms.

Understanding language-specific details and common pitfalls is essential to avoid bugs and write effective bit manipulation code.

Practice

1. What is the result of the bitwise AND operation between 5 and 3? (5 & 3)

easy

A. 1

B. 7

C. 0

D. 8

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 & 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

2. Which of the following is the correct syntax for performing a bitwise XOR operation between variables a and b in JavaScript?

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 JavaScript

   The XOR operator is represented by the caret symbol (^).

2. Step 2: Check syntax correctness

   let result = a ^ b; uses a ^ b, which is the correct syntax for bitwise XOR.

3. Final Answer:

   let result = a ^ b; -> Option D

4. Quick Check:

   XOR operator is ^ in JavaScript [OK]

Hint: XOR uses ^ symbol in JavaScript [OK]

Common Mistakes:

• Using && which is logical AND, not bitwise
• Using | which is bitwise OR, not XOR
• Using % which is modulo, unrelated to bits

3. What will be the output of the following JavaScript code?

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

medium

A. 2

B. 4

C. 1

D. 0

Solution

1. Step 1: Understand right shift operation

   Right shift by 2 means move bits 2 places to the right, dropping the rightmost bits.

2. Step 2: Apply right shift on binary 1000

   1000 >> 2 becomes 0010, which is decimal 2.

3. Final Answer:

   2 -> Option A

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. Find the error in the following code snippet that attempts to flip all bits of a number n using bitwise NOT:

let n = 5;
let flipped = ~n;
console.log(flipped);

What is the issue?

medium

A. Missing parentheses around ~n

B. Bitwise NOT returns a negative number due to two's complement representation

C. Variable n must be a string for bitwise NOT

D. Bitwise NOT operator (~) is not supported in JavaScript

Solution

1. Step 1: Understand bitwise NOT in JavaScript

   Bitwise NOT flips all bits and returns the two's complement negative number.

2. Step 2: Explain why output is negative

   For 5 (00000101), ~5 flips bits to 11111010 which is -6 in two's complement.

3. Final Answer:

   Bitwise NOT returns a negative number due to two's complement representation -> Option B

4. Quick Check:

   ~n flips bits and returns negative number [OK]

Hint: Bitwise NOT flips bits and returns negative in JS [OK]

Common Mistakes:

• Expecting positive flipped bits as output
• Thinking ~ is unsupported operator
• Assuming input must be string for bitwise ops

5. You want to set the 3rd bit (0-indexed from right) of a number num to 1 without changing other bits. Which expression correctly does this in JavaScript?

hard

A. num = num ^ (1 << 3);

B. num = num & (1 << 3);

C. num = num | (1 << 3);

D. num = num << 3;

Solution

1. Step 1: Understand setting a bit using OR and shift

   Left shift 1 by 3 gives 00001000, which targets the 3rd bit.

2. Step 2: Use OR to set the bit without changing others

   OR with this mask sets the 3rd bit to 1, keeping others unchanged.

3. Final Answer:

   num = num | (1 << 3); -> Option C

4. Quick Check:

   Use OR with shifted 1 to set bit [OK]

Hint: Use OR with (1 << bit_position) to set bit [OK]

Common Mistakes:

• Using AND which clears bits instead of setting
• Using XOR which toggles bits and may unset
• Using left shift alone which changes number value