In software development, understanding the fundamentals allows you to navigate the depths of this career. Bitwise operations can unlock powerful techniques for optimizing code and solving complex problems. Recently I was solving a simple problem, where I needed to use the XOR (exclusive OR) operator, and I found it particularly fascinating. Let me introduce you into how the XOR operator works and see it in action with a practical example: finding the single non-duplicate element in an array.
What is XOR?
The XOR operator, denoted by ^
in Go, compares bits of two integers. For each bit position, the result is 1
if the bits are different and 0
if they are the same. Here’s the truth table for XOR:
A | B | A ^ B |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
This property makes XOR a powerful tool for various tasks, including swapping variables, checking equality, and more.
Solving the Single Non-Duplicate Problem
Imagine you have an array where every element appears twice except for one. Our task is to find this single non-duplicate element efficiently. Traditional methods might involve extra space or complex loops, but XOR simplifies this task significantly.
Here’s how you can do it in Go:
func singleNonDuplicate(list []int) int {
result := 0
for _, element := range list {
result ^= element
}
return result
}
What happened?
It started with result
set to 0
. Then for each number in the array, XOR it with result
.
Properties of XOR:
-
x ^ x = 0
: XORing a number with itself results in0
. -
x ^ 0 = x
: XORing a number with0
leaves it unchanged. -
x ^ z = ?
: XORing a number with other number different than zero?? Let's operate:
To do this, we need to represent each number in bits.
0 0 0 0 0 1 0 0 = 4
0 0 0 0 0 0 0 1 = 1
_________________
0 0 0 0 0 1 0 1 = 5
After XORing each bit of each number, we got a result. Now, let's apply this in a list of numbers to find the unique value.
Example
Consider the array [4, 1, 2, 1, 2]
. Let’s trace the XOR operations step by step:
- Start with
result = 0
. result = 0 ^ 4 = 4
result = 4 ^ 1 = 5
result = 5 ^ 2 = 7
result = 7 ^ 1 = 6
result = 6 ^ 2 = 4
After processing all numbers, result
contains the single non-duplicate element. This is because all pairs cancel each other out. The final result
is 4
, which is the single non-duplicate element.
Why Use XOR?
Efficiency: XOR operations are fast and require constant time, O(n).
Simplicity: No need for extra space or complicated logic.
Elegant Solution: The XOR property provides a clean and straightforward solution.
Conclusion
The XOR operator is a powerful tool in a programmer’s toolkit, especially for problems involving bit manipulation. By exploiting its properties, you can write concise and efficient code, as demonstrated with the single non-duplicate problem. Give it a try in your next project and see how XOR can simplify your algorithms.