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

Mental Model

Bit manipulation changes numbers by working directly on their 0s and 1s. It uses simple rules to combine or flip bits quickly.

Analogy: Imagine a row of light switches (bits) that can be ON (1) or OFF (0). Bit operations are like flipping, combining, or shifting these switches to get new patterns.

Number 6 in bits: 0 1 1 0
Positions:       3 2 1 0

AND: 1 & 0 = 0
OR:  1 | 0 = 1
XOR: 1 ^ 0 = 1
NOT: ~0 = 1 (flip all bits)
Left Shift: move bits left, add 0 on right
Right Shift: move bits right, drop bits on left

Dry Run Walkthrough

Input: number1 = 6 (0110), number2 = 3 (0011)

Goal: Show how AND, OR, XOR, NOT, left shift, and right shift change these numbers at bit level

Step 1: Perform AND between 6 and 3

0110 (6) AND 0011 (3) = 0010 (2)

Why: AND keeps bits ON only if both numbers have 1 in that position

Step 2: Perform OR between 6 and 3

0110 (6) OR 0011 (3) = 0111 (7)

Why: OR turns bits ON if either number has 1 in that position

Step 3: Perform XOR between 6 and 3

0110 (6) XOR 0011 (3) = 0101 (5)

Why: XOR turns bits ON only if bits differ between numbers

Step 4: Perform NOT on 6 (4-bit view)

NOT 0110 (6) = 1001 (9 in unsigned, -7 in signed)

Why: NOT flips every bit from 0 to 1 or 1 to 0

Step 5: Left shift 6 by 1

0110 (6) << 1 = 1100 (12)

Why: Left shift moves bits left, adding 0 on right, doubling the number

Step 6: Right shift 6 by 1

0110 (6) >> 1 = 0011 (3)

Why: Right shift moves bits right, dropping the rightmost bit, halving the number

Result:

Final results:
AND: 2 (0010)
OR: 7 (0111)
XOR: 5 (0101)
NOT: 9 (1001) in 4-bit unsigned
Left Shift: 12 (1100)
Right Shift: 3 (0011)

Annotated Code

DSA Java

public class BitManipulationBasics {
    public static void main(String[] args) {
        int number1 = 6; // 0110 in binary
        int number2 = 3; // 0011 in binary

        int andResult = number1 & number2; // AND operation
        int orResult = number1 | number2;  // OR operation
        int xorResult = number1 ^ number2; // XOR operation
        int notResult = ~number1 & 0xF;    // NOT operation limited to 4 bits
        int leftShiftResult = number1 << 1; // Left shift by 1
        int rightShiftResult = number1 >> 1; // Right shift by 1

        System.out.println("AND: " + andResult);           // Expected 2
        System.out.println("OR: " + orResult);             // Expected 7
        System.out.println("XOR: " + xorResult);           // Expected 5
        System.out.println("NOT (4-bit): " + notResult);  // Expected 9
        System.out.println("Left Shift: " + leftShiftResult);  // Expected 12
        System.out.println("Right Shift: " + rightShiftResult); // Expected 3
    }
}

int andResult = number1 & number2; // AND operation

combine bits keeping 1 only where both bits are 1

int orResult = number1 | number2; // OR operation

combine bits keeping 1 where either bit is 1

int xorResult = number1 ^ number2; // XOR operation

combine bits keeping 1 where bits differ

int notResult = ~number1 & 0xF; // NOT operation limited to 4 bits

flip all bits and mask to keep only 4 bits

int leftShiftResult = number1 << 1; // Left shift by 1

move bits left by 1, add 0 on right

int rightShiftResult = number1 >> 1; // Right shift by 1

move bits right by 1, drop rightmost bit

Output

AND: 2

OR: 7

XOR: 5

NOT (4-bit): 9

Left Shift: 12

Right Shift: 3

Complexity Analysis

Time: O(1) because bit operations work on fixed-size integers directly without loops

Space: O(1) because no extra memory is needed beyond variables

vs Alternative: Compared to arithmetic operations, bit manipulation is faster and uses less CPU because it works directly on bits

Edge Cases

NOT operation on number with more than 4 bits

Masking with 0xF limits output to 4 bits to avoid confusion from extra bits

DSA Java

int notResult = ~number1 & 0xF;    // NOT operation limited to 4 bits

Right shift on negative numbers

Right shift keeps sign bit for signed numbers, which can cause unexpected results

DSA Java

int rightShiftResult = number1 >> 1; // Right shift by 1

When to Use This Pattern

When you see problems asking to flip bits, combine bits, or quickly multiply/divide by powers of two, reach for bit manipulation because it works directly on binary digits for speed and simplicity.

Common Mistakes

Mistake: Not masking the NOT operation result, causing unexpected bits beyond intended size
Fix: Apply a mask like & 0xF to keep only desired bits after NOT

Mistake: Confusing left shift with multiplication without considering overflow
Fix: Remember left shift multiplies by powers of two but can overflow if bits shift out

Summary

Bit manipulation changes numbers by working directly on their bits using AND, OR, XOR, NOT, and shifts.

Use it when you need fast, low-level control over numbers or want to perform operations like toggling bits or multiplying/dividing by two.

The key insight is that numbers are just bits, and simple rules on bits can produce powerful results quickly.

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