Algorithms

Bitwise Algorithm 4: Find Odd Singleton

0

Problem

Given an array of integers, in which all values occur an even number of times except for one which occurs an odd number of times. Find the integer that occurs an odd number of times.

For example, given this array: 4, 5, 7, 3, 4, 4, 4, 7, 3, 5, 7. The number 7 occurs an odd number of times while every other number occurs an even number of times, so the solution is 7.

Algorithm

My first thought when hearing this problem was to create an dictionary/hashmap to keep track of the count of each number and then just find the one with an odd count and return the corresponding number. This is a perfectly good solution that runs in O(n) time and also requires O(n) space (where n is the size of the array). O(n) is definitely the best we can do with time, because it would be impossible to solve the problem without looking at every number in the array, but we can do better with space using some bitwise operations!

Recall the bitwise XOR operator from boolean algebra. If you bitwise XOR a number with itself, you get 0. If you bitwise XOR a number with 0, you get the original number. If we XOR all the numbers in the array together, we are left with just the bits from the value that appears an odd number of times (since it didn't have a pair to cancel out with).

In our example:
4 XOR 5 = 1
1 XOR 7 = 6
6 XOR 3 = 5
5 XOR 4 = 1
1 XOR 4 = 5
5 XOR 4 = 1
1 XOR 7 = 6
6 XOR 3 = 5
5 XOR 5 = 0
0 XOR 7 = 7

As expected, the number we are left with is 7.

Here is the code in java:

public static int findOddSingleton(int[] nums) {
    int n = nums[0];
    for (int i = 1; i < nums.length; i++)
        n = n ^ nums[i];
    }
    return n;
}

Bitwise Algorithm 3: Count Bits

0

Problem

Count the number of 1s in the bit representation of the given integer.

For example, given the number 6, the bit representation is 0110, which contains two 1s, so the answer is 2.

Algorithm

In the previous tutorial we learned how to clear the lowest bit of a number. We can use that algorithm to solve this problem. All we need to do is count how many times we need to clear the lowest bit of a number, until we are left with the number 0.

Here is the code in java:

public static int countBits(int n, int k) {
    int count = 0;
    while(0 != n) {
        n = clearLowestBit(n);
        count++;
    }
    return count;
}

Bitwise Algorithm 2: Clear Lowest Bit

0

Problem

Clear the rightmost set bit in the given integer.

For example, given the number 5, the bit pattern is 0101. Clearing the right most set bit we get 0100, which is 4. Given the number 8, the bit pattern is 1000, clearing the right most set bit we get 0.

Algorithm

The algorithm is simple. The difference in bit pattern between two consecutive binary numbers (n and n-1) is such that the rightmost set bit in the greater number is not set in the lesser number. However, all bits to the left of the rightmost set bit in the greater number are the same in both numbers. Therefore, if we bitwise AND the two consequence numbers together, we get the number in which the rightmost set bit from the greater number is unset, but all the other bits are kept the same.

Here is the code in java:

public static int clearLowestBit(int x) {
    return x &amp; (x-1);
}

Bitwise Algorithm 1: Clear Bit

0

Problem

Given an integer x, clear the kth bit from the right (the rightmost bit is the 0th bit).

For example, let's say x = 000100101110. Here the 1st, 2nd, 3rd, 5th, and 8th bit are set. So for k=1, the algorithm should return 00100101100, but for k=0, since the 0th bit is already clear, it should return the original value unchanged.

Algorithm

To solve this problem we need to do some bit masking. We want to mask one bit to 0, while leaving the other bits unchanged. To mask a bit to 0, we use a bitwise AND. We need to bitwise AND the integer x with a number containing bits all set to 1, except in the kth location set to 0. In boolean algebra a \& 1 = a whereas a \& 0 = 0, so we leave all the bits unchanged except in the kth location we clear it.

For example if x = 00100101110 and k=1, we want to do the operation 000100101110 \& 111111111101, which gives us our answer, 000100101100.

The question then is how do we compute the number 111111111101 where all bits are set except the kth bit. To do this, we can take the number 1 shift it to the left by k positions and negate the result.

Here is the code in java:

public static int clearBit(int x, int k) {
    return x &amp; ~(1 &lt;&lt; k);
}

Interesting Programming Puzzle

0

How many ways can you write a function such that f(1) = 2 and f(2) = 1. It doesn't matter what the function returns for other values. Here are the functions I came up with in c.

Using control flow:

int f1(int i) {
	if (i == 1) return 2;
	return 1;
}

Using bitwise xor:

int f2(int i) {
	return i^3;
}

Using subtraction:

int f3(int i) {
	return 3-i;
}

Using modulus:

int f4(int i) {
	return i%2 + 1;
}

Using an array:

int f5(int i) {
	static const int arr[] = {0, 2, 1};
	return arr[i];
}

Using logical not:

int f6(int i) {
	return !(i-1) + 1;
}

Can anyone think of more solutions?

Go to Top