Managed

pub const Managed = struct {
    pub const sign_bit: usize = 1 << (@typeInfo(usize).int.bits - 1);

    /// Default number of limbs to allocate on creation of a `Managed`.
    pub const default_capacity = 4;

    /// Allocator used by the Managed when requesting memory.
    allocator: Allocator,

    /// Raw digits. These are:
    ///
    /// * Little-endian ordered
    /// * limbs.len >= 1
    /// * Zero is represent as Managed.len() == 1 with limbs[0] == 0.
    ///
    /// Accessing limbs directly should be avoided.
    limbs: []Limb,

    /// High bit is the sign bit. If set, Managed is negative, else Managed is positive.
    /// The remaining bits represent the number of limbs used by Managed.
    metadata: usize,

    /// Creates a new `Managed`. `default_capacity` limbs will be allocated immediately.
    /// The integer value after initializing is `0`.
    pub fn init(allocator: Allocator) !Managed {
        return initCapacity(allocator, default_capacity);
    }

    pub fn toMutable(self: Managed) Mutable {
        return .{
            .limbs = self.limbs,
            .positive = self.isPositive(),
            .len = self.len(),
        };
    }

    pub fn toConst(self: Managed) Const {
        return .{
            .limbs = self.limbs[0..self.len()],
            .positive = self.isPositive(),
        };
    }

    /// Creates a new `Managed` with value `value`.
    ///
    /// This is identical to an `init`, followed by a `set`.
    pub fn initSet(allocator: Allocator, value: anytype) !Managed {
        var s = try Managed.init(allocator);
        errdefer s.deinit();
        try s.set(value);
        return s;
    }

    /// Creates a new Managed with a specific capacity. If capacity < default_capacity then the
    /// default capacity will be used instead.
    /// The integer value after initializing is `0`.
    pub fn initCapacity(allocator: Allocator, capacity: usize) !Managed {
        return .{
            .allocator = allocator,
            .metadata = 1,
            .limbs = block: {
                const limbs = try allocator.alloc(Limb, @max(default_capacity, capacity));
                limbs[0] = 0;
                break :block limbs;
            },
        };
    }

    /// Returns the number of limbs currently in use.
    pub fn len(self: Managed) usize {
        return self.metadata & ~sign_bit;
    }

    /// Returns whether an Managed is positive.
    pub fn isPositive(self: Managed) bool {
        return self.metadata & sign_bit == 0;
    }

    /// Sets the sign of an Managed.
    pub fn setSign(self: *Managed, positive: bool) void {
        if (positive) {
            self.metadata &= ~sign_bit;
        } else {
            self.metadata |= sign_bit;
        }
    }

    /// Sets the length of an Managed.
    ///
    /// If setLen is used, then the Managed must be normalized to suit.
    pub fn setLen(self: *Managed, new_len: usize) void {
        self.metadata &= sign_bit;
        self.metadata |= new_len;
    }

    pub fn setMetadata(self: *Managed, positive: bool, length: usize) void {
        self.metadata = if (positive) length & ~sign_bit else length | sign_bit;
    }

    /// Ensures an Managed has enough space allocated for capacity limbs. If the Managed does not have
    /// sufficient capacity, the exact amount will be allocated. This occurs even if the requested
    /// capacity is only greater than the current capacity by one limb.
    pub fn ensureCapacity(self: *Managed, capacity: usize) !void {
        if (capacity <= self.limbs.len) {
            return;
        }
        self.limbs = try self.allocator.realloc(self.limbs, capacity);
    }

    /// Frees all associated memory.
    pub fn deinit(self: *Managed) void {
        self.allocator.free(self.limbs);
        self.* = undefined;
    }

    /// Returns a `Managed` with the same value. The returned `Managed` is a deep copy and
    /// can be modified separately from the original, and its resources are managed
    /// separately from the original.
    pub fn clone(other: Managed) !Managed {
        return other.cloneWithDifferentAllocator(other.allocator);
    }

    pub fn cloneWithDifferentAllocator(other: Managed, allocator: Allocator) !Managed {
        return .{
            .allocator = allocator,
            .metadata = other.metadata,
            .limbs = block: {
                const limbs = try allocator.alloc(Limb, other.len());
                @memcpy(limbs, other.limbs[0..other.len()]);
                break :block limbs;
            },
        };
    }

    /// Copies the value of the integer to an existing `Managed` so that they both have the same value.
    /// Extra memory will be allocated if the receiver does not have enough capacity.
    pub fn copy(self: *Managed, other: Const) !void {
        if (self.limbs.ptr == other.limbs.ptr) return;

        try self.ensureCapacity(other.limbs.len);
        @memcpy(self.limbs[0..other.limbs.len], other.limbs[0..other.limbs.len]);
        self.setMetadata(other.positive, other.limbs.len);
    }

    /// Efficiently swap a `Managed` with another. This swaps the limb pointers and a full copy is not
    /// performed. The address of the limbs field will not be the same after this function.
    pub fn swap(self: *Managed, other: *Managed) void {
        mem.swap(Managed, self, other);
    }

    /// Debugging tool: prints the state to stderr.
    pub fn dump(self: Managed) void {
        for (self.limbs[0..self.len()]) |limb| {
            std.debug.print("{x} ", .{limb});
        }
        std.debug.print("len={} capacity={} positive={}\n", .{ self.len(), self.limbs.len, self.isPositive() });
    }

    /// Negate the sign.
    pub fn negate(self: *Managed) void {
        self.metadata ^= sign_bit;
    }

    /// Make positive.
    pub fn abs(self: *Managed) void {
        self.metadata &= ~sign_bit;
    }

    pub fn isOdd(self: Managed) bool {
        return self.limbs[0] & 1 != 0;
    }

    pub fn isEven(self: Managed) bool {
        return !self.isOdd();
    }

    /// Returns the number of bits required to represent the absolute value of an integer.
    pub fn bitCountAbs(self: Managed) usize {
        return self.toConst().bitCountAbs();
    }

    /// Returns the number of bits required to represent the integer in twos-complement form.
    ///
    /// If the integer is negative the value returned is the number of bits needed by a signed
    /// integer to represent the value. If positive the value is the number of bits for an
    /// unsigned integer. Any unsigned integer will fit in the signed integer with bitcount
    /// one greater than the returned value.
    ///
    /// e.g. -127 returns 8 as it will fit in an i8. 127 returns 7 since it fits in a u7.
    pub fn bitCountTwosComp(self: Managed) usize {
        return self.toConst().bitCountTwosComp();
    }

    pub fn fitsInTwosComp(self: Managed, signedness: Signedness, bit_count: usize) bool {
        return self.toConst().fitsInTwosComp(signedness, bit_count);
    }

    /// Returns whether self can fit into an integer of the requested type.
    pub fn fits(self: Managed, comptime T: type) bool {
        return self.toConst().fits(T);
    }

    /// Returns the approximate size of the integer in the given base. Negative values accommodate for
    /// the minus sign. This is used for determining the number of characters needed to print the
    /// value. It is inexact and may exceed the given value by ~1-2 bytes.
    pub fn sizeInBaseUpperBound(self: Managed, base: usize) usize {
        return self.toConst().sizeInBaseUpperBound(base);
    }

    /// Sets an Managed to value. Value must be an primitive integer type.
    pub fn set(self: *Managed, value: anytype) Allocator.Error!void {
        try self.ensureCapacity(calcLimbLen(value));
        var m = self.toMutable();
        m.set(value);
        self.setMetadata(m.positive, m.len);
    }

    pub const ConvertError = Const.ConvertError;

    /// Convert `self` to `Int`.
    ///
    /// Returns an error if self cannot be narrowed into the requested type without truncation.
    pub fn toInt(self: Managed, comptime Int: type) ConvertError!Int {
        return self.toConst().toInt(Int);
    }

    /// Convert `self` to `Float`.
    pub fn toFloat(self: Managed, comptime Float: type, round: Round) struct { Float, Exactness } {
        return self.toConst().toFloat(Float, round);
    }

    /// Set self from the string representation `value`.
    ///
    /// `value` must contain only digits <= `base` and is case insensitive.  Base prefixes are
    /// not allowed (e.g. 0x43 should simply be 43).  Underscores in the input string are
    /// ignored and can be used as digit separators.
    ///
    /// Returns an error if memory could not be allocated or `value` has invalid digits for the
    /// requested base.
    ///
    /// self's allocator is used for temporary storage to boost multiplication performance.
    pub fn setString(self: *Managed, base: u8, value: []const u8) !void {
        if (base < 2 or base > 36) return error.InvalidBase;
        try self.ensureCapacity(calcSetStringLimbCount(base, value.len));
        var m = self.toMutable();
        try m.setString(base, value);
        self.setMetadata(m.positive, m.len);
    }

    /// Set self to either bound of a 2s-complement integer.
    /// Note: The result is still sign-magnitude, not twos complement! In order to convert the
    /// result to twos complement, it is sufficient to take the absolute value.
    pub fn setTwosCompIntLimit(
        r: *Managed,
        limit: TwosCompIntLimit,
        signedness: Signedness,
        bit_count: usize,
    ) !void {
        try r.ensureCapacity(calcTwosCompLimbCount(bit_count));
        var m = r.toMutable();
        m.setTwosCompIntLimit(limit, signedness, bit_count);
        r.setMetadata(m.positive, m.len);
    }

    /// Converts self to a string in the requested base. Memory is allocated from the provided
    /// allocator and not the one present in self.
    pub fn toString(self: Managed, allocator: Allocator, base: u8, case: std.fmt.Case) ![]u8 {
        if (base < 2 or base > 36) return error.InvalidBase;
        return self.toConst().toStringAlloc(allocator, base, case);
    }

    /// To allow `std.fmt.format` to work with `Managed`.
    pub fn format(self: Managed, w: *std.Io.Writer) std.Io.Writer.Error!void {
        return formatNumber(self, w, .{});
    }

    /// If the absolute value of integer is greater than or equal to `pow(2, 64 * @sizeOf(usize) * 8)`,
    /// this function will fail to print the string, printing "(BigInt)" instead of a number.
    /// This is because the rendering algorithm requires reversing a string, which requires O(N) memory.
    /// See `toString` and `toStringAlloc` for a way to print big integers without failure.
    pub fn formatNumber(self: Managed, w: *std.Io.Writer, n: std.fmt.Number) std.Io.Writer.Error!void {
        return self.toConst().formatNumber(w, n);
    }

    /// Returns math.Order.lt, math.Order.eq, math.Order.gt if |a| < |b|, |a| ==
    /// |b| or |a| > |b| respectively.
    pub fn orderAbs(a: Managed, b: Managed) math.Order {
        return a.toConst().orderAbs(b.toConst());
    }

    /// Returns math.Order.lt, math.Order.eq, math.Order.gt if a < b, a == b or a > b
    /// respectively.
    pub fn order(a: Managed, b: Managed) math.Order {
        return a.toConst().order(b.toConst());
    }

    /// Returns true if a == 0.
    pub fn eqlZero(a: Managed) bool {
        return a.toConst().eqlZero();
    }

    /// Returns true if |a| == |b|.
    pub fn eqlAbs(a: Managed, b: Managed) bool {
        return a.toConst().eqlAbs(b.toConst());
    }

    /// Returns true if a == b.
    pub fn eql(a: Managed, b: Managed) bool {
        return a.toConst().eql(b.toConst());
    }

    /// Normalize a possible sequence of leading zeros.
    ///
    /// [1, 2, 3, 4, 0] -> [1, 2, 3, 4]
    /// [1, 2, 0, 0, 0] -> [1, 2]
    /// [0, 0, 0, 0, 0] -> [0]
    pub fn normalize(r: *Managed, length: usize) void {
        assert(length > 0);
        assert(length <= r.limbs.len);

        var j = length;
        while (j > 0) : (j -= 1) {
            if (r.limbs[j - 1] != 0) {
                break;
            }
        }

        // Handle zero
        r.setLen(if (j != 0) j else 1);
    }

    /// r = a + scalar
    ///
    /// r and a may be aliases.
    ///
    /// Returns an error if memory could not be allocated.
    pub fn addScalar(r: *Managed, a: *const Managed, scalar: anytype) Allocator.Error!void {
        const needed = @max(a.len(), calcLimbLen(scalar)) + 1;
        const aliased = limbsAliasDistinct(r, a);
        try r.ensureAliasAwareCapacity(needed, aliased);
        var m = r.toMutable();
        m.addScalar(a.toConst(), scalar);
        r.setMetadata(m.positive, m.len);
    }

    /// r = a + b
    ///
    /// r, a and b may be aliases.
    ///
    /// Returns an error if memory could not be allocated.
    pub fn add(r: *Managed, a: *const Managed, b: *const Managed) Allocator.Error!void {
        const needed = @max(a.len(), b.len()) + 1;
        const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
        try r.ensureAliasAwareCapacity(needed, aliased);
        var m = r.toMutable();
        m.add(a.toConst(), b.toConst());
        r.setMetadata(m.positive, m.len);
    }

    /// r = a + b with 2s-complement wrapping semantics. Returns whether any overflow occurred.
    ///
    /// r, a and b may be aliases.
    ///
    /// Returns an error if memory could not be allocated.
    pub fn addWrap(
        r: *Managed,
        a: *const Managed,
        b: *const Managed,
        signedness: Signedness,
        bit_count: usize,
    ) Allocator.Error!bool {
        const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
        const needed = calcTwosCompLimbCount(bit_count);
        try r.ensureAliasAwareCapacity(needed, aliased);
        var m = r.toMutable();
        const wrapped = m.addWrap(a.toConst(), b.toConst(), signedness, bit_count);
        r.setMetadata(m.positive, m.len);
        return wrapped;
    }

    /// r = a + b with 2s-complement saturating semantics.
    ///
    /// r, a and b may be aliases.
    ///
    /// Returns an error if memory could not be allocated.
    pub fn addSat(r: *Managed, a: *const Managed, b: *const Managed, signedness: Signedness, bit_count: usize) Allocator.Error!void {
        const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
        const needed = calcTwosCompLimbCount(bit_count);
        try r.ensureAliasAwareCapacity(needed, aliased);
        var m = r.toMutable();
        m.addSat(a.toConst(), b.toConst(), signedness, bit_count);
        r.setMetadata(m.positive, m.len);
    }

    /// r = a - b
    ///
    /// r, a and b may be aliases.
    ///
    /// Returns an error if memory could not be allocated.
    pub fn sub(r: *Managed, a: *const Managed, b: *const Managed) !void {
        const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
        const needed = @max(a.len(), b.len()) + 1;
        try r.ensureAliasAwareCapacity(needed, aliased);
        var m = r.toMutable();
        m.sub(a.toConst(), b.toConst());
        r.setMetadata(m.positive, m.len);
    }

    /// r = a - b with 2s-complement wrapping semantics. Returns whether any overflow occurred.
    ///
    /// r, a and b may be aliases.
    ///
    /// Returns an error if memory could not be allocated.
    pub fn subWrap(
        r: *Managed,
        a: *const Managed,
        b: *const Managed,
        signedness: Signedness,
        bit_count: usize,
    ) Allocator.Error!bool {
        const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
        const needed = calcTwosCompLimbCount(bit_count);
        try r.ensureAliasAwareCapacity(needed, aliased);
        var m = r.toMutable();
        const wrapped = m.subWrap(a.toConst(), b.toConst(), signedness, bit_count);
        r.setMetadata(m.positive, m.len);
        return wrapped;
    }

    /// r = a - b with 2s-complement saturating semantics.
    ///
    /// r, a and b may be aliases.
    ///
    /// Returns an error if memory could not be allocated.
    pub fn subSat(
        r: *Managed,
        a: *const Managed,
        b: *const Managed,
        signedness: Signedness,
        bit_count: usize,
    ) Allocator.Error!void {
        const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
        const needed = calcTwosCompLimbCount(bit_count);
        try r.ensureAliasAwareCapacity(needed, aliased);
        var m = r.toMutable();
        m.subSat(a.toConst(), b.toConst(), signedness, bit_count);
        r.setMetadata(m.positive, m.len);
    }

    /// rma = a * b
    ///
    /// rma, a and b may be aliases. However, it is more efficient if rma does not alias a or b.
    ///
    /// Returns an error if memory could not be allocated.
    ///
    /// rma's allocator is used for temporary storage to speed up the multiplication.
    pub fn mul(rma: *Managed, a: *const Managed, b: *const Managed) !void {
        var alias_count: usize = 0;
        if (rma.limbs.ptr == a.limbs.ptr)
            alias_count += 1;
        if (rma.limbs.ptr == b.limbs.ptr)
            alias_count += 1;
        const needed = a.len() + b.len() + 1;
        const capacity_alias = limbsAliasDistinct(rma, a) or limbsAliasDistinct(rma, b);
        try rma.ensureAliasAwareCapacity(needed, capacity_alias);
        var m = rma.toMutable();
        if (alias_count == 0) {
            m.mulNoAlias(a.toConst(), b.toConst(), rma.allocator);
        } else {
            const limb_count = calcMulLimbsBufferLen(a.len(), b.len(), alias_count);
            const limbs_buffer = try rma.allocator.alloc(Limb, limb_count);
            defer rma.allocator.free(limbs_buffer);
            m.mul(a.toConst(), b.toConst(), limbs_buffer, rma.allocator);
        }
        rma.setMetadata(m.positive, m.len);
    }

    /// rma = a * b with 2s-complement wrapping semantics.
    ///
    /// rma, a and b may be aliases. However, it is more efficient if rma does not alias a or b.
    ///
    /// Returns an error if memory could not be allocated.
    ///
    /// rma's allocator is used for temporary storage to speed up the multiplication.
    pub fn mulWrap(
        rma: *Managed,
        a: *const Managed,
        b: *const Managed,
        signedness: Signedness,
        bit_count: usize,
    ) !void {
        var alias_count: usize = 0;
        if (rma.limbs.ptr == a.limbs.ptr)
            alias_count += 1;
        if (rma.limbs.ptr == b.limbs.ptr)
            alias_count += 1;
        const needed = calcTwosCompLimbCount(bit_count);
        const capacity_alias = limbsAliasDistinct(rma, a) or limbsAliasDistinct(rma, b);
        try rma.ensureAliasAwareCapacity(needed, capacity_alias);
        var m = rma.toMutable();
        if (alias_count == 0) {
            m.mulWrapNoAlias(a.toConst(), b.toConst(), signedness, bit_count, rma.allocator);
        } else {
            const limb_count = calcMulWrapLimbsBufferLen(bit_count, a.len(), b.len(), alias_count);
            const limbs_buffer = try rma.allocator.alloc(Limb, limb_count);
            defer rma.allocator.free(limbs_buffer);
            m.mulWrap(a.toConst(), b.toConst(), signedness, bit_count, limbs_buffer, rma.allocator);
        }
        rma.setMetadata(m.positive, m.len);
    }

    pub fn ensureTwosCompCapacity(r: *Managed, bit_count: usize) !void {
        try r.ensureCapacity(calcTwosCompLimbCount(bit_count));
    }

    /// True if two distinct `Managed` parameters share the same limbs buffer.
    ///
    /// We specifically exclude the case where `@intFromPtr(a) == @intFromPtr(b)` (same object).
    /// When both pointers refer to the same `Managed` instance, `ensureCapacity` can reallocate
    /// the buffer (if needed) without creating dangling pointers for that object.
    fn limbsAliasDistinct(a: *const Managed, b: *const Managed) bool {
        return @intFromPtr(a) != @intFromPtr(b) and a.limbs.ptr == b.limbs.ptr;
    }

    /// When `aliased` is false (including when both pointers refer to the same object),
    /// `ensureCapacity` may reallocate; callers who rely on distinct `Managed` instances
    /// aliasing must ensure capacity before aliasing.
    /// See https://github.com/ziglang/zig/issues/6167
    fn ensureAliasAwareCapacity(r: *Managed, needed: usize, aliased: bool) !void {
        if (aliased) {
            assert(needed <= r.limbs.len);
        } else {
            try r.ensureCapacity(needed);
        }
    }

    /// Use this function before doing `addScalar` if some of your parameters alias each other
    pub fn ensureAddScalarCapacity(r: *Managed, a: *const Managed, scalar: anytype) !void {
        try r.ensureCapacity(@max(a.len(), calcLimbLen(scalar)) + 1);
    }

    /// Use this function before doing `add` if some of your parameters alias each other
    pub fn ensureAddCapacity(r: *Managed, a: *const Managed, b: *const Managed) !void {
        try r.ensureCapacity(@max(a.len(), b.len()) + 1);
    }

    /// Use this function before doing `mul` if some of your parameters alias each other
    pub fn ensureMulCapacity(rma: *Managed, a: *const Managed, b: *const Managed) !void {
        try rma.ensureCapacity(a.len() + b.len() + 1);
    }

    /// q = a / b (rem r)
    ///
    /// a / b are floored (rounded towards 0).
    ///
    /// Returns an error if memory could not be allocated.
    pub fn divFloor(q: *Managed, r: *Managed, a: *const Managed, b: *const Managed) !void {
        const q_alias = limbsAliasDistinct(q, a) or limbsAliasDistinct(q, b);
        const r_alias = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
        try q.ensureAliasAwareCapacity(a.len(), q_alias);
        try r.ensureAliasAwareCapacity(b.len(), r_alias);
        var mq = q.toMutable();
        var mr = r.toMutable();
        const limbs_buffer = try q.allocator.alloc(Limb, calcDivLimbsBufferLen(a.len(), b.len()));
        defer q.allocator.free(limbs_buffer);
        mq.divFloor(&mr, a.toConst(), b.toConst(), limbs_buffer);
        q.setMetadata(mq.positive, mq.len);
        r.setMetadata(mr.positive, mr.len);
    }

    /// q = a / b (rem r)
    ///
    /// a / b are ceiled (rounded towards positive infinity).
    ///
    /// Returns an error if memory could not be allocated.
    pub fn divCeil(q: *Managed, r: *Managed, a: *const Managed, b: *const Managed) !void {
        const q_alias = limbsAliasDistinct(q, a) or limbsAliasDistinct(q, b);
        const r_alias = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
        try q.ensureAliasAwareCapacity(a.len(), q_alias);
        try r.ensureAliasAwareCapacity(b.len(), r_alias);
        var mq = q.toMutable();
        var mr = r.toMutable();
        const limbs_buffer = try q.allocator.alloc(Limb, calcDivLimbsBufferLen(a.len(), b.len()));
        defer q.allocator.free(limbs_buffer);
        mq.divCeil(&mr, a.toConst(), b.toConst(), limbs_buffer);
        q.setMetadata(mq.positive, mq.len);
        r.setMetadata(mr.positive, mr.len);
    }

    /// q = a / b (rem r)
    ///
    /// a / b are truncated (rounded towards -inf).
    ///
    /// Returns an error if memory could not be allocated.
    pub fn divTrunc(q: *Managed, r: *Managed, a: *const Managed, b: *const Managed) !void {
        const q_alias = limbsAliasDistinct(q, a) or limbsAliasDistinct(q, b);
        const r_alias = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
        try q.ensureAliasAwareCapacity(a.len(), q_alias);
        try r.ensureAliasAwareCapacity(b.len(), r_alias);
        var mq = q.toMutable();
        var mr = r.toMutable();
        const limbs_buffer = try q.allocator.alloc(Limb, calcDivLimbsBufferLen(a.len(), b.len()));
        defer q.allocator.free(limbs_buffer);
        mq.divTrunc(&mr, a.toConst(), b.toConst(), limbs_buffer);
        q.setMetadata(mq.positive, mq.len);
        r.setMetadata(mr.positive, mr.len);
    }

    /// r = a << shift, in other words, r = a * 2^shift
    /// r and a may alias.
    pub fn shiftLeft(r: *Managed, a: *const Managed, shift: usize) !void {
        const aliased = limbsAliasDistinct(r, a);
        const needed = a.len() + (shift / limb_bits) + 1;
        try r.ensureAliasAwareCapacity(needed, aliased);
        var m = r.toMutable();
        m.shiftLeft(a.toConst(), shift);
        r.setMetadata(m.positive, m.len);
    }

    /// r = a <<| shift with 2s-complement saturating semantics.
    /// r and a may alias.
    pub fn shiftLeftSat(r: *Managed, a: *const Managed, shift: usize, signedness: Signedness, bit_count: usize) !void {
        const aliased = limbsAliasDistinct(r, a);
        const needed = calcTwosCompLimbCount(bit_count);
        try r.ensureAliasAwareCapacity(needed, aliased);
        var m = r.toMutable();
        m.shiftLeftSat(a.toConst(), shift, signedness, bit_count);
        r.setMetadata(m.positive, m.len);
    }

    /// r = a >> shift
    /// r and a may alias.
    pub fn shiftRight(r: *Managed, a: *const Managed, shift: usize) !void {
        if (a.len() <= shift / limb_bits) {
            // Shifting negative numbers converges to -1 instead of 0
            if (a.isPositive()) {
                r.metadata = 1;
                r.limbs[0] = 0;
            } else {
                r.metadata = 1;
                r.setSign(false);
                r.limbs[0] = 1;
            }
            return;
        }

        const aliased = limbsAliasDistinct(r, a);
        const needed = a.len() - (shift / limb_bits);
        try r.ensureAliasAwareCapacity(needed, aliased);
        var m = r.toMutable();
        m.shiftRight(a.toConst(), shift);
        r.setMetadata(m.positive, m.len);
    }

    /// r = ~a under 2s-complement wrapping semantics.
    /// r and a may alias.
    pub fn bitNotWrap(r: *Managed, a: *const Managed, signedness: Signedness, bit_count: usize) !void {
        const aliased = limbsAliasDistinct(r, a);
        const needed = calcTwosCompLimbCount(bit_count);
        try r.ensureAliasAwareCapacity(needed, aliased);
        var m = r.toMutable();
        m.bitNotWrap(a.toConst(), signedness, bit_count);
        r.setMetadata(m.positive, m.len);
    }

    /// r = a | b
    ///
    /// a and b are zero-extended to the longer of a or b.
    pub fn bitOr(r: *Managed, a: *const Managed, b: *const Managed) !void {
        const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
        const needed = @max(a.len(), b.len());
        try r.ensureAliasAwareCapacity(needed, aliased);
        var m = r.toMutable();
        m.bitOr(a.toConst(), b.toConst());
        r.setMetadata(m.positive, m.len);
    }

    /// r = a & b
    pub fn bitAnd(r: *Managed, a: *const Managed, b: *const Managed) !void {
        const cap = if (a.len() >= b.len())
            if (b.isPositive()) b.len() else if (a.isPositive()) a.len() else a.len() + 1
        else if (a.isPositive()) a.len() else if (b.isPositive()) b.len() else b.len() + 1;

        const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
        try r.ensureAliasAwareCapacity(cap, aliased);
        var m = r.toMutable();
        m.bitAnd(a.toConst(), b.toConst());
        r.setMetadata(m.positive, m.len);
    }

    /// r = a ^ b
    pub fn bitXor(r: *Managed, a: *const Managed, b: *const Managed) !void {
        const cap = @max(a.len(), b.len()) + @intFromBool(a.isPositive() != b.isPositive());
        const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
        try r.ensureAliasAwareCapacity(cap, aliased);

        var m = r.toMutable();
        m.bitXor(a.toConst(), b.toConst());
        r.setMetadata(m.positive, m.len);
    }

    /// rma may alias x or y.
    /// x and y may alias each other.
    ///
    /// rma's allocator is used for temporary storage to boost multiplication performance.
    pub fn gcd(rma: *Managed, x: *const Managed, y: *const Managed) !void {
        const aliased = limbsAliasDistinct(rma, x) or limbsAliasDistinct(rma, y);
        const needed = @min(x.len(), y.len());
        try rma.ensureAliasAwareCapacity(needed, aliased);
        var m = rma.toMutable();
        var limbs_buffer = std.array_list.Managed(Limb).init(rma.allocator);
        defer limbs_buffer.deinit();
        try m.gcd(x.toConst(), y.toConst(), &limbs_buffer);
        rma.setMetadata(m.positive, m.len);
    }

    /// r = a * a
    pub fn sqr(rma: *Managed, a: *const Managed) !void {
        const needed_limbs = 2 * a.len() + 1;
        const capacity_alias = limbsAliasDistinct(rma, a);
        const same_buffer = rma.limbs.ptr == a.limbs.ptr;
        try rma.ensureAliasAwareCapacity(needed_limbs, capacity_alias);

        if (same_buffer) {
            const a_len = a.len();
            const tmp = try rma.allocator.alloc(Limb, a_len);
            defer rma.allocator.free(tmp);
            @memcpy(tmp[0..a_len], a.limbs[0..a_len]);
            const a_const: Const = .{ .limbs = tmp[0..a_len], .positive = a.isPositive() };
            var rma_mut = rma.toMutable();
            rma_mut.sqrNoAlias(a_const, rma.allocator);
            rma.setMetadata(rma_mut.positive, rma_mut.len);
        } else {
            var rma_mut = rma.toMutable();
            rma_mut.sqrNoAlias(a.toConst(), rma.allocator);
            rma.setMetadata(rma_mut.positive, rma_mut.len);
        }
    }

    pub fn pow(rma: *Managed, a: *const Managed, b: u32) !void {
        const needed_limbs = calcPowLimbsBufferLen(a.bitCountAbs(), b);
        const capacity_alias = limbsAliasDistinct(rma, a);
        const same_buffer = rma.limbs.ptr == a.limbs.ptr;

        try rma.ensureAliasAwareCapacity(needed_limbs, capacity_alias);
        const limbs_buffer = try rma.allocator.alloc(Limb, needed_limbs);
        defer rma.allocator.free(limbs_buffer);

        if (same_buffer) {
            const a_len = a.len();
            const tmp = try rma.allocator.alloc(Limb, a_len);
            defer rma.allocator.free(tmp);
            @memcpy(tmp[0..a_len], a.limbs[0..a_len]);
            const a_const: Const = .{ .limbs = tmp[0..a_len], .positive = a.isPositive() };
            var rma_mut = rma.toMutable();
            rma_mut.pow(a_const, b, limbs_buffer);
            rma.setMetadata(rma_mut.positive, rma_mut.len);
        } else {
            var rma_mut = rma.toMutable();
            rma_mut.pow(a.toConst(), b, limbs_buffer);
            rma.setMetadata(rma_mut.positive, rma_mut.len);
        }
    }

    /// r = ⌊√a⌋
    pub fn sqrt(rma: *Managed, a: *const Managed) !void {
        const bit_count = a.bitCountAbs();
        const aliased = limbsAliasDistinct(rma, a);

        if (bit_count == 0) {
            try rma.set(0);
            rma.setMetadata(a.isPositive(), rma.len());
            return;
        }

        if (!a.isPositive()) {
            return error.SqrtOfNegativeNumber;
        }

        const needed_limbs = calcSqrtLimbsBufferLen(bit_count);
        const limbs_buffer = try rma.allocator.alloc(Limb, needed_limbs);
        defer rma.allocator.free(limbs_buffer);

        const needed = (a.len() - 1) / 2 + 1;
        try rma.ensureAliasAwareCapacity(needed, aliased);
        var m = rma.toMutable();
        m.sqrt(a.toConst(), limbs_buffer);
        rma.setMetadata(m.positive, m.len);
    }

    /// r = truncate(Int(signedness, bit_count), a)
    pub fn truncate(r: *Managed, a: *const Managed, signedness: Signedness, bit_count: usize) !void {
        const aliased = limbsAliasDistinct(r, a);
        const needed = calcTwosCompLimbCount(bit_count);
        try r.ensureAliasAwareCapacity(needed, aliased);
        var m = r.toMutable();
        m.truncate(a.toConst(), signedness, bit_count);
        r.setMetadata(m.positive, m.len);
    }

    /// r = saturate(Int(signedness, bit_count), a)
    pub fn saturate(r: *Managed, a: *const Managed, signedness: Signedness, bit_count: usize) !void {
        const aliased = limbsAliasDistinct(r, a);
        const needed = calcTwosCompLimbCount(bit_count);
        try r.ensureAliasAwareCapacity(needed, aliased);
        var m = r.toMutable();
        m.saturate(a.toConst(), signedness, bit_count);
        r.setMetadata(m.positive, m.len);
    }

    /// r = @popCount(a) with 2s-complement semantics.
    /// r and a may be aliases.
    pub fn popCount(r: *Managed, a: *const Managed, bit_count: usize) !void {
        const aliased = limbsAliasDistinct(r, a);
        const needed = calcTwosCompLimbCount(bit_count);
        try r.ensureAliasAwareCapacity(needed, aliased);
        var m = r.toMutable();
        m.popCount(a.toConst(), bit_count);
        r.setMetadata(m.positive, m.len);
    }
}