Suppose we have a binary number that represents a number n. We need to find a binary number that is larger than n but smallest, and that also has the same number of 0s and 1s. So if the number is 1011 (11 in decimal), then the output will be 1101 (13 in decimal). This problem can be solved using the next permutation calculation. Let's look at the algorithm to get this idea.
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
The above is the detailed content of Binary representation of next larger number with same number of 1's and 0's in C program?. For more information, please follow other related articles on the PHP Chinese website!