如何在不转换数字的情况下按顺序（增加）生成所有二进制字符串，直到 2^63？

Question

输出应该是这样的 0 1个 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000 ....等等

这里应该是不用数字转换生成的。例如，我们不应该通过将 7 转换为二进制来生成 111。

Answer 1

由于您唯一需要的功能是递增，因此您可以轻松编写 class:

 class BinaryNumber {
 public:
      uint8_t data[64];  // This is wasted space, see notes.
      bool increment();
 };
 std::ostream & operator<<(std::ostream &, const BinaryNumber &);

当我们只关心其中的一位时，bitset 可能是一种比将所有 space 浪费在 8 位值更好的数据结构，但我想保持简单。

增加一个值也不错。

// Returns false once we hit max value
bool BinaryNumber::increment() {
    bool retVal = false;
    for (int index = 0; index < 64; ++index) {
        if (data[index] == 0) {
            data[index] = 1;
            retVal = true;
            break;
        }
        else {
            data[index] = 0;
        }
    }
    return retVal;
}

考虑将值 0 递增。查看代码。如果第一位是 0，我们将它变成 1 并中断循环（返回 true 因为我们提早中断）。

如果它是 1，我们将其翻转回零并递归，在索引 [1] 处递增。循环直到我们达到零，这样我们就不需要再携带任何 1。

write方法就交给你了

这不是最有效的方法，但它简洁易懂。

Answer 2

由于目标是为输出生成一个字符串，因此使用 std::string 来保存当前值是有意义的。获取下一个值意味着将当前值加 1 并处理进位，就像您手动操作一样。所以;

class binary_string {
public:
    binary_string() : text(‘0’) {}
    const std::string& get() const { return text; }
    bool next();
private:
    std::string text;
};

bool binary_string::next() {
    std::size_t pos;
    for (pos = 0; pos < text size(); ++pos) {
        if (text[pos] == ‘0’) {
            text[pos) = ‘1’:
            break;
        else
            text[pos] = ‘0’;
    }
    if (pos == 64)
        return false;
    if (pos == text.size())
        text.push_back(‘0’)
    return true;
}

使用：

int main() {
    binary_string str;
    do {
        std::cout << str.get();
    } while (str.next());
    return 0;
}

做好准备，这需要很长的时间才能完成。

如何在不转换数字的情况下按顺序（增加）生成所有二进制字符串，直到 2^63？

How to generate all binary string in order(increasing) upto 2^63 without converting numbers?

c++

string

algorithm

binary