package ch05q03_FinderOfNextSmallestPrevLargest;

import java.util.Stack;
/*
 * James TK Lo (C) 2013.  All rights reserved.  https://github.com/jamestklo
 * Personal implementation(s) in Java, for calculating the binary representation of a decimal number.
 *   
Cracking The Coding Interview 4th Edition, Question 5.3
Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.
 *
 * a solution cleaner than the book's, not yet support negative numbers
 */
public class FinderOfNextSmallestPrevLargest {
	public static int binaryToInteger(String bits) {
		int output = 0;	
		for (int i=0, j=bits.length()-1; i < bits.length(); ++i, --j) {
			if (bits.charAt(i) == '1') {
				output += 1<<j;	
			}
		}
		return output;
	}
	public static final String integerToBinary(int input) {
		int copy = input;
		Stack<String> stack = new Stack<String>();
		while (copy != 0) {
			int bit = copy & 1;
			if (bit == 1) {
				stack.add("1");
			}
			else {
				stack.add("0");
			}
			copy = copy >>> 1;
		}
		StringBuffer sb = new StringBuffer();
		while(! stack.empty()) {
			sb.append(stack.pop());
		}
		return sb.toString();
	}
	
	public static final int NUM_BITS = 32;
	public static final int POS_BITS = NUM_BITS-2;
	public static final int MOST_POSITIVE = ((1<<POS_BITS) -1) + (1<<POS_BITS);
	public static final int MOST_NEGATIVE = 0-MOST_POSITIVE;
	public static int find(int input, int bit) {
		switch (input) {
			case -1:	return -1;
			case 0:		return 0;
		}
		if (bit == 1) { 
			switch (input) {
				case MOST_NEGATIVE:	return MOST_NEGATIVE;	// previous largest of the most negative number
				case MOST_POSITIVE:	return MOST_POSITIVE;	// next smallest of the most positive number
			}
		}
		else if (bit == 0) {
			switch(input) {
				case MOST_NEGATIVE:	return 1;				// next smallest of the most negative number
				case -2:			return MOST_POSITIVE;	// next smallest of -2
				case 1:				return MOST_NEGATIVE;	// previous largest of 1
				case MOST_POSITIVE:	return -2;				// previous largest of the most positive number
			}
		}
		
		int copy  = input;
		int count = -1;
		int first = NUM_BITS;
		for (int i=0; i < NUM_BITS; ++i, copy>>=1) {
			if ((copy & 1) == bit) {
				++count;
			}
			else if (count >= 0) {
				first = i;			
				break;
			}
		}
		int mask = 1 << first;
		if (bit == 1) {
			return ( input & (~0-mask+1) ) | mask | ((1<<count)-1);	
		}
		mask <<= 1;
		int right = 1 << (first-count);
		right = right -1;
		return ( input & (~0-mask+1) ) | (right<<count);					
	}
	public static int findNextSmallest(int input) {
		return find(input, (input >= 0)?1:0);
	}
	public static String findNextSmallest(String input) {
		return integerToBinary(findNextSmallest(binaryToInteger(input)));
	}
	public static int findPrevLargest(int input) {
		return find(input, (input >= 0)?0:1);
	}
	public static String findPrevLargest(String input) {
		return integerToBinary(findPrevLargest(binaryToInteger(input)));
	}	
	public static void main(String[] args) {
		System.out.println(findNextSmallest("1011100"));
		System.out.println(findPrevLargest("1100011"));
	}
}

@@ -1227,29 +1227,32 @@
 ;%0D%0A%09%7D%0D%0A%09%0D%0A%09p
-ublic
+rotected
  static fina
@@ -1271,29 +1271,32 @@
 TS = 32;%0D%0A%09p
-ublic
+rotected
  static fina
@@ -1323,29 +1323,32 @@
 _BITS-2;%0D%0A%09p
-ublic
+rotected
  static fina
@@ -1404,29 +1404,32 @@
 S_BITS);%0D%0A%09p
-ublic
+rotected
  static fina
@@ -1466,29 +1466,32 @@
 OSITIVE;%0D%0A%09p
-ublic
+rotected
  static int 
@@ -1506,19 +1506,23 @@
  input, 
-int
+boolean
  bit) %7B%0D
@@ -1603,21 +1603,16 @@
 %09if (bit
- == 1
 ) %7B %0D%0A%09%09
@@ -1838,22 +1838,8 @@
 else
- if (bit == 0)
  %7B%0D%0A
@@ -2302,19 +2302,17 @@
 & 1) == 
-bit
+1
 ) %7B%0D%0A%09%09%09
@@ -2424,37 +2424,32 @@
 irst;%0D%0A%09%09if (bit
- == 1
 ) %7B%0D%0A%09%09%09return (
@@ -2698,33 +2698,32 @@
 urn find(input, 
-(
 input %3E= 0)?1:0)
@@ -2719,13 +2719,8 @@
  %3E= 
-0)?1:
 0);%0D
@@ -2718,37 +2718,38 @@
 t %3E= 0);%0D%0A%09%7D%0D%0A%09p
-ublic
+rivate
  static String f
@@ -2924,17 +2924,16 @@
 (input, 
-(
 input %3E=
@@ -2939,13 +2939,8 @@
 = 0)
-?0:1)
 ;%0D%0A%09
@@ -2936,37 +2936,38 @@
 t %3E= 0);%0D%0A%09%7D%0D%0A%09p
-ublic
+rivate
  static String f

refactored FinderOfNextSmallestPrevLargest.java