Unlocking the XOR Operator in Go: Finding the Single Non-Duplicate Element

Bryan Algutria — Mon, 22 Jul 2024 15:51:32 +0000

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 in 0.
x ^ 0 = x: XORing a number with 0 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.

DEV Community: Bryan Algutria

Unlocking the XOR Operator in Go: Finding the Single Non-Duplicate Element