第一题：计算二进制数两个1之间的间距

  • 题目：

我的思路

  • 英文翻译过来就是把数字化成二进制，计算两个1之间的最大间距。1000,1100,1010的最大间距分别是0,1,2.以此类推
  • 我的第一反应是大学数字逻辑课上的一个知识点，十进制转化为二进制——短除法！
  • 也就是说，在接收到输入的十进制数之后，利用短除法，转化为二进制数。转化的过程进行间距的计算
  • 虽然短除法先计算出来的是二进制低位的数，但是1010的间距从左往右数和从右往左数，结果是等价的
  • 实现如下：
func BiggestGap(n int) int {    distance,temp := 0,0    bValue := 0    for n,bValue = bDiv(n);bValue==0; {        n,bValue = bDiv(n)    }    for (n>0)  {        n,bValue = bDiv(n)        temp+=1        if bValue==1 {            if temp>distance {                distance=temp            }            temp = 0        }    }    return distance}func bDiv(n int)(remainder,bValue int){    if n%2 == 0 {        return n/2,0    }else {        return (n-1)/2,1    }}

别人的思路

  • 看完题目，肯定是得自己先琢磨。琢磨完了，得学习学习别人是怎么分析的。先贴上别人的实现，源码是C++，我翻译成golang版本了
  • 别人家的版本：
func BinaryDistance(n uint) int {    var i uint    distance,last:=0,-1    for i=0;i<32;i++{        if (n >> i) & 1 !=0 {            if last>=0 {                distance = max(distance,int(i)-last)            }            last = int(i)        }    }    return distance}func max(numbers ...int)  int{    max := 0    for _,num := range numbers{        if num>max {            max=num        }    }    return max}
  • 这个思路的关键点是 xxxxx0 & 000001的结果恒为零，xxxxx1 & 000001的结果恒为1（x的意思是为0或1）。
  • 有了这个计算基础之后，加上int类型默认是32位，借助移位运算符 >>，就能够判断二进制数的每一位是0还是1了
  • 最后这部分就没什么难度了，不断计算相邻两个1的距离，比之前保存的最大间距大，更新，小，丢弃，调整位置继续计算