Biểu diễn nhị phân của số lớn hơn tiếp theo cùng số bit 1 và 0 trong C

Cho số nhị phân, tìm số nhị phân nhỏ nhất lớn hơn nó nhưng có cùng số bit 0 và 1. Ví dụ: 1011 (11) -> 1101 (13).

Giải bằng thuật toán next-permutation trên chuỗi bit.

Thuật toán

nextBin(bin)
BẮT ĐẦU
len = bin.length
VỚI i = len-2 XUỐNG 1
    NẾU bin[i]=='0' VÀ bin[i+1]=='1' THÌ
        HOÁN ĐỔI bin[i], bin[i+1]; BREAK
NẾU i==0 TRẢ VỀ "No greater number"
j = i+2, k = len-1
KHI j < k
    NẾU bin[j]=='1' VÀ bin[k]=='0' THÌ HOÁN ĐỔI, j++, k--
    NGƯỢC LẠI NẾU bin[i]=='0' THÌ BREAK
    NGƯỢC LẠI j++
KẾT THÚC
TRẢ VỀ bin
KẾT THÚC

Chương trình C++ ví dụ

#include <iostream>
using namespace std;

string nextBinary(string bin) {
    int len = bin.size(), i;
    for (i = len-2; i >= 1; i--) {
        if (bin[i]=='0' && bin[i+1]=='1') {
            swap(bin[i], bin[i+1]);
            break;
        }
    }
    if (i == 0) return "No greater number is present";
    int j = i+2, k = len-1;
    while (j < k) {
        if (bin[j]=='1' && bin[k]=='0') {
            swap(bin[j], bin[k]);
            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);
}

Kết quả

Binary value of next greater number = 1101