algorithm - 破解编码面试中的BitSet bug？

Question

下面是破解coding面试书第10-4题解法中BitSet的实现。为什么它分配的数组大小为 32 而不是 (size/32 + 1)。我在这里遗漏了什么还是这是一个错误？

如果我将 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;
    }

Answer 1

从阅读您提到的解决方案(第 205 页)以及我对计算机编程的一点了解中我可以收集到的信息，在我看来，这是一个位集的特殊实现，意味着采用 32,000 的参数在它的构造中(参见 checkDuplicates 函数。问题是关于检查一个包含从 1 到 N 的数字的数组，其中 N 最多为 32,000，并且只有 4KB 的内存)。

这样，创建了一个包含 1000 个元素的数组，每个元素用于位集中的 32 位。你可以在bitset类中看到，为了得到一个位的位置，我们(floor)除以32得到数组索引，然后mod 32得到具体的位位置。