Find the nearest numbers that have same number of 1s for an integer

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

  1. 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.
  2. 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
  3. Make the number as small as possible by rearranging all the 1s to be as far right as possible: Example: xxxxx101100 becomes xxxxx100011
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: