Runhe Tian Coding Practice

An array A[1..n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is ”fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?

My initial thoughts:
I have no idea about this problem, basically. I thought that if the array is sorted, then the least significant bits of those integers would appear as 0, 1, 0, 1, 0, 1, etc. But the second least significant bits are then presented as 0, 0, 1, 1, 0, 0, 1, 1 and these two have to be corresponding to each other. Then I’m stack there.

Solutions:

	public static int findMissing(ArrayList<Integer> array) {
		return findMissing(array, Integer.SIZE - 1);
	}

	public static int findMissing(ArrayList<Integer> input, int column) {
		if (column < 0) {
			return 0;
		}
		ArrayList<Integer> oddIndices = new ArrayList<Integer>();
		ArrayList<Integer> evenIndices = new ArrayList<Integer>();
		for (Integer t : input) {
			if ((t & (1 << column)) == 0) {
				evenIndices.add(t);
			} else {
				oddIndices.add(t);
			}
		}
		if (oddIndices.size() >= evenIndices.size()) {
			return (findMissing(evenIndices, column - 1)) << 1 | 0;
		} else {
			return (findMissing(oddIndices, column - 1)) << 1 | 1;
		}
	}

The idea is to use recursion to process bit by bit from least significant to most significant. For each bit, the point is that if one value is missing, the number of 1s and 0s in this bit will change. Change how? Before removing an integer, we can only have three cases:

Number of 1s = Number of 0s + 1.
Number of 1s = Number of 0s.
 Number of 1s = Number of 0s – 1.

Therefore, if we remove an integer with LSB 1, we will end up with #1s = #0s. Hence, by counting the number of 1s and 0s of LSB, we can eliminate half of the integers and we advance to the second least significant bit. We continue to do this recursively until we find the missing value.
	

Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc).

My initial thoughts:
I was thinking to shift the number to the left and then manipulate the bits somehow, shift the number to the right and also do the trick, then combine these two together. But I never figured out the details…

