Bitwise Calculator — C++ source

// =============================================================================
//  bitwise.cpp — CosmoDev polyglot showcase port of the `bitwise` tool
//  -----------------------------------------------------------------------------
//  Language : C++ (C++17, standard library only)
//  Source:   ported from src/lib/bitwise.ts (the canonical, live TypeScript
//             lib); mirrors src/tool-sources/bitwise/{python.py,rust.rs}
//  License  : display source — part of CosmoDev's polyglot tool pages
//             (dev.cosmolabs.org). Shown verbatim alongside the JS/TS/Go/Rust/
//             Python ports and the other language ports.
//  -----------------------------------------------------------------------------
//  Pure, deterministic bitwise calculator. Zero deps. Operands are interpreted
//  as width-bit two's-complement values: any integer is normalized to the
//  half-open range [0, 2^width) before an operation, and every result is masked
//  back into that range — so the returned integer is always the unsigned
//  bit-pattern of the width-bit result.
//
//  C++ note: the TS source uses arbitrary-precision `bigint`. The C++ standard
//  library has no bignum type, so values live in std::int64_t/std::uint64_t.
//  This stays exact for every supported width (8/16/32/64): parsed magnitudes
//  fold through two's-complement wrapping (invisible after width-bit
//  normalization), and shift/rotate intermediates pre-mask the operand so
//  nothing exceeds 64 bits — arithmetically identical to the reference's
//  masked bigint shifts. Only literals beyond 2^64-1 diverge from the TS lib
//  (thrown as a clean out_of_range), far outside any realistic input.
//
//  The enum spellings `and_`/`or_`/`xor_`/`not_` carry a trailing underscore
//  because `and`, `or`, `xor`, `not` are alternative operator tokens in C++.
// =============================================================================

#include <algorithm>
#include <cctype>
#include <cstdint>
#include <cstring>
#include <stdexcept>
#include <string>
#include <vector>

