Integer in an interval with maximized number of trailing zero bits

Sought is an efficient algorithm that finds the unique integer in an interval [a, b] which has the maximum number of trailing zeros in its binary representation (a and b are integers > 0):

def bruteForce(a: Int, b: Int): Int =
  (a to b).maxBy(Integer.numberOfTrailingZeros(_))

def binSplit(a: Int, b: Int): Int = {
  require(a > 0 &开发者_如何学JAVA& a <= b)
  val res = ???
  assert(res == bruteForce(a, b))
  res
}

here are some examples

bruteForce(  5,   7) ==   6 // binary 110 (1 trailing zero)
bruteForce(  1, 255) == 128 // binary 10000000
bruteForce(129, 255) == 192 // binary 11000000

etc.

This one finds the number of zeros:

// Requires a>0
def mtz(a: Int, b: Int, mask: Int = 0xFFFFFFFE, n: Int = 0): Int = {
  if (a > (b & mask)) n
  else mtz(a, b, mask<<1, n+1)
}

This one returns the number with those zeros:

// Requires a > 0
def nmtz(a: Int, b: Int, mask: Int = 0xFFFFFFFE): Int = {
  if (a > (b & mask)) b & (mask>>1)
  else nmtz(a, b, mask<<1)
}

I doubt the log(log(n)) solution has a small enough constant term to beat this. (But you could do binary search on the number of zeros to get log(log(n)).)

I decided to take Rex's challenge and produce something faster. :-)

// requires a > 0
def mtz2(a: Int, b: Int, mask: Int = 0xffff0000, shift: Int = 8, n: Int = 16): Int = {
  if (shift == 0) if (a > (b & mask)) n - 1 else n
  else if (a > (b & mask)) mtz2(a, b, mask >> shift, shift / 2, n - shift)
  else mtz2(a, b, mask << shift, shift / 2, n + shift)
}

Benchmarked with

import System.{currentTimeMillis => now}
def time[T](f: => T): T = {
  val start = now
  try { f } finally { println("Elapsed: " + (now - start)/1000.0 + " s") }
}

val range = 1 to 200
time(f((a, b) => mtz(a, b)))
time(f((a, b) => mtz2(a, b)))

First see if there is a power of two that lies within your interval. If there is at least one, the largest one wins.

Otherwise, choose the largest power of two that is less than your minimum bound.

Does 1100000...0 lie in your bound? If yes, you've won. If it's still less than your minimum bound, try 1110000...0; otherwise, if it's greater than your maximum bound, try 1010000...0.

And so forth, until you win.

as a conclusion, here is my variant of Rex' answer which gives both the center value and also an 'extent' which is the minimum power of two distance from the center which covers both a in the one direction and b in the other.

@tailrec def binSplit(a: Int, b: Int, mask: Int = 0xFFFFFFFF): (Int, Int) = {
  val mask2 = mask << 1
  if (a > (b & mask2)) (b & mask, -mask)
  else binSplit(a, b, mask2)
}

def test(): Unit = {
  val Seq(r1, r2) = Seq.fill(2)(util.Random.nextInt(0x3FFFFFFF) + 1)
  val (a, b) = if (r1 <= r2) (r1, r2) else (r2, r1)
  val (center, extent) = binSplit(a, b)
  assert((center >= a) && (center <= b) && (center - extent) <= a &&
         (center - extent) >= 0 && (center + extent) > b, (a, b, center, extent))
}

for (i <- 0 to 100000) { test() }