Блог пользователя wrick

Автор wrick, история, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.