Bit Manipulation Basics AND OR XOR NOT Left Right Shift in DSA Java - 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 bit manipulation, we can change, check, or combine these bits quickly using special operations like AND, OR, XOR, NOT, and shifting bits left or right. 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 can be slower and less efficient. Bit manipulation lets us solve problems like checking flags, compressing data, or doing math faster. It is used everywhere from video games to network communication and security. Without it, many programs would be slower and use more resources.

Where it fits

Before learning bit manipulation, you should understand basic number systems, especially binary numbers. After mastering bit manipulation, you can explore advanced topics like data compression, cryptography, and low-level programming such as device drivers or embedded systems.

Mental Model

Core Idea

Bit manipulation is about treating numbers as tiny on/off switches and using simple rules to combine or change these switches quickly.

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, or checking which ones are on, using simple rules to control many switches at once.

Number in bits:  0 1 1 0 1 0 1 1
Operations:
AND (&):       1 if both bits are 1, else 0
OR (|):        1 if at least one bit is 1
XOR (^):       1 if bits are different
NOT (~):       flips each bit
Left Shift (<<): moves bits left, adds zeros on right
Right Shift (>>): moves bits right, drops bits on left

Build-Up - 7 Steps

1

Foundation

Understanding Binary Numbers

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

Every number in a computer is stored as a series of bits (0s and 1s). For example, the number 13 in binary is 00001101 (8 bits). Each bit represents a power of two, starting from the right (2^0). Adding the powers where bits are 1 gives the number's value.

Result

You can convert any decimal number to binary and understand its bit pattern.

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

2

Foundation

Basic Bitwise Operations Explained

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 each bit (0 becomes 1, 1 becomes 0). Example: 1010 (10) & 1100 (12) = 1000 (8) These operations work bit by bit.

Result

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

Knowing these operations lets you control bits precisely, which is the foundation of bit manipulation.

3

Intermediate

Using Bit Shifts to Move Bits

🤔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 changes the number's value by moving bits.

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: 00000101 (5) << 1 = 00001010 (10) >> 1 = 00000010 (2) Shifts are fast ways to multiply or divide by powers of two.

Result

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

Understanding shifts helps optimize math operations and manipulate bit positions efficiently.

4

Intermediate

Combining Operations for Bit Masks

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

Concept: Learn how to use AND, OR, and XOR with masks to check, set, or toggle specific bits.

A bit mask is a number where some bits are 1 and others 0, used to target bits. To check a bit: AND with a mask that has 1 at the bit position. To set a bit: OR with a mask that has 1 at the bit position. To toggle a bit: XOR with a mask that has 1 at the bit position. Example: To set bit 2 (counting from 0) in 00000100 (4), OR with 00000100 (4) gives 00000100 (4). To clear a bit, use AND with the NOT of the mask.

Result

You can change or check specific bits without touching others.

Using masks with bitwise operations is a powerful way to control individual bits safely.

5

Intermediate

Java Code for Bitwise Operations

Concept: See how to write and run bitwise operations in Java with examples.

Example Java code: int a = 5; // 0101 int b = 12; // 1100 System.out.println("AND: " + (a & b)); // 4 (0100) System.out.println("OR: " + (a | b)); // 13 (1101) System.out.println("XOR: " + (a ^ b)); // 9 (1001) System.out.println("NOT a: " + (~a)); // -6 (two's complement) System.out.println("a << 1: " + (a << 1)); // 10 System.out.println("b >> 2: " + (b >> 2)); // 3

Result

Java prints the results of bitwise operations as integers.

Seeing code helps connect the theory to real programming practice.

6

Advanced

Handling Signed Numbers and Two's Complement

🤔Before reading on: do you think NOT (~) flips bits and always gives a positive number? Commit to your answer.

Concept: Understand how negative numbers are stored and how bitwise NOT affects them.

Computers use two's complement to store negative numbers. In two's complement, the highest bit is the sign bit. NOT (~) flips all bits, which changes the number's sign and value. Example: For 8-bit 5 (00000101), ~5 = 11111010, which is -6 in two's complement. This means bitwise NOT can produce negative numbers, not just inverted bits.

Result

You understand why bitwise NOT can produce negative results in Java.

Knowing two's complement prevents confusion when using NOT and interpreting results.

7

Expert

Optimizing Code with Bit Tricks

🤔Before reading on: do you think bit manipulation can replace some math operations for speed? Commit to your answer.

Concept: Learn advanced bit tricks used in real-world code to optimize performance.

Examples: - Check if a number is even: (num & 1) == 0 - Swap two numbers without temp: a ^= b; b ^= a; a ^= b; - Count set bits quickly using Brian Kernighan's algorithm. - Use shifts to multiply/divide by powers of two instead of slow math. These tricks reduce CPU cycles and memory use in critical code.

Result

You can write faster, smaller code using bit tricks.

Mastering bit tricks gives you an edge in performance-critical programming.

Under the Hood

