Binary Search over Int/Long using bit hacks

Revision en1, by wrick, 2016-07-07 16:39:43

If you are binary searching over Ints (or Longs), there is a neat trick you can use to quickly find the answer in exactly 32 (or 64 for Longs) operations. This code is simple to write, less error prone than binary search (off by 1 mistakes) and in practice often faster.

import java.util.OptionalLong;
import java.util.function.LongPredicate;
import java.util.stream.LongStream;

/**
 * Find the largest long that satisfies the predicate f using exactly 64 bit-wise operations: O(64 * O(f))
 *
 * @param f Monotonous predicate
 * @return The largest number that satisfies f
 */
static OptionalLong binarySearch(LongPredicate f) {
    long p = 0L, n = Long.MIN_VALUE;
    for(long t = n >>> 1; t > 0; t >>= 1) {
      if (f.test(p|t)) p |= t;
      if (f.test(n|t)) n |= t;
    }
    return LongStream.of(p, n).filter(f).findFirst();
}

If you only want to search over non-negative numbers, its even simpler:

static OptionalLong binarySearch(LongPredicate f) {
    long p = 0L;
    for(long t = Long.MIN_VALUE >>> 1; t > 0; t >>= 1) {
      if (f.test(p|t)) p |= t;
    }
    return f.test(p) ? OptionalLong.of(p) : OptionalLong.empty();
}

How does it work: There are only 64-bits in a long. Just toggle them one by one from left to right depending on whether the predicate is satisfied or not.

Exercise for reader: Modify above code to search for smallest instead of largest.

Tags bit manipulation, binary seach, java 8, java

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English wrick 2016-07-08 00:12:36 47
en3 English wrick 2016-07-07 16:43:55 7
en2 English wrick 2016-07-07 16:43:07 85
en1 English wrick 2016-07-07 16:39:43 1487 Initial revision (published)