namespace bitwise {

/// Numeric base for parsing and formatting bit patterns.
enum class base { bin, oct, dec, hex };

/// Supported bitwise operation. `not_` is unary on `a`; the binary ops take
/// `a` and `b`; for the shift/rotate ops `b` is the count.
enum class op { and_, or_, xor_, not_, shl, shr, rol, ror };

/// Operating field width, in bits: one of 8, 16, 32, 64.
using width = std::uint32_t;

/// Positional radix (2/8/10/16) consumed by the parser/formatter.
inline std::uint32_t radix(base b) {
    switch (b) {
    case base::bin: return 2;
    case base::oct: return 8;
    case base::dec: return 10;
    case base::hex: return 16;
    }
    return 10;
}

/// Lowercase digit alphabet valid for each base — drives validation and the
/// per-character digit-value lookup.
inline const char* digits(base b) {
    switch (b) {
    case base::bin: return "01";
    case base::oct: return "01234567";
    case base::dec: return "0123456789";
    case base::hex: return "0123456789abcdef";
    }
    return "0123456789";
}

/// Lowercase name, for error messages that match the TS lib.
inline const char* lower(base b) {
    switch (b) {
    case base::bin: return "bin";
    case base::oct: return "oct";
    case base::dec: return "dec";
    case base::hex: return "hex";
    }
    return "dec";
}

/// Lowercase ASCII copy of `s` — keeps an uppercase mantissa like "0xFF"
/// valid, mirroring the reference's lowered-string prefix handling.
inline std::string lowered(const std::string& s) {
    std::string out(s);
    std::transform(out.begin(), out.end(), out.begin(), [](unsigned char c) {
        return static_cast<char>(std::tolower(c));
    });
    return out;
}

/// Parse a numeric string in `base` into a signed 64-bit integer. Strips an
/// optional leading sign and the 0x/0b/0o prefixes (case-insensitive). Throws
/// std::invalid_argument on empty input or any digit invalid for the requested
/// base, and std::out_of_range on a literal whose magnitude exceeds 2^64-1.
/// The raw signed value is returned (no width normalization); callers fold it
/// into a field via normalize() / bitwise().
///
/// Magnitudes accumulate as std::uint64_t and negate by wrapping subtraction,
/// so the full unsigned range (e.g. hex 0xFFFFFFFFFFFFFFFF) round-trips
/// exactly — a wrap of 2^64 is invisible once the value is width-normalized.
inline std::int64_t parse(const std::string& value, base b) {
    // Trim ASCII whitespace from both ends.
    const char* ws = " \t\n\r";
    size_t begin = value.find_first_not_of(ws);
    if (begin == std::string::npos)
        throw std::invalid_argument("Empty " + std::string(lower(b)) + " value");
    size_t end = value.find_last_not_of(ws);
    std::string trimmed = value.substr(begin, end - begin + 1);

    // Peel off an optional leading '-' so negative literals parse correctly.
    bool negative = false;
    if (trimmed.front() == '-') {
        negative = true;
        trimmed.erase(0, 1);
    }
    if (trimmed.empty())
        throw std::invalid_argument("Empty " + std::string(lower(b)) + " value");

    // Strip each base prefix in turn (0x, then 0b, then 0o) from a lowered
    // copy — mirrors the reference's chained leading-prefix removal.
    std::string body = lowered(trimmed);
    for (const char* prefix : {"0x", "0b", "0o"})
        if (body.rfind(prefix, 0) == 0)
            body.erase(0, 2);
    if (body.empty())
        throw std::invalid_argument("Empty " + std::string(lower(b)) + " value");

    // Horner's method over the digit alphabet, with a checked accumulate:
    // an over-wide literal reports a clean error instead of wrapping.
    const char* alphabet = digits(b);
    std::uint64_t r = radix(b);
    std::uint64_t acc = 0;
    for (char c : body) {
        const char* hit = std::strchr(alphabet, c);
        if (hit == nullptr)
            throw std::invalid_argument(std::string("Invalid digit '") + c +
                                        "' for base " + lower(b));
        std::uint64_t digit = static_cast<std::uint64_t>(hit - alphabet);
        if (acc > (UINT64_MAX - digit) / r)
            throw std::out_of_range("Value out of range for base " +
                                    std::string(lower(b)));
        acc = acc * r + digit;
    }

    // Wrapping negate is exact mod 2^64 (all target platforms are two's
    // complement); the cast reinterprets the pattern as signed.
    return negative ? static_cast<std::int64_t>(UINT64_C(0) - acc)
                    : static_cast<std::int64_t>(acc);
}

/// Bitmask for a `w`-bit field: 2^w - 1. Width 64 is spelled directly
/// because 1 << 64 would overflow std::uint64_t.
inline std::uint64_t mask(width w) {
    return w == 64 ? UINT64_MAX : ((UINT64_C(1) << w) - 1);
}

/// Normalize any signed value to its unsigned w-bit two's-complement value,
/// i.e. into the half-open range [0, 2^w) — e.g. -1 at width 8 yields 255.
/// The reference computes ((n % m) + m) % m with m = 2^w on arbitrary-precision
/// ints; casting to std::uint64_t already yields n mod 2^64 (two's-complement
/// truncation), and ANDing with the width-bit mask reduces that to n mod 2^w —
/// the same canonical value, without materializing 2^64 itself.
inline std::uint64_t normalize(std::int64_t n, width w) {
    return static_cast<std::uint64_t>(n) & mask(w);
}

/// Render an unsigned value in `b`, zero-padded to at least `min_digits`
/// places. Manual base conversion keeps the port stdlib-only and yields the
/// lowercase digits of the TS `bigint.toString(radix)` output.
inline std::string format_u64(std::uint64_t v, base b, size_t min_digits) {
    static const char alphabet[] = "0123456789abcdef";
    std::uint64_t r = radix(b);

    // Extract digits LSB-first; the do/while renders "0" for zero naturally.
    std::string out;
    do {
        out.push_back(alphabet[v % r]);
        v /= r;
    } while (v != 0);
    if (out.size() < min_digits)
        out.insert(0, min_digits - out.size(), '0'); // zero-pad up to the minimum
    std::reverse(out.begin(), out.end());
    return out;
}

/// Render `n` in `b`, zero-padded to at least `min_digits` places. Negative
/// values carry a leading '-' and format their magnitude (computed with
/// wrapping subtraction — exact and INT64_MIN-safe). `min_digits` corresponds
/// to the `width` parameter of the TS reference (a width-bit binary value
/// needs exactly `width` digits).
inline std::string format(std::int64_t n, base b, size_t min_digits) {
    if (n < 0) {
        std::uint64_t mag = UINT64_C(0) - static_cast<std::uint64_t>(n);
        return "-" + format_u64(mag, b, min_digits);
    }
    return format_u64(static_cast<std::uint64_t>(n), b, min_digits);
}

/// Apply a w-bit operation. `a` is the (unary) operand for `not_`; `b` is the
/// second operand for binary ops and the shift/rotate count for shl/shr/rol/
/// ror. Both operands are normalized to w-bit two's complement first; the
/// result is masked to `w` bits.
///
/// For shl/shr we short-circuit when the shift count meets or exceeds `w`:
/// every significant bit is shifted out, so the masked result is zero (this
/// also keeps every shift amount below 64 — C++ leaves shifts >= 64
/// undefined). For shl/rol the shifted operand is pre-masked with
/// (mask >> count): the low `w` bits of the true bigint shift are identical,
/// but the intermediate can no longer exceed 64 bits.
inline std::uint64_t bitwise(op o, std::int64_t a, std::int64_t b, width w) {
    std::uint64_t m = mask(w);
    std::uint64_t x = normalize(a, w);
    std::uint64_t y = normalize(b, w);

    switch (o) {
    case op::and_:
        return x & y;
    case op::or_:
        return x | y;
    case op::xor_:
        return x ^ y;
    case op::not_:
        return ~x & m;
    case op::shl:
        if (y >= w)
            return 0;
        return (x & (m >> y)) << y; // == (x << y) & m, without overflow
    case op::shr:
        // x is normalized non-negative → logical (zero-filling) shift.
        return y >= w ? 0 : x >> y;
    case op::rol:
    case op::ror: {
        std::uint64_t shift = y % w; // rotate amount wraps within width
        if (shift == 0)
            return x;
        // A right-rotate by `shift` is a left-rotate by (w - shift).
        std::uint64_t s = (o == op::rol) ? shift : static_cast<std::uint64_t>(w) - shift;
        return ((x & (m >> s)) << s) | (x >> (w - s));
    }
    }
    return 0; // unreachable with a valid op
}

/// Fixed-width binary string of `w` bits (MSB first). Formats the unsigned
/// normalized pattern directly: a width-64 pattern can exceed INT64_MAX and
/// must not round-trip through the signed path.
inline std::string to_bits(std::int64_t n, width w) {
    return format_u64(normalize(n, w), base::bin, w);
}

/// Indices of set bits (LSB = index 0), normalized to `w`, in ascending
/// order. The loop stops at the highest set bit.
inline std::vector<std::uint32_t> flags(std::int64_t n, width w) {
    std::uint64_t v = normalize(n, w);
    std::vector<std::uint32_t> out;
    std::uint32_t i = 0;
    while (v != 0) {
        if (v & 1)
            out.push_back(i);
        v >>= 1;
        ++i;
    }
    return out;
}

} // namespace bitwise