At the hardware level, numbers are stored as sequences of bits in memory. Bitwise operations directly manipulate these bits using logic gates inside the CPU. AND, OR, XOR, and NOT correspond to simple gate operations that process bits in parallel. Shifts move bits left or right by wiring connections to shift registers. This low-level control makes bit manipulation extremely fast and efficient compared to arithmetic operations.

Why designed this way?

Bitwise operations were designed to match the physical behavior of digital circuits, which use switches and gates. This design allows direct control over hardware states and efficient data processing. Alternatives like decimal arithmetic are slower and require more complex hardware. Bit manipulation also enables compact data storage and fast algorithms, which were critical in early computing and remain important today.

┌───────────────┐
│   CPU ALU     │
│  ┌─────────┐  │
│  │ AND Gate│  │
│  └─────────┘  │
│  ┌─────────┐  │
│  │ OR Gate │  │
│  └─────────┘  │
│  ┌─────────┐  │
│  │ XOR Gate│  │
│  └─────────┘  │
│  ┌─────────┐  │
│  │ NOT Gate│  │
│  └─────────┘  │
│  ┌─────────┐  │
│  │Shift Reg│  │
│  └─────────┘  │
└─────┬─┬───────┘
      │ │
      ▼ ▼
  Bits in memory

Myth Busters - 4 Common Misconceptions

Quick: Does the NOT (~) operator always produce a positive number? Commit to yes or no.

Common Belief: NOT (~) just flips bits and always gives a positive number.

Reality: NOT (~) flips all bits, which can produce negative numbers due to two's complement representation.

Why it matters: Misunderstanding this causes confusion when interpreting results, leading to bugs in code that uses NOT.

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

Common Belief: Right shift (>>) always divides the number by two exactly.

Reality: Right shift divides by two only for positive numbers; for negative numbers, it depends on the language and may perform arithmetic shift preserving the sign.

Why it matters: Assuming exact division can cause errors in calculations with negative numbers.

Quick: Can you use OR (|) to clear bits? Commit to yes or no.

Common Belief: OR (|) can be used to clear bits (set bits to 0).

Reality: OR (|) can only set bits to 1; it cannot clear bits. To clear bits, you must use AND with NOT of the mask.

Why it matters: Using OR to clear bits will fail silently, leaving bits unchanged and causing logic errors.

Quick: Does XOR (^) with the same number always produce zero? Commit to yes or no.

Common Belief: XOR (^) with the same number always produces zero.

Reality: This is true; XORing a number with itself results in zero.

Why it matters: This property is useful for toggling bits and is a key trick in bit manipulation.

Expert Zone

1

Bitwise NOT (~) results depend on the fixed bit-width of the data type and two's complement representation, which can cause unexpected negative values.

2

Right shift (>>) behavior differs between logical and arithmetic shifts; Java uses arithmetic shift for signed types, preserving the sign bit.

3

Using XOR (^) to swap variables avoids temporary storage but can be less readable and sometimes slower on modern CPUs.

When NOT to use

Avoid bit manipulation when working with floating-point numbers or complex data structures where clarity and maintainability are more important. Use high-level arithmetic or libraries for cryptography instead of manual bit tricks unless performance is critical.

Production Patterns

Bit manipulation is used in embedded systems for hardware control, in graphics programming for color and pixel operations, in network protocols for flag checking, and in performance-critical algorithms like hashing and encryption.

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 work logically.

Digital Electronics

Bit manipulation corresponds directly to logic gates and circuits in digital electronics.

Knowing how hardware gates function clarifies why bitwise operations are so fast and fundamental.

Set Theory

Bitwise operations can represent set operations where bits correspond to elements.

This connection helps in algorithms that use bitsets to represent and manipulate sets efficiently.

Common Pitfalls

#1 Using OR (|) to clear bits instead of setting them.

Wrong approach:

int x = 13; // 1101
x = x | 2; // Trying to clear bit 1 (should clear but actually sets it)

Correct approach:

int x = 13; // 1101
x = x & ~2; // Clears bit 1 correctly

Root cause:

Confusing OR operation's ability to set bits with clearing bits, which requires AND with NOT.

#2 Assuming right shift (>>) always divides by two exactly.

Wrong approach:

int x = -4;
int y = x >> 1; // y is -2, but expecting -2 exactly as division

Correct approach:

int x = -4;
int y = x / 2; // Use division for exact result

Root cause:

Not accounting for arithmetic shift behavior on negative numbers.

#3 Misinterpreting bitwise NOT (~) results as positive numbers.

Wrong approach:

int x = 5;
int y = ~x; // Expecting positive 2 but gets -6

Correct approach:

int x = 5;
int y = ~x; // Result is -6 due to two's complement

Root cause:

Lack of understanding of two's complement representation for signed integers.

Key Takeaways

Bit manipulation treats numbers as collections of on/off switches called bits, allowing precise control.

AND, OR, XOR, and NOT are basic operations that combine or invert bits following simple rules.

Shifting bits left or right moves their positions, effectively multiplying or dividing by powers of two.

Two's complement representation affects how bitwise NOT and shifts behave with negative numbers.

Mastering bit manipulation enables writing faster, smaller, and more efficient code in many real-world applications.

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