在C程序中下一个更大数字的二进制表示形式,具有相同的1和0?
假设我们有一个二进制数,即数字n的表示。我们必须找到一个最小但大于n的数字的二进制表示形式,并且它也具有相同的数字0和1。因此,如果数字为1011(十进制为11),那么输出将为1101(13)。使用下一次排列计算可以找到此问题。让我们看一下获得想法的算法。
算法
nextBin(bin)-
Begin len := length of the bin for i in range len-2, down to 1, do if bin[i] is 0 and bin[i+1] = 1, then exchange the bin[i] and bin[i+1] break end if done if i = 0, then there is no change, return otherwise j:= i + 2, k := len – 1 while j < k, do if bin[j] is 1 and bin[k] is 0, then exchange bin[j] and bin[k] increase j and k by 1 else if bin[i] is 0, then break else increase j by 1 end if done return bin End
示例
#include <iostream> using namespace std; string nextBinary(string bin) { int len = bin.size(); int i; for (int i=len-2; i>=1; i--) { if (bin[i] == '0' && bin[i+1] == '1') { char ch = bin[i]; bin[i] = bin[i+1]; bin[i+1] = ch; break; } } if (i == 0) "No greater number is present"; int j = i+2, k = len-1; while (j < k) { if (bin[j] == '1' && bin[k] == '0') { char ch = bin[j]; bin[j] = bin[k]; bin[k] = ch; j++; k--; } else if (bin[i] == '0') break; else j++; } return bin; } int main() { string bin = "1011"; cout << "Binary value of next greater number = " << nextBinary(bin); }
输出结果
Binary value of next greater number = 1101