algorithm – 具有最大零尾位数的区间中的整数

发布时间：2020-12-16 18:21:49 所属栏目：安全来源：网络整理

导读：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

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

等等

解决方法

这个找到零的数量：

// 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,mask: Int = 0xFFFFFFFE): Int = {
  if (a > (b & mask)) b & (mask>>1)
  else nmtz(a,mask<<1)
}

我怀疑log(log(n))解决方案有一个足够小的常数项来击败它. (但你可以对零的数量进行二进制搜索以得到log(log(n)).)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!