文档章节

数组中存放0到n中的缺少一个数的连续数,找出该缺少的数

一贱书生
 一贱书生
发布于 2016/11/19 10:36
字数 378
阅读 54
收藏 0

最低有效位(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
博文 724
码字总数 600123
作品 0
编程题——31~40

三十一、连续子数组的最大和 输入一个整数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 三十二、从1到n整数中...

thanatos_y
2016/07/26
13
0
几个算法题

1 在一个字符串中找到第一个只出现一次的字符,如输入abac,则输出b 本题看似很简单,开个长度为256的表,对每个字符hash计数就可以了,但很多人写的代码都存在bug,可能会发生越界访问。这是...

泳泳啊泳泳
2017/12/25
0
0
一些面试题,整理自网络

腾讯面试题:tcp三次握手的过程,accept发生在三次握手哪个阶段? 答accept发生在三次握手之后。 第一次握手:客户端发送syn包(syn=j)到服务器。 第二次握手:服务器收到syn包,必须确认客户...

waveer
2016/12/08
24
0
面试精选之位操作问题集锦

Java 中位运算符有与(&)、或(|)、非(~)、异或(^)、左移(<<)、右移(>>)、无符号右移(>>>),只针对 int 类型有效,也可以作用于 byte、short、char、long,当为这四种类型时,J...

JohnnyShieh
2017/12/28
0
0
计算机等级考试三级网络技术上机题(11)

函数ReadDat( )实现从文件IN83.DAT中读取1000个十进制整数到数组xx中。请编制函数Compute( )分别计算出xx中偶数的个数even、奇数的平均值ave1、偶数的平均值ave2及所有偶数的方差totfc的值,...

等级考试
2014/12/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

面向对象类之间的关系

面向对象类之间的关系:is-a、has-a、use-a is-a关系也叫继承或泛化,比如大雁和鸟类之间的关系就是继承。 has-a关系称为关联关系,例如企鹅在气候寒冷的地方生活,“企鹅”和“气候”就是关...

gackey
45分钟前
1
0
读书(附电子书)|小狗钱钱之白色的拉布拉多

关注公众号,在公众号中回复“小狗钱钱”可免费获得电子书。 一、背景 之前写了一篇文章 《小狗钱钱》 理财小白应该读的一本书,那时候我才看那本书,现在看了一大半了,发现这本书确实不错,...

tiankonguse
今天
1
0
Permissions 0777 for ‘***’ are too open

异常显示: @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ WARNING: UNPROTECTED PRIVATE KEY FILE! @ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ ......

李玉长
今天
3
0
区块链10年了,还未落地,它失败了吗?

导读 几乎每个人,甚至是对通证持怀疑态度的人,都对区块链的技术有积极的看法,因为它有可能改变世界。然而,区块链技术问世已经10年了,我们仍然没有真正的用上区块链技术。 几乎每个人,甚...

问题终结者
今天
2
0
20180921 su与sudo命令、限制root用户通过ssh远程登录

su 命令 用户切换。 su # 切换到root用户su username # 切换到username用户# su 后面加-时,会初始化当前用户的各种环境su - username # 指定用户执行某些命令 su - -c "touch /tm...

野雪球
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部