การแสดงผลเลขฐานสองของเลขที่มากกว่าและมีจำนวน 1 และ 0 เท่ากันในโปรแกรม C

สมมติมีเลขฐานสองหนึ่งตัว แทนตัวเลข n ต้องหาการแทนฐานสองของตัวเลขที่น้อยที่สุดแต่ใหญ่กว่า n และมีจำนวน 0 และ 1 เท่าเดิม เช่น 1011 (11 ทศนิยม) ผลลัพธ์คือ 1101 (13) โจทย์นี้แก้ได้ด้วย next-permutation

อัลกอริทึม

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

ตัวอย่างโค้ด C++

#include 
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