Question

How to encode and decode any string into Base‑36 in C++

Answer 1

#include <iostream>
#include <string>
#include <vector>
#include <cstdint>
#include <algorithm>

/*
    Base-36 encoding/decoding:
    --------------------------
    Base-36 digits: 0–9, A–Z
    Encoding:
      - Convert string → big integer (base-256)
      - Convert big integer → base-36

    Decoding:
      - Convert base-36 → big integer
      - Convert big integer → original bytes
*/

const char base36Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

// Helper: convert Base-36 character → numeric value
int base36Value(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    return c - 'A' + 10;
}

std::string encodeToBase36(const std::string &input) {
    std::vector<uint64_t> number(1, 0);

    // Convert string → big integer (base-256)
    for (unsigned char c : input) {
        uint64_t carry = c;
        for (size_t i = 0; i < number.size(); ++i) {
            uint64_t value = number[i] * 256 + carry;
            number[i] = value % ((uint64_t)1 << 32);
            carry = value >> 32;
        }
        if (carry > 0) number.push_back(carry);
    }

    // Convert big integer → Base-36
    std::string encoded;
    while (!(number.size() == 1 && number[0] == 0)) {
        uint64_t remainder = 0;

        for (size_t i = number.size(); i-- > 0;) {
            uint64_t value = (remainder << 32) + number[i];
            number[i] = value / 36;
            remainder = value % 36;
        }

        while (number.size() > 1 && number.back() == 0)
            number.pop_back();

        encoded.push_back(base36Digits[remainder]);
    }

    std::reverse(encoded.begin(), encoded.end());
    return encoded;
}

std::string decodeFromBase36(const std::string &encoded) {
    // Convert Base-36 → big integer
    std::vector<uint64_t> number(1, 0);

    for (char c : encoded) {
        int digit = base36Value(c);
        uint64_t carry = digit;

        for (size_t i = 0; i < number.size(); ++i) {
            uint64_t value = number[i] * 36 + carry;
            number[i] = value % ((uint64_t)1 << 32);
            carry = value >> 32;
        }
        if (carry > 0) number.push_back(carry);
    }

    // Convert big integer → original bytes (base-256)
    std::string output;

    while (!(number.size() == 1 && number[0] == 0)) {
        uint64_t remainder = 0;

        for (size_t i = number.size(); i-- > 0;) {
            uint64_t value = (remainder << 32) + number[i];
            number[i] = value / 256;
            remainder = value % 256;
        }

        while (number.size() > 1 && number.back() == 0)
            number.pop_back();

        output.push_back(static_cast<char>(remainder));
    }

    std::reverse(output.begin(), output.end());
    return output;
}

int main() {
    std::string text = "Hello Universe!";
    std::string encoded = encodeToBase36(text);
    std::string decoded = decodeFromBase36(encoded);

    std::cout << "Original: " << text << "\n";
    std::cout << "Base-36 encoded: " << encoded << "\n";
    std::cout << "Decoded: " << decoded << "\n";
}


/*
run:

Original: Hello Universe!
Base-36 encoded: LP4N024HJ1YVBVD84Y8TYQP
Decoded: Hello Universe!

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <string>
#include <vector>
#include <cstdint>
#include <algorithm>

// Dictionary for Base-36 digits
const std::string BASE36_CHARS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

/**
 * Encodes an arbitrary string into a Base-36 string.
 * It treats the entire string as a large byte array (big-endian base-256 number)
 * and performs arbitrary-precision division to convert it to base-36.
 */
std::string encodeToBase36(const std::string& input) {
    if (input.empty()) return "";

    // Copy input bytes into a vector for in-place manipulation
    std::vector<uint8_t> bytes(input.begin(), input.end());
    std::string result = "";

    // Count leading zeros to preserve them in the output
    size_t leadingZeros = 0;
    while (leadingZeros < bytes.size() && bytes[leadingZeros] == 0) {
        leadingZeros++;
    }

    // Convert base-256 (bytes) to base-36 using large-integer division
    size_t startIdx = leadingZeros;
    while (startIdx < bytes.size()) {
        uint32_t remainder = 0;
        
        // Divide the large number by 36
        for (size_t i = startIdx; i < bytes.size(); ++i) {
            uint32_t current = remainder * 256 + bytes[i];
            bytes[i] = current / 36;
            remainder = current % 36;
        }

        // Append the character corresponding to the remainder
        result += BASE36_CHARS[remainder];

        // Advance startIdx if the leading bytes have become 0
        while (startIdx < bytes.size() && bytes[startIdx] == 0) {
            startIdx++;
        }
    }

    // Append '0' for each preserved leading zero byte
    for (size_t i = 0; i < leadingZeros; ++i) {
        result += '0';
    }

    // Because we collected remainders from least-significant to most-significant, reverse it
    std::reverse(result.begin(), result.end());
    return result;
}

/**
 * Decodes a Base-36 string back to its original string format.
 * It treats the base-36 string as a giant number and converts it back to base-256.
 */
std::string decodeFromBase36(const std::string& input) {
    if (input.empty()) return "";

    std::vector<uint8_t> bytes;
    bytes.push_back(0); // Start with a value of 0

    // Count leading '0' characters to preserve padding
    size_t leadingZeros = 0;
    while (leadingZeros < input.size() && input[leadingZeros] == '0') {
        leadingZeros++;
    }

    // Process each base-36 character
    for (size_t i = leadingZeros; i < input.size(); ++i) {
        char c = std::toupper(input[i]);
        size_t value = BASE36_CHARS.find(c);
        
        if (value == std::string::npos) {
            throw std::invalid_argument("Invalid character in Base-36 string.");
        }

        // Multiply existing bytes by 36 and add the new value
        uint32_t carry = value;
        for (size_t j = 0; j < bytes.size(); ++j) {
            uint32_t current = bytes[j] * 36 + carry;
            bytes[j] = current % 256;
            carry = current / 256;
        }

        // If there is still a carry left, append new bytes
        while (carry > 0) {
            bytes.push_back(carry % 256);
            carry /= 256;
        }
    }

    // The bytes are accumulated in little-endian order, reverse to get big-endian back
    std::reverse(bytes.begin(), bytes.end());

    // Construct the final string, prepending the preserved zero bytes
    std::string result(leadingZeros, '\0');
    result.append(bytes.begin(), bytes.end());

    // If the loop only processed zeros (or nothing), strip the initial placeholder zero
    if (result.size() > leadingZeros && result[leadingZeros] == '\0' && bytes.size() == 1) {
        result.pop_back();
    }

    return result;
}

int main() {
    std::string text = "Hello Universe!";
    
    // Encoding
    std::string encoded = encodeToBase36(text);
    std::cout << "Original: " << text << "\n";
    std::cout << "Encoded : " << encoded << "\n";

    // Decoding
    std::string decoded = decodeFromBase36(encoded);
    std::cout << "Decoded : " << decoded << "\n";
}


/*
run:

Original: Hello Universe!
Encoded : LP4N024HJ1YVBVD84Y8TYQP
Decoded : Hello Universe!

*/

 

70+ SQL courses for beginners and professionals