Целое число в интервале с максимальным числом завершающих нулевых бит

Question

Sought - эффективный алгоритм, который находит уникальное целое число в интервале [a, b], который имеет максимальное число конечных нулей в двоичном представлении (a и b - целые числа> 0):

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

def binSplit(a: Int, b: Int): Int = {
  require(a > 0 && a <= b)
  val res = ???
  assert(res == bruteForce(a, b))
  res
}

вот несколько примеров

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

и т. Д.

Answer 1

Этот находит число нулей:

// 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)
}

Этот возвращает число с этими нулями:

// 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)
}

Я сомневаюсь, что решение log (log (n))достаточно маленький постоянный срок, чтобы победить это.(Но вы можете выполнить бинарный поиск по количеству нулей, чтобы получить log (log (n)).)

Answer 2

Я решил принять вызов Рекса и произвести что-то быстрее. : -)

// 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)
}

Бенчмарк с

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)))

Answer 3

Сначала посмотрите, есть ли степень двойки, лежащая в вашем интервале.Если есть хотя бы один, выигрывает самый большой.

В противном случае выберите наибольшую степень двух, которая меньше вашей минимальной границы.

Имеет ли 1100000 ... 0 ваши границы??Если да, ты выиграл.Если он все еще меньше минимальной границы, попробуйте 1110000 ... 0;в противном случае, если он превышает ваш максимальный предел, попробуйте 1010000 ... 0.

и так далее, пока вы не выиграете.

Answer 4

в заключение, вот мой вариант ответа Рекса, который дает как значение центра, так и «экстент», который представляет собой минимальную степень двух расстояний от центра, которая покрывает как a в одном направлении, так и b в другом.

@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() }