wrick's blog

By wrick, history, 6 years ago, In English

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 (showing with Ints instead of Longs):

static Integer binarySearch(IntPredicate f) {
    int p = 0;
    for(int t = Integer.MIN_VALUE >>> 1; t > 0; t >>= 1) {
      if (f.test(p|t)) p |= t;
    }
    return f.test(p) ? p : null;
}

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 code to search for smallest instead of largest.

 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Hi, this article got a lot of negative votes. Any feedback appreciated :)

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Change | to + and it will become 146% more readable.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I know its same either way but I prefer to use | when the intention is bit manipulation and I use + when the intention is arithmetic addition. In this case, the intention is bit manipulation and not addition.