algorithm - 具有相同数量的 0 和 1 的二进制数

Question

给定一个二进制字符串或一个二进制数字(可以随意以任何方式获取)，我需要找出下一个较小的二进制数字，但保留原始二进制字符串或数字中 0 和 1 的数量。

例如

If the given binary number or string was 11100000, the required output would be 11010000.

If the given binary number or string was 11010000, the required output would be 11001000.

当然，我可以用蛮力方法来做到这一点。但我需要一个更好的解决方案。最佳的实现方式是什么？我想知道是否有人可以帮助我使用按位运算在 O(1) 中找到解决方案。

Answer 1

这是对 Setzer22 答案的详细阐述，该答案很接近，但缺少一个重要部分。

FindNextSmallestWithSameNumberOfBits(string[1...n])
1. for i = n - 1  to 1 do
2.     if string[i+1] = 0 and string[i] = 1 then
3.         string[i] := 0
4.         string[i+1] := 1
5.         sort(string[i+2...n], descending)
6.         return string[1...n]
7. return "no solution"

这是一个O(n)算法，当输入大小不受限制时，它是该问题的可证明最佳渐近界；虽然这是“按位”，因为它对位进行操作，但它显然没有使用人们通常认为的“按位操作”。幸运的是，对于任意长度的输入，使用传统的“按位运算”相对于此方法没有渐近优势。对于渐近分析不易应用的固定长度输入，使用 Asuka 在该问题的另一个答案中所链接的技术可能会更好。

请注意，根据注释，第 5 行的排序可以通过简单地反转字符串来替换。这样做的原因是，该子字符串保证采用 0...01...1 形式(即，任何 0 左侧的任何 0)。 1s)，因为如果不是，我们就已经找到了字符串 10 的出现并满足了第 2 行的条件。

Setzer22 的答案中缺少的关键是，一旦您将最右边的 1 及其右侧的 0 移动到右侧，您就需要将所有最右的 1 左移到最左。原因是向右移动的 1 位比其右侧的位更重要，因此向左移动任何不太重要的 1将给出一个更大的数字，但不足以抵消减少更高有效位的影响。

基于注释的澄清:请注意，在上面给出的伪代码的第 7 行中，算法可能不会返回有效的字符串。原因是，有时，不存在具有相同数量的1的字符串来表示较小的数字。当且仅当字符串 01 没有作为子字符串出现在输入字符串中时才会发生这种情况(在这种情况下，第 2 行的条件永远不会满足)。

这并不是有史以来最清晰的解释，因此如果需要更多工作，请告诉我。这是一个例子:

10011 // input
01011 // right-shift the right-most 1 bit with a 0 to the right of it
01110 // left-shift all 1 bits to the right of the right-shifted as far as possible

1010100011 // input
1010010011 // right-shift the right-most 1 bit with a 0 to the right of it
1010011100 // left-shift all 1 bits to the right of the right-shifted bit as far as possible

我刚刚想到的一种澄清这一点的方法是:右移1位保证结果将小于原始数字；将1左移到右侧可保证结果不小于所需的值。