Bitwise Operations for Array Problems

In our previous lesson, we dove deep into the mechanics of recursion by tracing function calls on the call stack. This gave you a concrete model for how recursive algorithms execute. Today, we shift from managing function calls to manipulating data at its most fundamental level: the individual bits.

This lesson introduces bitwise operators, a topic that is crucial for performance optimization and a favorite in technical interviews for testing deep computer science fundamentals. You'll learn how these operators work directly on the binary representation of numbers. The goal is to master the core operators—AND, OR, XOR, and shifts—and then apply this knowledge to solve a classic array problem with an elegant and highly efficient solution. This skill allows you to think about problems in a completely new, low-level dimension.

The Building Blocks: Bitwise Operators

At the heart of the CPU, all operations happen on bits. Java, like C and Python, provides operators that let you work at this level. Understanding them is like learning the assembly language of data manipulation.

The main bitwise operators are:

AND (&): Returns a 1 in a bit position only if both corresponding bits are 1.
OR (|): Returns a 1 if at least one of the corresponding bits is 1.
XOR (^): Returns a 1 only if the corresponding bits are different.
NOT (~): Flips all the bits of a number (0s become 1s, and 1s become 0s).
Left Shift (<<): Shifts all bits to the left by a specified number of positions.
Right Shift (>>): Shifts all bits to the right.

The following truth table summarizes the behavior of the most common logical bitwise operators.

This truth table shows the result of AND, OR, XOR, and NOT operations for every combination of two bits, X and Y. For instance, `1 XOR 0` results in `1`, while `1 AND 0` results in `0`.

L1 | Bit Manipulations | Raj (Striver) | Introduction to Bit Manipulations

To get a comprehensive introduction, we'll watch a video from Striver's "CodeBeyond" channel. The instructor clearly explains each operator with examples.

First, watch the segment covering the core logical operators: AND, OR, XOR, and NOT. Pay close attention to the truth table logic for each one. Next, watch the explanation of the shift operators: Right Shift and Left Shift. Note the connection he makes between shifting and division/multiplication by powers of two. This is a very important property.

Let's briefly summarize the key properties of the shift operators:

Left Shift (`<<`)

When you perform number << i, you are shifting the bits of number to the left by i positions. The vacant positions on the right are filled with zeros. This operation is equivalent to multiplying the number by $2^{i}$ .
For example, 5 << 2 (0101 shifted left by 2) becomes 10100, which is 20. This is the same as $5 \times 2^{2} = 5 \times 4 = 20$ .

Right Shift (`>>`)

When you perform number >> i, you are shifting the bits to the right by i positions. In Java, this is a signed right shift, meaning the new bits on the left are filled with the value of the most significant bit (the sign bit). This preserves the number's sign. For positive numbers, it's equivalent to dividing by $2^{i}$ .

Application: Finding the Single Number

Now, let's use these operators to solve a classic problem you're likely to encounter in coding interviews: LeetCode 136. Single Number.

Problem Statement: You are given a non-empty array of integers where every element appears twice, except for one. Your task is to find that single, unique element.
Constraint: Your solution must have a linear runtime complexity, O(n), and use only constant extra space, O(1).

We'll follow your preferred method of progressing from brute-force to the optimal solution.

Find the number that appears once, and the other numbers twice - Tutorial

This article from takeUforward perfectly breaks down the problem using the brute-force, better, and optimal approaches. It aligns exactly with our learning strategy.

First, read the problem description to understand the goal. Next, study the Brute Force section. Read the approach description and look at the Java code. You'll see it uses nested loops, resulting in an O(n²) time complexity. Then, move to the Better Approach. This uses hashing. Read the hashing approach and review the Java code. While it's O(n) time, it uses O(maxElement) or O(n) space, which violates the problem's space constraint. Finally, study the Optimised Approach. This is the main focus. Read the intuition and approach carefully. Then, analyze the Java code. This is the solution that meets both time and space complexity requirements.

The Power of XOR

As you saw in the optimal solution, the XOR operator (^) is the key. Let's revisit its properties:

A number XORed with itself is zero: a ^ a = 0.
A number XORed with zero is the number itself: a ^ 0 = a.
XOR is commutative and associative: a ^ b = b ^ a and (a ^ b) ^ c = a ^ (b ^ c).

How does this help? Imagine the array [4, 1, 2, 1, 2]. If we XOR all the elements together, the order doesn't matter due to the commutative and associative properties. We can group the pairs:

4 ^ (1 ^ 1) ^ (2 ^ 2)

Since 1 ^ 1 = 0 and 2 ^ 2 = 0, the expression simplifies to:

4 ^ 0 ^ 0

And since 4 ^ 0 = 4, we are left with the unique number.

This is an incredibly elegant solution that solves the problem in a single pass (O(n) time) without any extra data structures (O(1) space).

L1 | Bit Manipulations | Raj (Striver) | Introduction to Bit Manipulations

To see Striver explain this exact solution, watch this segment. Hearing it explained reinforces the logic.

Watch from the explanation of this problem. He walks through the logic of how XORing all elements cancels out the duplicates, leaving only the single number.

Other Common Bitwise Tricks in Interviews

The "single number" problem is just one example. Bit manipulation is a rich field for clever interview questions. Here are a couple more to give you a taste of what's possible:

Check if a number is Even or Odd: Instead of using the modulo operator (n % 2 == 0), you can use a bitwise AND. A number is odd if its least significant bit (LSB) is 1. Therefore, (n & 1) == 1 means n is odd, and (n & 1) == 0 means n is even. This can be marginally faster as bitwise operations are often closer to the hardware.

Swap two numbers without a temporary variable: This is a classic trick question.

int a = 5;
int b = 7;

a = a ^ b; // a becomes 5 ^ 7
b = a ^ b; // b becomes (5 ^ 7) ^ 7 = 5
a = a ^ b; // a becomes (5 ^ 7) ^ 5 = 7

After these three operations, a will be 7 and b will be 5.

L1 | Bit Manipulations | Raj (Striver) | Introduction to Bit Manipulations

Striver's video also covers these common patterns.

For the XOR swap trick, watch the segment from swapping of two numbers. For the even/odd check, watch from check if a number is odd or even.

Key Takeaways

Bitwise operators (&, |, ^, ~, <<, >>) manipulate integers at the binary level.
They are fundamental for low-level optimization and solving certain problems with high efficiency.
The XOR (^) operator is particularly powerful. Its properties (a ^ a = 0 and a ^ 0 = a) allow for elegant solutions to problems involving duplicates.
The "single number" problem demonstrates a perfect use case for XOR, yielding an O(n) time and O(1) space solution that is ideal for interview settings.
Knowing bitwise tricks like the even/odd check and XOR swap can showcase a deeper understanding of computer science principles.

Conclusion

You've now added another powerful tool to your problem-solving arsenal. By learning to think in terms of bits, you can devise solutions that are not only correct but also optimally efficient. This kind of thinking is highly valued in top tech companies.

In our next lesson, we will return to recursion. We will apply the foundational concepts of recursive thinking and call stack tracing to solve classic problems like calculating factorials and Fibonacci numbers. This will lead us to an important observation about overlapping subproblems, a key pattern that paves the way for understanding dynamic programming later in the course.

Recommended resources

The Building Blocks: Bitwise Operators

Left Shift (<<)

Right Shift (>>)

Application: Finding the Single Number

The Power of XOR

Other Common Bitwise Tricks in Interviews

Key Takeaways

Conclusion

Left Shift (`<<`)

Right Shift (`>>`)