Solution:

	public static int swapOddEvenBits(int x) {
		return (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
	}

The solution’s idea is similar to mine… well, to some degree.

Mask the odd bits (keep the odd bits and turn off all the even bits). We can do this by: number & 10101010…. In a 32-bit machine, the mask is 0xAAAAAAAA. After doing that, we have all the odd bits, we shift the number to the right for one position, that puts all the odd bits to the oven position.
Mask the even bits (keep the even bits and turn off all the odd bits). We can do this by: number & 01010101…. In a 32-bit machine, the mask is 0x55555555. After doing that, we have all the even bits, we shift the number to the left for one position, that puts all the even bits to the odd position.
We then | the two results combine them together and output the final number.

We should learn the general way of swapping any two bits in position i and position j.
	public static int swapTwoPositions(int number, int i, int j) {
		return (((number & (1 << i)) >> i) << j)
				| (((number & (1 << j)) >> j) << i)
				| ((~(1 << i)) & (~(1 << j)) & number);
	}

There are three parts separated by |. The first part mask the i position and move it to j position. The second part mask the j position and move it to i position. The third part turns off bits i and j but keep the rest.
	

Write a function to determine the number of bits required to convert integer A to integer B.
Input: 31, 14
Output: 2

My initial thoughts:
31 = 11111
14 = 01110
Take 31 – 14 and we get:
17 = 10001
So we take the difference of A-B or B-A, and check how many 1s in that integer.

My initial codes:

	public static int numberOfBitsRequiredToConvert(int A, int B) {
		int diff = A - B >= 0 ? A - B : B - A;
		int count = 0;
		for (int i = 0; i < 32; ++i)
			count += (diff & (1 << i)) > 0 ? 1 : 0;
		return count;
	}

Solutions:
	public static int bitSwapRequired(int a, int b) {
		int count = 0;
		for (int c = a ^ b; c != 0; c = c >> 1) {
			count += c & 1;
		}
		return count;
	}

We can conclude two basic idea from this solution:

When trying to detect which bits of two numbers are different, we use XOR(^).
To check each bit of a number, we can keep & it with 1 and then shift to right.

	

Explain what the following code does: ((n & (n-1)) == 0).

When we have A & B == 0, it means that A and B have no common 1s, i.e. any two bits at the same positions of A and B are either different from each other, or two 0s.

Let’s look at ((n & (n-1)) == 0).

• n == 1. n – 1 == 0. 1 & 0 == 0.
• n == 2. n – 1 == 1. 10 & 01 == 0.
• n == 3. n – 1 == 2. 11 & 10 != 0.
• n == 4. n – 1 == 3. 100 & 011 == 0.
• n == 5. n – 1 == 4. 101 & 100 != 0.
• n == 6. n – 1 == 5. 110 & 101 != 0.
• n == 7. n – 1 == 6. 111 & 110 != 0.
• n == 8. n – 1 == 7. 1000 & 0111 == 0.

Looking at those n that satisfies ((n & (n-1)) == 0), we find n == 1, 2, 4, 8, i.e. power of 2.
If we think about a general case, let’s say we have a binary number abcde1xxx.
Let think about 1xxx first, after subtracting 1, they have to share not common 1: therefore n-1 must be like 0yyy, which means you must ”borrow” 1 from the most significant bits. That indicates you must have 1xxx as 1000 and 0yyy as 0111. So we have the number n in the form abcde1000.
Now let us look at abcde part. n-1 is abcde0111. To make ((n & (n-1)) == 0), we must have abcde as 0000.
To sum up, n must be in the form of 00…010…0, i.e. the power of 2.

Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.

My initial thoughts:
For the next largest, keep adding 1 to the number until find the number that has same number of 1 bits. For the next smallest, keep decreasing 1.

My initial codes:

	public static int findNextSmallest(int number) {
		int result = number - 1;
		while (Integer.bitCount(result) != Integer.bitCount(number))
			result--;
		return result;
	}

	public static int findNextLargest(int number) {
		int result = number + 1;
		while (Integer.bitCount(result) != Integer.bitCount(number))
			result++;
		return result;
	}

Comments after running:

Definitely gonna work but terribly boring. We know this is not what the interviewer expects.
Solutions:
	public static boolean GetBit(int n, int index) {
		return ((n & (1 << index)) > 0);
	}

	public static int SetBit(int n, int index, boolean b) {
		if (b) {
			return n | (1 << index);
		} else {
			int mask = ~(1 << index);
			return n & mask;
		}
	}

	public static int GetNext_NP(int n) {
		if (n <= 0)
			return -1;
		int index = 0;
		int countOnes = 0;
		
		// Find first one.
		while (!GetBit(n, index))
			index++;
		
		// Turn on next zero.
		while (GetBit(n, index)) {
			index++;
			countOnes++;
		}
		n = SetBit(n, index, true);

		// Turn off previous one
		index--;
		n = SetBit(n, index, false);
		countOnes--;

		// Set zeros
		for (int i = index - 1; i >= countOnes; i--) {
			n = SetBit(n, i, false);
		}

		// Set ones
		for (int i = countOnes - 1; i >= 0; i--) {
			n = SetBit(n, i, true);
		}
		
		return n;
	}

	public static int GetPrevious_NP(int n) {
		if (n <= 0)
			return -1; // Error

		int index = 0;
		int countZeros = 0;

		// Find first zero.
		while (GetBit(n, index))
			index++;

		// Turn off next 1.
		while (!GetBit(n, index)) {
			index++;
			countZeros++;
		}
		n = SetBit(n, index, false);

		// Turn on previous zero
		index--;
		n = SetBit(n, index, true);
		countZeros--;

		// Set ones
		for (int i = index - 1; i >= countZeros; i--) {
			n = SetBit(n, i, true);
		}

		// Set zeros
		for (int i = countZeros - 1; i >= 0; i--) {
			n = SetBit(n, i, false);
		}

		return n;
	}

Solution’s idea

Traverse from right to left. Once we’ve passed a 1, turn on the next 0. We’ve now increased the number by 2^i. Yikes! Example: xxxxx011100 becomes xxxxx111100.
Turn off the one that’s just to the right side of that. We’re now bigger by 2^i – 2^(i-1). Example: xxxxx111100 becomes xxxxx101100
Make the number as small as possible by rearranging all the 1s to be as far right as possible: Example: xxxxx101100 becomes xxxxx100011

	

Given a (decimal – e.g. 3.72) number that is passed in as a string, print the binary representation. If the number can not be represented accurately in binary, print “ERROR”.

My initial thoughts:
I thought this question ask me to implement toBinaryString() method built in Java API. So I was thinking about the IEEE-754 standard. In a 32-bit machine, the 1st bit is for sign, 2nd – 9th digits are for exponent and the rest are for mantissa. Then you need to float the decimal point first and then determine the mantissa, etc. Way more complicated than I can handle…
Turns out the question asks for something like this:
INPUT: 3.25
OUTPUT 11.01
i.e., we treat the integer and decimal parts separately.

My initial codes:

	public static String toBinary(String n) {
		int intPart = Integer.parseInt(n.substring(0, n.indexOf('.')));
		double decPart = Double.parseDouble(n.substring(n.indexOf('.'),
				n.length()));
		String int_string = "";
		while (intPart != 0) {
			int digit = intPart % 2;
			intPart = intPart >> 1; // divide by 2
			int_string += digit;
		}

		String dec_string = new String();
		Set<Double> seen = new HashSet<Double>();
		seen.add(decPart);
		while (decPart != 0.0) {
			System.out.println("decPart = " + decPart);
			int digit = decPart * 2 >= 1 ? 1 : 0;
			decPart = decPart * 2 >= 1 ? decPart * 2 - 1 : decPart * 2;
			if (seen.contains(decPart)) {
				return "ERROR";
			} else {
				seen.add(decPart);
			}
			dec_string += digit;
		}

		return int_string + "." + dec_string;
	}

Comments after running:

It tries to represent decimals that cannot be represented in finite binary bits by keeping adding digits, only to find that it hits the bottom line of the machine precision and then round off.

INPUT: 3.126

EXPECTED OUTPUT: ERROR

OUTPUT: 11.00100000010000011000100100110111010010111100011010101
Solution:
	public static String printBinary(String n) {
		int intPart = Integer.parseInt(n.substring(0, n.indexOf('.')));
		double decPart = Double.parseDouble(n.substring(n.indexOf('.'),
				n.length()));
		String int_string = "";
		while (intPart > 0) {
			int r = intPart % 2;
			intPart >>= 1;
			int_string = r + int_string;
		}
		StringBuffer dec_string = new StringBuffer();
		while (decPart > 0) {
			if (dec_string.length() > 32)
				return "ERROR";
			if (decPart == 1) {
				dec_string.append((int) decPart);
				break;
			}
			double r = decPart * 2;
			if (r >= 1) {
				dec_string.append(1);
				decPart = r - 1;
			} else {
				dec_string.append(0);
				decPart = r;
			}
		}
		return int_string + "." + dec_string.toString();
	}

The solution controls the limit of the representation by saying that if after 32 bits the number still cannot be fully represented (hits 1 after some times of multiplications), then it will reprot error.
	

You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (e.g., M becomes a substring of N located at i and starting at j).
EXAMPLE:
Input: N = 10000000000, M = 10101, i = 2, j = 6
Output: N = 10001010100

My initial thoughts:

1. Create a mask with 1s but only 0s between positions i and j. AND the mask with N to clear the bits between i and j to 0s.
2. Create another mask with 0s but only 1s between positions i and j. AND the mask with M to clear the bits outside i and j to 0s.
3. OR N and M.

My initial codes:

	public static void setBits(int N, int M, int i, int j) {
		int mask = 1;
		for (int digit = i; digit <= j; ++digit)
			mask |= (mask << digit);
		N &= ~mask;
		M &= mask;
		N = N | M;
	}

Comments after running:

It does not work…
Solution:
	public static int updateBits(int n, int m, int i, int j) {
		int max = ~0; /* All 1's */

		// 1's through position j, then 0's
		int left = max - ((1 << j) - 1);

		// 1's after position i
		int right = ((1 << i) - 1);

		// 1's with 0s between i and j
		int mask = left | right;

		// Clear i through j, then put m in there
		return (n & mask) | (m << i);
	}

The idea is the same as mine but my implementation is wrong…