自行设计大整数的移位

Question

请设计一个16个字节的大整数数据类型，并实现它的左移位操作（“<<”）

Answer 1

该回答引用ChatGPT

为了设计一个16字节的大整数数据类型，我们可以使用一个包含4个64位整数的数组。每个数组元素都可以表示16个字节的数据，因此，我们可以通过操作数组元素来进行大整数运算。

---

下面是一个简单的示例代码，其中我们定义了一个名为 BigNumber 的类，该类具有16字节的存储容量，并实现了左移位操作。在这个示例中，我们将左移操作实现为将数组元素依次左移，并处理进位。请注意，这只是一种简单的实现方式，实际上可能还需要考虑许多其他因素，如符号扩展、溢出检查等。

class BigNumber {
private:
    uint64_t data[4];
public:
    BigNumber() {
        memset(data, 0, sizeof(data));
    }
    BigNumber(const BigNumber& other) {
        memcpy(data, other.data, sizeof(data));
    }
    BigNumber& operator<<(int shift) {
        int words = shift / 64;
        int bits = shift % 64;
        if (bits > 0) {
            for (int i = 3; i >= words; i--) {
                data[i] <<= bits;
                if (i > words && (data[i-1] >> (64-bits) > 0)) {
                    data[i] |= (data[i-1] >> (64-bits));
                }
            }
        } else {
            for (int i = 3; i >= words; i--) {
                data[i] = data[i-words];
            }
        }
        for (int i = 0; i < words; i++) {
            data[i] = 0;
        }
        return *this;
    }
};

在上述代码中，我们使用了位运算符 << 来实现左移操作。具体来说，我们首先计算要移动的字数和位数。然后，我们对数组元素进行循环处理，将每个元素左移指定的位数，并处理进位。最后，我们将已经处理过的元素清零。

---

请注意，此处我们假设输入的移动位数为正数。如果要支持负数的移位操作，我们还需要实现右移操作，并根据移动位数的符号选择调用左移或右移操作。