Bits, Code and Some Java

 

Bits, Code and Some Java

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.

Bits

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.