Why Bit Manipulation Basics AND OR XOR NOT Left Right Shift in DSA Java?

The Big Idea

Discover how tiny switches inside your computer can be flipped instantly to solve big problems fast!

The Scenario

Imagine you have a huge stack of papers, and you need to quickly find out which papers have a certain mark, combine marks from two stacks, or flip marks on papers. Doing this by checking each paper one by one is slow and tiring.

The Problem

Manually checking or changing each paper's mark takes a lot of time and is easy to mess up. It's like counting hundreds of tiny details by hand, which is slow and full of mistakes.

The Solution

Bit manipulation lets you handle many tiny yes/no marks all at once using simple commands. It's like having a magic tool that can quickly combine, flip, or shift all marks in one go, saving time and effort.

Before vs After

✗ Before

int countMarks(int[] papers) {
  int count = 0;
  for (int paper : papers) {
    if (paper == 1) count++;
  }
  return count;
}

✓ After

int countMarks(int papers) {
  int count = 0;
  while (papers != 0) {
    count += papers & 1;
    papers >>= 1;
  }
  return count;
}

What It Enables

Bit manipulation enables lightning-fast operations on data by working directly with the smallest building blocks of information.

Real Life Example

In video games, bit manipulation helps quickly check which keys are pressed or which game features are active, making the game respond instantly.

Key Takeaways

Manual checking of bits is slow and error-prone.

Bit manipulation uses simple commands to handle many bits at once.

This makes programs faster and more efficient.

Practice

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

easy

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

B. Returns 1 if at least one bit is 1

C. Returns 1 only if both bits are 1

D. Returns 0 only if both bits are 0

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 C

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 any bit is 1

2. Which of the following is the correct syntax for left shifting an integer variable x by 3 positions in Java?

easy

A. x << 3;

B. x >> 3;

C. x <<< 3;

D. x >>> 3;

Solution

1. Step 1: Recall left shift operator syntax in Java

   Left shift operator is << and shifts bits to the left.

2. Step 2: Identify correct usage

   To shift variable x left by 3 bits, use x << 3;. Other options are right shifts or invalid.

3. Final Answer:

   x << 3; -> Option A

4. Quick Check:

   Left shift = x << number [OK]

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

Common Mistakes:

• Using >>> for left shift (it's unsigned right shift)
• Using <<< which is invalid syntax
• Confusing left and right shift operators

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

int a = 5;  // binary 0101
int b = 3;  // binary 0011
int c = a ^ b;
System.out.println(c);

medium

A. 8

B. 7

C. 2

D. 6

Solution

1. Step 1: Convert numbers to binary

   a = 5 is 0101, b = 3 is 0011 in binary.

2. Step 2: Apply XOR operation bitwise

   XOR returns 1 if bits differ, 0 if same.
   0101 XOR 0011 = 0110 (binary) which is 6 decimal.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   5 ^ 3 = 6 [OK]

Hint: XOR sets bits where inputs differ [OK]

Common Mistakes:

• Confusing XOR with OR or AND
• Calculating XOR incorrectly bitwise
• Assuming XOR adds numbers

4. Identify the error in the following Java code snippet:

int x = 8;
int y = ~x << 2;
System.out.println(y);

medium

A. No error; the code runs and prints a valid integer

B. The shift operator << must be used before the NOT operator ~

C. The bitwise NOT operator (~) cannot be used on integers

D. The variable y should be declared as long instead of int

Solution

1. Step 1: Analyze bitwise NOT and shift usage

   The NOT operator (~) flips all bits of x. Then the result is shifted left by 2 bits.

2. Step 2: Check Java syntax and types

   Both ~ and << operators work on int type. The expression is valid and prints an integer.

3. Final Answer:

   No error; the code runs and prints a valid integer -> Option A

4. Quick Check:

   ~ and << valid on int [OK]

Hint: Bitwise NOT and shifts work fine on int in Java [OK]

Common Mistakes:

• Thinking ~ cannot be used on int
• Assuming operator order is wrong
• Believing int can't hold shifted values

5. Given an integer n, which expression correctly toggles (flips) the 4th bit (counting from 0) of n using bitwise operators in Java?

hard

A. n = n | (1 << 4);

B. n = n ^ (1 << 4);

C. n = n & ~(1 << 4);

D. n = ~n << 4;

Solution

1. Step 1: Understand toggling a bit

   Toggling means flipping the bit: 0 becomes 1, 1 becomes 0.

2. Step 2: Identify correct operator for toggling

   XOR (^) with 1 at the bit position flips that bit. So n ^ (1 << 4) toggles the 4th bit.

3. Final Answer:

   n = n ^ (1 << 4); -> Option B

4. Quick Check:

   Toggling bit uses XOR with mask [OK]

Hint: Use XOR with mask to toggle bits [OK]

Common Mistakes:

• Using OR to toggle (only sets bit)
• Using AND with negation to toggle (clears bit)
• Using NOT and shift incorrectly