5

我正在研究这个问题并提出一个解决方案（可能需要添加一个或两个条件）但不确定这是否是正确的方法并且发现使用两个循环很麻烦并且不确定这是否是这样做的有效方法。如果有人有一些不错的技巧或任何更好的方法会受到欢迎，那就太好了:)。（语言不是障碍）

我的算法：

  • 首先找到数字中的第一个 '0' lsb 位
  • 然后找到与此“0”位相邻的下一个设置位
  • 将您找到的“0”位更改为 1，将“1”位更改为“0”
  • 你会得到的数字是下一个
  • 如果设置了所有位，那么您没有任何数字小于相同数量的“1”位。
void nextSmaller(int number) {
    int firstZeroBitHelper = 1, nextOneBitHelper;
    while (firstZeroBitHelper < number) {
        // when we find first lsb zero bit we'll stop
        bool bit = number & firstZeroBitHelper;
        if (bit == false)
            break;
        firstZeroBitHelper = firstZeroBitHelper << 1;
    }

    if (firstZeroBitHelper >= number) {
        cout << "No minimum number exists" << endl;
        return;
    }

    nextOneBitHelper = firstZeroBitHelper;
    nextOneBitHelper = nextOneBitHelper << 1;

    while (nextOneBitHelper < number) {
        // when we get '1' after the previous zero we stop
        bool bit = number & nextOneBitHelper;
        if (bit == true)
            break;
        nextOneBitHelper = nextOneBitHelper << 1;
    }

    // change the first zero to 1
    number = number | firstZeroBitHelper;
    // change the next set bit to zero
    number = number & ~nextOneBitHelper;

    cout << number << endl;
}
4

5 回答 5

5

Continuing from my comment..

Well, I found it, and pretty quickly too. See The Art of Computer Programming chapter 7.1.3 (in volume 4A), answer to question 21: "the reverse of Gosper's hack".

It looks like this:

t = y + 1;
u = t ^ y;
v = t & y;
x = v - (v & -v) / (u + 1);

Where y is the input and x the result. The same optimizations as in Gosper's hack apply to that division.

于 2013-09-21T08:18:59.920 回答
4

往上走：

  • 在数字中找到最右边的“01”并将其设为“10”。
  • 尽可能向右对齐所有后续 1 位。

往下走：

  • 在数字中找到最右边的“10”并将其设为“01”。
  • 左对齐所有后面的 1 位（即，如果您刚刚设置的位后面已经跟着一个 1，则不做任何事情）。

一个使向下情况清晰的示例：

  • 225 = 0b11 10 0001
  • 交换：0b11 01 000 1
  • 左对齐：0b1101 1 000 = 216

我将首先解释向上的情况，因为它对我来说不那么棘手。我们希望找到可以将 1 位向左移动一位的最不重要的位置（换句话说，最右边的 0 右侧有 1）。应该清楚的是，这是我们可以设置的最右边的位，因为我们需要为我们设置的每个位在其他地方清除一个位，并且我们需要在我们设置的位右侧的某个地方清除一个位，否则这个数字会变小而不是变大。

现在我们已经设置了这个位，我们想要清除一个位（以恢复设置位的总数），并重新洗牌剩余的位，使数字尽可能小（这使它成为下一个最大的数字）相同数量的设置位）。我们可以清除我们刚刚设置的那个位的右边的位，并且我们可以将任何剩余的 1 位尽可能推到最右边，而不必担心低于我们的原始数字，因为所有不太重要的位加起来仍然是小于我们刚刚设置的单个位。

找到下一个较低的数字而不是下一个较高的数字基本上是相同的，除了我们正在寻找可以将设置位向右移动一个位置的最右边的位置，并且在这样做之后，我们希望将所有不太重要的位移动为尽可能左。

看起来其他人已经掌握了这个很好的版本，但我想看看我是否可以很好地解释算法的逻辑/数学方面。

于 2013-09-21T09:03:24.080 回答
3

