3

下面是破解编码面试书10-4题解法中BitSet的实现。为什么它分配一个 size/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;
    }

}

4

2 回答 2

0

从阅读您提到的解决方案（第 205 页）中收集到的信息，以及我对计算机编程的了解很少，在我看来，这是一个特殊的 bitset 实现，旨在在其构造中采用 32,000 的参数（请参阅checkDuplicates函数。问题是关于检查数字从 1 到 N 的数组，其中 N 最多为 32,000，只有 4KB 的内存）。

这样，创建了一个包含 1000 个元素的数组，每个元素用于位集中的 32 位。您可以在 bitset 类中看到，要获取位的位置，我们（地板）除以 32 以获取数组索引，然后对 32 取模以获取特定的位位置。

于 2013-09-02T03:10:38.023 回答
0

是的，书中的答案是不正确的。正确答案：

bitset = new int[(size + 31) >> 5]; // divide by 32
于 2013-09-03T14:52:24.557 回答