提问者:小点点

如何生成所有二进制字符串的顺序(递增)到2^63而不转换数字?


输出应该像0 1 10 11 100 101 110 111 100 100 1 101 1 101 1 110 1 110 1 111 1 111 1 100 00...等

在这里,这应该是不需要从数字转换而生成的。例如,我们不应该通过将7转换为二进制来生成111。


共1个答案

匿名用户

因为您需要的唯一特性是增量,所以您可以很容易地编写一个类:

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

也许bitset是一种更好的数据结构,而不是在只关心1个位的情况下用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方法留给您。

这不是最有效的方法,但它很干净,也很容易理解。