# Bits, Code and Some Java

## January 25, 2017 Recently, while playing around with exercises on HackerRank, I came across a neat thing you can do with numbers by using bit manipulation. Because clickbait sucks, let me explain what I came across before briefly diving into the basics and moving on to code. That way I’ll save you time if you already know everything I’m about to say.

You have an array of integers, all but one are pairs of identical numbers. Find the one that doesn’t have a pair. Use bitwise operations. If you know how to do it - awesome, I didn’t. I don’t use bit stuff in my everyday code, for me - they’re never a go-to consideration for solving a problem, which is a bummer and something I should fix. If, however, you don’t know how to do it - a quick refresher on bitwise operations first.

## Bitwise AND

``````	    0110
AND 0010
0010
``````
``````	    1010
AND 1010
1010
``````

## Bitwise OR

``````	    0110
OR  0010
0110
``````
``````	    1010
OR  1010
1010
``````

## Bitwise XOR

``````	    0110
XOR 0010
0100
``````
``````	    1010
XOR 1010
0000
``````

## Bitwise NOT

``````	NOT 0110
1001
``````
``````	NOT 1010
0101
``````

## Code

Right, let’s repeat the problem.

Suppose you have an array of integers. All but one integer appear in the array in pairs, like so [1, 2, 3, 3, 5, 2, 1]. You want to look through the array and return the only number that is not paired up.

There is a whole bunch of approaches you can take. For example.

## Brute Force

Let’s have a dirty, inefficient solution first.

``````	public int findSingle(int[] integers) {
int single = -666;

for (int i = 0; i < integers.length; i++) {
single = integers[i];

for (int j = 0; j < integers.length; j++) {
if (i != j && single == integers[j]) {
single = -666;
}
}

if (single != -666) {
break;
}
}

return single;
}
``````

Here we compare every integer in the array to every other integer in the array, if they’re at different positions in the array and are equal - set the value of single to something invalid (-666). If after comparing an ith value to every jth value single is not -666 - we have found our single value. Obviously, this solution isn’t great, we can’t have a -666 in the array and the performance is O(N^2). Let’s do better.

## The HashMap Approach

Because HashMaps are cool, let’s look at a solution with one.

``````	public int findSingle(int[] integers) {
HashMap<Integer, Integer> couples = new HashMap<Integer, Integer>();

for (int key : integers) {
if (!couples.containsKey(key)) {
couples.put(key, 1);
} else {
couples.put(key, couples.get(key) + 1);
}
}

for (int key : couples.keySet()) {
if (couples.get(key) == 1) {
return key;
}
}

return -1;
}
``````

So, first we iterate through the array and count the number of occurrences of each number and increment relevant counters in the HashMap. Then, once we’re done processing - we go through all the keys in the HashMap, looking for the one that has the value set to 1 and return that key. This solution can be easily extended to accommodate for cases with more than one non-paired element, so that’s cool. It has an O(N) performance and O(N) space complexity, since we’re storing stuff in the HashMap. How about we don’t?

## The Bit Manipulation Approach

A neat little approach would be to use the bitwise xor. Like this:

``````	public int findSingle(int[] integers) {
int xorVal = 0;

for (int value : integers) {
xorVal ^= value;
}

return xorVal;
}
``````

The way this works is - all integers get xored together. As we’ve seen way above - xoring two numbers of the same value returns zero. 5^5 = 0. So if the array only contains one integer that doesn’t have a pair - the final value of xorVal will always be that single value, since the rest will be xored into oblivion. Also, O(N) performance, O(1) space complexity. Sweet.