BitSet bug破解编码面试？
BitSet bug破解编码面试？
提问于 2013-09-02 09:23:36
下面是BitSet在破解编码面试书中解决问题10-4中的实现。为什么它分配一个大小为/32的数组而不是(大小/32+ 1)。我是不是漏掉了什么，还是这是个bug？
如果我将33传递给BitSet的构造函数，那么我将只分配一个int，如果我试图设置或获取位32，我将获得AV！
package Question10_4;
class BitSet {
int[] bitset;
public BitSet(int size) {
bitset = new int[size >> 5]; // divide by 32
}
boolean get(int pos) {
int wordNumber = (pos >> 5); // divide by 32
int bitNumber = (pos & 0x1F); // mod 32
return (bitset[wordNumber] & (1 << bitNumber)) != 0;
}
void set(int pos) {
int wordNumber = (pos >> 5); // divide by 32
int bitNumber = (pos & 0x1F); // mod 32
bitset[wordNumber] |= 1 << bitNumber;
}}
回答 2
Stack Overflow用户
发布于 2013-09-02 11:10:38
从我从阅读你提到的解决方案(在第205页)收集到的信息以及我对计算机编程的了解很少，对我来说，这似乎是一个位集的特殊实现，意味着在其构造中接受32,000的参数(参见checkDuplicates函数)。这个问题是关于检查一个数字从1到N的数组，其中N最多是32,000，只有4KB的内存)。
这样，就创建了一个包含1000个元素的数组，每个元素用于位集中的32位。你可以在bitset类中看到，为了得到一个位的位置，我们(求底)除以32得到数组索引，然后mod 32得到具体的位位置。
Stack Overflow用户
发布于 2013-09-03 22:52:25
是的，书中的答案是错误的。正确答案：
bitset = new int[(size + 31) >> 5]; // divide by 32页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/18564551
复制相关文章
相似问题
腾讯云开发者
