Bit Manipulation Basics AND OR XOR NOT Left Right Shift in DSA Java - Execution Trace

Concept Flow - Bit Manipulation Basics AND OR XOR NOT Left Right Shift

Start with two numbers

↓

Apply AND (&)

→Result: bits 1 only if both bits 1

↓

Apply OR (|)

→Result: bits 1 if any bit 1

↓

Apply XOR (^)

→Result: bits 1 if bits differ

↓

Apply NOT (~)

→Result: bits flipped

↓

Apply Left Shift (<<)

→Bits shifted left, zeros fill right

↓

Apply Right Shift (>>)

→Bits shifted right, sign bit fills left

↓

Apply Unsigned Right Shift (>>>)

→Bits shifted right, zeros fill left

↓

End with new number results

Start with two numbers, apply each bit operation step-by-step, producing new bit patterns and results.

Execution Sample

DSA Java

int a = 6;  // 0110 in binary
int b = 11; // 1011 in binary
int c = a & b;
int d = a | b;
int e = a ^ b;
int f = ~a;
int g = a << 1;
int h = b >> 2;
int i = b >>> 2;

This code applies AND, OR, XOR, NOT, left shift, right shift, and unsigned right shift on two numbers and stores results.

Execution Table

Step	Operation	Input Values (binary)	Operation Detail	Result (binary)	Result (decimal)
1	AND (&)	a=0110, b=1011	Bitwise AND: 1 only if both bits 1	0010	2
2	OR (|)	a=0110, b=1011	Bitwise OR: 1 if any bit 1	1111	15
3	XOR (^)	a=0110, b=1011	Bitwise XOR: 1 if bits differ	1101	13
4	NOT (~)	a=0000...0110	Bitwise NOT: flip all bits (32-bit)	1111...1001	-7
5	Left Shift (<<)	a=0000...0110	Shift bits left by 1, fill 0 right	0000...1100	12
6	Right Shift (>>)	b=0000...1011	Shift bits right by 2, fill sign bit left	0000...0010	2
7	Unsigned Right Shift (>>>)	b=0000...1011	Shift bits right by 2, fill 0 left	0000...0010	2
8	End	-	-	-	-

💡 All bitwise operations completed on inputs a=6 and b=11.

Variable Tracker

Variable	Initial (decimal)	Initial (binary)	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7
a	6	00000000000000000000000000000110	6	6	6	6	6	6	6
b	11	00000000000000000000000000001011	11	11	11	11	11	11	11
c = a & b	-	-	2 (00000000000000000000000000000010)	-	-	-	-	-	-
d = a | b	-	-	-	15 (00000000000000000000000000001111)	-	-	-	-	-
e = a ^ b	-	-	-	-	13 (00000000000000000000000000001101)	-	-	-	-
f = ~a	-	-	-	-	-	-7 (11111111111111111111111111111001)	-	-	-
g = a << 1	-	-	-	-	-	-	12 (00000000000000000000000000001100)	-	-
h = b >> 2	-	-	-	-	-	-	2 (00000000000000000000000000000010)	-	-
i = b >>> 2	-	-	-	-	-	-	-	-	2 (00000000000000000000000000000010)

Key Moments - 3 Insights

Why does ~a (NOT) produce a negative number?

Because NOT flips all bits including the sign bit in 32-bit signed integers, making the number negative as shown in step 4 of execution_table.

Why does right shift (>>) fill with sign bit but unsigned right shift (>>>) fills with zero?

Right shift (>>) keeps the sign bit to preserve positive/negative sign (step 6), while unsigned right shift (>>>) always fills with zero (step 7), changing sign if number was negative.

What happens to bits shifted out in left or right shifts?

Bits shifted out are discarded and lost; new bits on the opposite side are filled with zeros (left shift) or sign/zero bits (right shifts), as shown in steps 5, 6, and 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the decimal result of a ^ b?

A 15

B 2

C 13

D 7

💡 Hint

Check the 'Result (decimal)' column at step 3 in execution_table.

At which step does the NOT (~) operation occur and what is the decimal result?

A Step 4, result -7

B Step 5, result 12

C Step 6, result 2

D Step 3, result 13

💡 Hint

Look for the NOT operation row in execution_table and check the decimal result.

If we change a from 6 to 3, what would be the result of a & b at step 1?

A 1

B 3

C 2

D 0

💡 Hint

Perform bitwise AND of 3 (0011) and 11 (1011) as in step 1 of execution_table.

Concept Snapshot

Bit Manipulation Basics:
- AND (&): 1 if both bits 1
- OR (|): 1 if any bit 1
- XOR (^): 1 if bits differ
- NOT (~): flips all bits (signed 32-bit)
- Left Shift (<<): shift bits left, fill 0 right
- Right Shift (>>): shift bits right, fill sign bit left
- Unsigned Right Shift (>>>): shift right, fill 0 left

Full Transcript

This lesson shows how to use basic bit manipulation operations in Java. We start with two numbers, 6 and 11, and apply AND, OR, XOR, NOT, left shift, and right shift operations. Each operation changes the bits in a specific way. AND keeps bits set only if both inputs have 1. OR sets bits if any input has 1. XOR sets bits if inputs differ. NOT flips all bits, which can produce negative numbers due to signed representation. Left shift moves bits left, adding zeros on the right. Right shift moves bits right, filling with the sign bit to keep positive or negative sign. Unsigned right shift fills with zeros on the left. The execution table shows each step with binary and decimal results. Variable tracker shows how values change. Key moments clarify common confusions about negative results and bit filling. Visual quizzes test understanding of results and bit operations. This helps beginners see how bits change step-by-step in these common operations.

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