Geek Answers Handbook

An integer in the interval with the maximum number of trailing zero bits

Sought is an efficient algorithm that finds a unique integer in the 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 && 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

and etc.

+4
source share
4 answers

This 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 returns a number with these 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 that the solution log (log (n)) has a small enough constant term to beat this. (But you can do a binary search on the number of zeros to get the log (log (n)).)

+5
source

I decided to take Rex 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) }

Comparison 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)))
+4
source

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

Otherwise, select the highest power of the two, which is less than the minimum.

Is there 1,100,000 ... 0 in your binding? If so, you won. If it is even less than the minimum, try 1110000 ... 0; otherwise, if it is greater than your maximum border, try 1010000 ... 0.

And so on, until you win.

+2
source

as a conclusion, here is my version of Rex’s answer, which gives both a central value and a “degree”, which is the minimum power at two distances from the center, which covers both a in 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() }
0
source

More articles:


All Articles