anatolyg 很好地涵盖了您的算法，但有一个更有效的解决方案。

您可以使用Gosper 的 hack并巧妙地意识到，如果您翻转位，那么 Gosper 会按降序生成值。

像这样的伪代码会起作用：

let k := number
let n := num bits in k (log base 2)
k = k ^ ((1 << n) - 1)
k = gosper(k)
k = k ^ ((1 << n) - 1)
return k

这为您提供了一个不错的 O(1)（如果您认为 xor 是线性时间，则为 O(log n)）算法。:)

有些情况你必须考虑，比如 if k=2^x-1for some x，但这很容易抓住。

于 2013-09-21T08:16:02.137 回答
2

您描述的算法不太正确；除了一个细节，它做的一切都是正确的。任何二进制数都具有以下形式，可以在算法的中间找到：

xxxxx...10000...1111...
         ---n---// f //

这里xxx...是任意位，连续的 0 和 1 的个数由firstZeroBitHelperand nextOneBitHelper( fand n) 决定。

现在你必须减少这个数字，留下相同数量的设置位，这必然会将最重要1的变为0：

xxxxx...0????...????...
         -----n+f------

请注意，位的任何值???都会使新数字小于原始数字，并且您确实希望选择这些位以使结果数字具有最大值：

xxxxx...011111...0000...
         ---f+1--//n-1//

因此，您不仅要翻转 2 位，还要翻转f+2位（一位从1to 0，f+1其他位从0to 1）。

一种方法如下。

首先关闭所有相关位：

number &= ~nextOneBitHelper;
number &= ~(nextOneBitHelper - 1);

现在打开所需的位，从 MSB 开始：

nextOneBitHelper >>= 1;
while (firstZeroBitHelper != 0)
{
    number |= nextOneBitHelper;
    nextOneBitHelper >>= 1;
    firstZeroBitHelper >>= 1;
}

可以在没有循环的情况下实现上述位旋转；为此，您需要计算n和f。这样做之后：

unsigned mask = (1 << (f + 1)) - 1; // has f+1 bits set to 1
mask <<= n - 1; // now has these bits at correct positions
number |= mask; // now the number has these bits set
于 2013-09-21T08:06:17.133 回答
1 
#include <iostream>

bool AlmostdivBy2(int num) {
    return (-~num & (num)) == 0;
}

void toggleright(int &num) {
    int t;
    for (t = -1; num & 1; t++)
        num >>= 1;
    ++num = (num << t) | ~-(1 << t);
}

void toggleleft(int &num) {
    while (~num & 1)
        num >>= 1; //Simply keep chopping off zeros
    //~num & 1 checks if the number is even
    //Even numbers have a zero at bit at the rightmost spot
}

int main() {

    int value;
    std::cin >> value;
    if (!AlmostdivBy2(value)) {
        (~value & 1) ? toggleleft(value) : toggleright(value);
    }
    std::cout << value << "\n";
    return 0;
}

我想我可能想多了，但这是我的解释：

  • 如果该数字接近 2 的幂，即 1、3、7、15、31 等值，那么没有比它小的值可以在其二进制表示中具有相同数量的 1。因此，我们不担心这些数字。

  • 如果数字是偶数，那是另一个简单的解决方法，我们只需从最后切掉零，直到数字是奇数

  • 奇数提出了最大的挑战，这就是为什么它是递归的。首先，您必须从数字的右侧开始找到第一个零位。找到后，您将在该数字上加一，这会将最后一位变为 1。随着递归展开，您不断将这些位向左移动并加一。完成后，您将拥有下一个最小的。

希望我没有混淆你

编辑

对其进行了更多工作，这是一个非递归版本toggleright

void toggleright(int &num) {    
    int t = 1;
    while ( (num >>= 1) & 1 && t++ );
    num = (-~num << ~-t) | ~-(1 << t);    
}
于 2013-09-21T09:30:23.927 回答