数组中存放0到n中的缺少一个数的连续数,找出该缺少的数
数组中存放0到n中的缺少一个数的连续数,找出该缺少的数
一贱书生 发表于1年前
数组中存放0到n中的缺少一个数的连续数,找出该缺少的数
  • 发表于 1年前
  • 阅读 51
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】新注册用户域名抢购1元起>>>   

最低有效位(Least Significant Bit)代表二进制数中的最小的单位,可以用来指示数字很小的变化。也就是说,LSB是一个二进制数字中的第0位(即最低位),具有权值为2^0,可以用它来检测数的奇偶性。在大端序中,lsb指最右边的位。

   最高有效位the Most Significant Bitmsb),是指一个n位二进制数字中的n-1位,具有最高的权值2^n − 1。与之相反的称之为最低有效位。在大端序中,msb即指最左端的位。对于有符号二进制数,负数采用反码或补码形式,此时msb用来表示符号,msb为1表示负数,0表示正数。

   注意:

    (1)MSB(全大写)有时也指the Most Significant Byte,指多字节序列中具有最大权重的字节。

     (2)LSB(全大写)有时也指Least Significant Byte,指多字节序列中最小权重的字节。

 

public int findMissing(ArrayList<BitInteger> array)
{
/*
bit 0对应于LSB.以此为起点,逐步向较高的位推进
*/
return findMissing(array,0);
}
public int findMissing(ArrayList<BitInteger> input,int column)
{
if(column>=BitInteger.INTEGER_SIZE)//终止条件或错误条件
{
return 0;
}
ArrayList<BitInteger> oneBits=new ArrayList<BitInteger>(input.size()/2);
ArrayList<BitInteger> zeroBits=new ArrayList<BitInteger>(input.size()/2);
for(BitInteger t:input)
{
if(t.fetch(column)==0)
{
zeroBits.add(t);
}
else
{
oneBits.add(t);
}
}
if(zeroBit.size()<=oneBits.size())
{
int v=findMissing(zeroBits,column+1);
return (v<<1)|0;
}
else
{
int v=findMissing(oneBits,column+1);
return (v<<1)|1;
}
}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 19
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: