我正在尝试创建一个由 int[]
支持的位 vector 。
所以我有以下代码:
public class BitVector {
int[] vector = new int[1 << 16];
public void setBit(int nextInt) {
nextInt = nextInt & 0xFFFF;
int pos = nextInt / 32;
int offset = nextInt % 32;
vector[pos] |= (1 << offset);
}
public int findClearedBit() {
for(int i = 0; i < vector.length; i++){
for(int j = 0; j < 8; j++){
if((vector[i] & (1 << j)) == 0)
return i * 32 + j;
}
}
return -1;
}
}
我知道也许我应该使用 byte[]
等,但我想知道为什么这种方式不起作用。
我的想法是,我从流中传入 int
并保留低 16 位并将相应的位标记为已设置。因此,当我遍历 vector 时,我会发现缺少数字(由低 16 位表示)。
但是我得到了错误的结果。所以我相信我的处理是错误的。
有什么想法吗?
更新:
我有一个 32 位整数流。当我阅读它们时,我尝试通过使用较低的 16 位 并设置位 vector (代码已发布)来标记丢失的数字。
我还尝试找到丢失的高 16 位,第二次读取流。
因此,虽然缺少的数字是:231719592
= (1101110011111100001010101000
) = (3535
-49832
)
当我读取流时,我没有得到 49832
作为丢失的低位,但是 65536
更新2:
public int findMissingInt(File f)throws Exception{
Scanner sc = new Scanner(f);
int SIZE = 1 << 16;
int[] occurences = new int[SIZE];
while(sc.hasNext()){
occurences[getIdx(sc.nextInt())]++;
}
int missingUpper = -1;
for(int i = 0; i < occurences.length; i++){
if(occurences[i] < SIZE){
System.out.println("Found upper bits:"+i);
missingUpper = i;
break;
}
}
if(missingUpper == -1){
return -1;
}
//Arrays.fill(occurences, 0); //I reused this. Bellow changed after answer of Peter de Rivaz
BitVector v = new BitVector(new int[1 << (16-5)]);
sc = new Scanner(f);
while(sc.hasNext()){
v.setBit(sc.nextInt());
}
int missingLower = v.findClearedBit();
System.out.println("Lower bits:"+missingLower);
return createNumber(missingUpper, missingLower);
}
private int createNumber(int missingUpper, int missingLower) {
int result = missingUpper;
result = result << 16;
return result | missingLower;
}
public int getIdx(int nextInt) {
return (nextInt >>> 16);
}
我得到:
Missing number=231719592
Found upper bits:3535 //CORRECT
Lower bits:-1 //WRONG
Actual missing number=-1 //WRONG
最佳答案
我认为有两个问题:
您的数组有 65536 个条目,但您在每个条目中存储 32 位,因此您只需要 65536/32 个条目。
您在每个 int 中存储 32 位,但在查找间隙时只检查从 0 到 7 的 j
第一个错误意味着您的程序将 65536 报告为缺少的 16 位数字。 第二个错误意味着您的程序没有发现丢失的数字。
即改变
int[] vector = new int[1 << 16];
到
int[] vector = new int[1 << (16-5)];
和改变
for(int j = 0; j < 8; j++)
到
for(int j = 0; j < 32; j++)
编辑
从评论来看,问题实际上是如何在有限的内存中找到缺失的数字。这个问题的答案可以找到here on stackoverflow .
高级代码中还有一个错误。
在填充位集的第二遍期间,您应该只包含具有匹配高位位的数字。
即改变
v.setBit(sc.nextInt());
类似于
int nx = sc.nextInt();
if (getIdx(nx)==missingUpper)
v.setBit(nx);
关于java - 我的位 vector 有什么问题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13553232/