This example illustrates how to extract the sign (the leftmost bit), exponent (the 8 following bits) and mantissa (the 23 rightmost bits) from a float in Java.

int bits = Float.floatToIntBits(-0.005f);
int sign = bits >>> 31;
int exp = (bits >>> 23 & ((1 << 8) - 1)) - ((1 << 7) - 1);
int mantissa = bits & ((1 << 23) - 1);
System.out.println(sign + " " + exp + " " + mantissa + " " +
  Float.intBitsToFloat((sign << 31) | (exp + ((1 << 7) - 1)) << 23 | mantissa));

The same approach can be used for double’s (11 bit exponent and 52 bit mantissa).

long bits = Double.doubleToLongBits(-0.005);
long sign = bits >>> 63;
long exp = (bits >>> 52 & ((1 << 11) - 1)) - ((1 << 10) - 1);
long mantissa = bits & ((1L << 52) - 1);
System.out.println(sign + " " + exp + " " + mantissa + " " +
  Double.longBitsToDouble((sign << 63) | (exp + ((1 << 10) - 1)) << 52 | mantissa));

For more information look here.

I’ve been into a couple of interviews during the last two weeks. Today I got an interesting question: “reverse a single-linked list, in place”. The solution I suggested was good, but not great - “a better solution would use non-static recursion and be only two lines long”. After some thinking on the way home, I think the answer could look like this (updated version):

public class LinkedList {

  public String s;
  public LinkedList tail;

  public LinkedList(String s) {
    this.s = s;
    this.tail = null;
  }

  public LinkedList add(String s) {
    if (this.tail == null) {
      this.tail = new LinkedList(s);
    } else {
      this.tail.add(s);
    }
    return this;
  }

  public LinkedList reverse() {
    if (this.tail == null) {
      return new LinkedList(this.s);
    } else {
      return this.tail.reverse().add(this.s);
    }
  }

  @Override
  public String toString() {
    if (this.tail != null) {
      return s + " -> " + tail;
    } else {
      return s;
    }
  }

  public static void main(String[] args) {
    System.err.println(new LinkedList("s").add("i").add("m").add("o").add("n").reverse());
  }
}

A traditional way to debug programs is to carefully place print-statements here and there. However, as the amount of printed text increases the ability to filter out and understand the important information decreases. For this reasons, I have searched on how to use ANSI color codes in Java and found a nice implementation in Jlibs. Unfortunately this library did way more than what I needed, and therefore I have stripped it down into a small class that wraps a text string to add color codes and attributes. Feel free to use it and thanks a lot to the original author :-)

Task: Given an unsorted array of integers, find the k-th smallest entry.

Solution: this can be viewed as a reduce-and-conquer problem. The key-idea is to select an element as pivot and split the array into two sub-arrays, smaller (A) and greater (B) than pivot. Then, as long the length of A is greater or equal to k, we delegate the task to this array. Otherwise, we check if the rank of the smallest entry in B is greater or equal to k in the original array (n-|B|). If so, delegate the problem to B with k’ = k-(n-|B|). Otherwise, return the pivot value.

The worst case time of this method is O(n^2), for more information see the Wikipedia article.

Finding all possible, non-empty subsets of an array is actually a really simple task. Everything you need is a counter between 1 and 2^n-1, where n is the number of entries. For each possible value of the counter check it’s bits - 1 at position i means that i’th value of the array is present in the particular subset. No recursion, only shifts and additions.

int[] numbers = { 1, 2, 3, 4 };
int n = numbers.length;
int np = 1 << n;
for (int i = 1; i < np; i++) {
	int bitv = i;
	int pos = 0;
	while (bitv > 0) {
		if ((bitv & 1) == 1) {
			System.out.print(numbers[pos] + " ");
		}
		bitv >>= 1;
		pos++;
	}
	System.out.println();
}