llvm-native-core 0.1.16

//! APInt — Arbitrary Precision Integers
//!
//! Clean-room implementation based on standard algorithms from computer science
//! literature (Knuth, Hacker's Delight, etc.). No LLVM source code was consulted.
//!
//! APInt represents fixed-width integer values. The bit width is fixed at
//! construction time and determines the range. All arithmetic operations are
//! wrapping (modulo 2^bit_width). Signed operations follow C99 truncation-toward-zero
//! semantics.

use std::cmp::Ordering;
use std::fmt;
use std::hash::{Hash, Hasher};
use std::ops::{Add, BitAnd, BitOr, BitXor, Mul, Neg, Not, Shl, Shr, Sub};

// ---------------------------------------------------------------------------
// APInt struct
// ---------------------------------------------------------------------------

/// Arbitrary-precision integer with a fixed bit width (≥ 1).
///
/// The value is stored as a little-endian array of 64-bit words.
/// Only `ceil(bit_width / 64)` words are allocated; unused high bits
/// in the last word are guaranteed to be zero after any public operation.
#[derive(Clone)]
pub struct APInt {
    /// Bit width of this integer (≥ 1).
    bit_width: u32,
    /// Value stored as little-endian 64-bit words.
    /// For bit_width ≤ 64, a single word is used; for wider widths,
    /// additional words hold the higher-order bits.
    words: Vec<u64>,
}

// ---------------------------------------------------------------------------
// Internal helpers (free functions)
// ---------------------------------------------------------------------------

/// Number of u64 words needed for `bit_width` bits.
#[inline]
fn num_words(bit_width: u32) -> usize {
    debug_assert!(bit_width >= 1, "bit_width must be >= 1");
    ((bit_width as usize + 63) / 64).max(1)
}

/// Create a mask for the valid bits in the last word.
/// Returns `!0u64` when bit_width is a multiple of 64 (all bits valid).
#[inline]
fn last_word_mask(bit_width: u32) -> u64 {
    let bits_in_last = bit_width % 64;
    if bits_in_last == 0 {
        u64::MAX
    } else {
        (1u64 << bits_in_last) - 1
    }
}

/// Number of unused high bits in the last word.
#[inline]
fn excess_bits(bit_width: u32) -> u32 {
    let rem = bit_width % 64;
    if rem == 0 {
        0
    } else {
        64 - rem
    }
}

// ---------------------------------------------------------------------------
// Word-level arithmetic primitives
// ---------------------------------------------------------------------------

/// Add two same-length word slices with optional carry-in.
/// Returns (result_words, carry_out).
fn add_words(a: &[u64], b: &[u64]) -> (Vec<u64>, bool) {
    let n = a.len().max(b.len());
    let mut result = vec![0u64; n];
    let mut carry = false;
    for i in 0..n {
        let av = a.get(i).copied().unwrap_or(0);
        let bv = b.get(i).copied().unwrap_or(0);
        let (sum1, c1) = av.overflowing_add(bv);
        let (sum2, c2) = sum1.overflowing_add(carry as u64);
        result[i] = sum2;
        carry = c1 || c2;
    }
    (result, carry)
}

/// Subtract `b` from `a` (same-length word slices) with optional borrow-in.
/// Returns (result_words, borrow_out).
fn sub_words(a: &[u64], b: &[u64]) -> (Vec<u64>, bool) {
    let n = a.len().max(b.len());
    let mut result = vec![0u64; n];
    let mut borrow = false;
    for i in 0..n {
        let av = a.get(i).copied().unwrap_or(0);
        let bv = b.get(i).copied().unwrap_or(0);
        let (diff1, b1) = av.overflowing_sub(bv);
        let (diff2, b2) = diff1.overflowing_sub(borrow as u64);
        result[i] = diff2;
        borrow = b1 || b2;
    }
    (result, borrow)
}

/// Multiply two word slices.  The result has length `a.len() + b.len()`.
fn mul_words(a: &[u64], b: &[u64]) -> Vec<u64> {
    let n = a.len() + b.len();
    let mut result = vec![0u64; n];
    for i in 0..a.len() {
        let mut carry: u64 = 0;
        for j in 0..b.len() {
            let product =
                (a[i] as u128) * (b[j] as u128) + (result[i + j] as u128) + (carry as u128);
            result[i + j] = product as u64;
            carry = (product >> 64) as u64;
        }
        result[i + b.len()] = carry;
    }
    result
}

/// Divide `dividend` (little-endian words) by a single-word `divisor`.
/// Returns `(quotient_words, remainder)`.
fn div_rem_single(dividend: &[u64], divisor: u64) -> (Vec<u64>, u64) {
    let mut quotient = vec![0u64; dividend.len()];
    let mut remainder: u64 = 0;
    for i in (0..dividend.len()).rev() {
        let d = ((remainder as u128) << 64) | (dividend[i] as u128);
        quotient[i] = (d / divisor as u128) as u64;
        remainder = (d % divisor as u128) as u64;
    }
    (quotient, remainder)
}

/// Divide two multi-word numbers (little-endian words).
/// `n` = dividend, `d` = divisor.  Both are normalized (no leading zeros).
/// Returns `(quotient, remainder)` where quotient and remainder have the same
/// length as `n`.  Panics if divisor is zero.
fn div_rem_multi(n: &[u64], d: &[u64]) -> (Vec<u64>, Vec<u64>) {
    // Assert divisor is not zero.
    debug_assert!(!d.iter().all(|&w| w == 0), "division by zero");
    let m = n.len();
    // If divisor is single-word, use fast path.
    let d_nwords = d.iter().rposition(|&w| w != 0).map(|i| i + 1).unwrap_or(0);
    if d_nwords <= 1 {
        let divisor = if d_nwords == 0 { 0 } else { d[0] };
        if divisor == 1 {
            return (n.to_vec(), vec![0u64; m]);
        }
        let (q, r) = div_rem_single(n, divisor);
        let mut rem = vec![0u64; m];
        rem[0] = r;
        return (q, rem);
    }

    // Multi-word division using binary long division (shift-subtract).
    // This is O(n^2) but correct for all sizes.
    let mut remainder = n.to_vec();
    let mut quotient = vec![0u64; m];

    // Total significant bits of dividend and divisor.
    let n_bits = significant_bits(n);
    let d_bits = significant_bits(d);

    if n_bits < d_bits {
        return (quotient, remainder);
    }

    // We work bit-by-bit from most significant to least.
    let shift = n_bits - d_bits;
    // For each bit position from shift down to 0:
    for pos in (0..=shift).rev() {
        // Left-shift divisor by `pos` bits (logically) and compare/subtract.
        if cmp_shifted(&remainder, d, pos) != Ordering::Less {
            sub_shifted(&mut remainder, d, pos);
            // Set bit `pos` in quotient.
            let word_idx = (pos as usize) / 64;
            let bit_idx = (pos as usize) % 64;
            quotient[word_idx] |= 1u64 << bit_idx;
        }
    }

    (quotient, remainder)
}

/// Compare `a` against `b` left-shifted by `shift` bits.
fn cmp_shifted(a: &[u64], b: &[u64], shift: usize) -> Ordering {
    let word_shift = shift / 64;
    let bit_shift = (shift % 64) as u32;

    // We compare starting from the most significant possible word.
    let a_bits = significant_bits(a);
    let b_bits = significant_bits(b);
    let b_shifted_bits = b_bits + shift;

    if a_bits > b_shifted_bits {
        return Ordering::Greater;
    }
    if a_bits < b_shifted_bits {
        return Ordering::Less;
    }

    // Same bit length; compare word by word from high to low.
    let max_word = (b_shifted_bits + 63) / 64;
    for i in (0..max_word).rev() {
        let a_word = a.get(i).copied().unwrap_or(0);
        let b_word = get_shifted_word(b, i, word_shift, bit_shift);
        match a_word.cmp(&b_word) {
            Ordering::Equal => continue,
            ord => return ord,
        }
    }
    Ordering::Equal
}

/// Get the word at logical index `i` from `b` left-shifted by `(word_shift, bit_shift)`.
fn get_shifted_word(b: &[u64], i: usize, word_shift: usize, bit_shift: u32) -> u64 {
    let lo_idx = i.wrapping_sub(word_shift);
    let hi_idx = lo_idx.wrapping_sub(1);
    let lo = b.get(lo_idx).copied().unwrap_or(0);
    let hi = if lo_idx == 0 {
        0
    } else {
        b.get(hi_idx).copied().unwrap_or(0)
    };

    if bit_shift == 0 {
        lo
    } else {
        (lo << bit_shift) | (hi >> (64 - bit_shift))
    }
}

/// Subtract `b << shift` from `a` (in-place).
fn sub_shifted(a: &mut [u64], b: &[u64], shift: usize) {
    let word_shift = shift / 64;
    let bit_shift = (shift % 64) as u32;
    let mut borrow: u64 = 0;

    for i in 0..a.len() {
        let b_word = get_shifted_word(b, i, word_shift, bit_shift);
        let (diff1, b1) = a[i].overflowing_sub(b_word);
        let (diff2, b2) = diff1.overflowing_sub(borrow);
        a[i] = diff2;
        borrow = (b1 as u64) + (b2 as u64);
    }
}

/// Count significant bits (position of highest set bit + 1) in a word slice.
fn significant_bits(words: &[u64]) -> usize {
    for i in (0..words.len()).rev() {
        if words[i] != 0 {
            return i * 64 + 64 - words[i].leading_zeros() as usize;
        }
    }
    0
}

// ---------------------------------------------------------------------------
// Construction
// ---------------------------------------------------------------------------

impl APInt {
    /// Create an APInt from a u64 value.
    ///
    /// If `is_signed` is true, the u64 is interpreted as a signed 64-bit value
    /// and sign-extended to `bit_width`.  If false, it is zero-extended.
    ///
    /// # Panics
    /// Panics if `bit_width` is zero.
    pub fn new(bit_width: u32, val: u64, is_signed: bool) -> Self {
        assert!(bit_width >= 1, "APInt::new: bit_width must be >= 1, got 0");
        let nw = num_words(bit_width);
        let mut words = vec![0u64; nw];
        words[0] = val;

        if is_signed && (val >> 63) != 0 {
            // Sign-extend: fill all upper words with 1s.
            for w in words.iter_mut().skip(1) {
                *w = u64::MAX;
            }
        }

        let mut result = APInt { bit_width, words };
        result.clear_unused_bits();
        result.normalize();
        result
    }

    /// Returns the bit width of this integer.
    pub fn bit_width(&self) -> u32 {
        self.bit_width
    }

    /// Create an APInt from a single u64 (zero-extended).
    /// Create from a u64 value (zero-extended to `bit_width`).
    ///
    /// # Panics
    /// Panics if `bit_width` is zero.
    pub fn from_u64(bit_width: u32, val: u64) -> Self {
        Self::new(bit_width, val, false)
    }

    /// Create from an i64 value (sign-extended to `bit_width`).
    ///
    /// # Panics
    /// Panics if `bit_width` is zero.
    pub fn from_i64(bit_width: u32, val: i64) -> Self {
        Self::new(bit_width, val as u64, true)
    }

    /// Create an APInt representing zero.
    pub fn get_zero(bit_width: u32) -> Self {
        Self::new(bit_width, 0, false)
    }

    /// Create an APInt representing one.
    pub fn get_one(bit_width: u32) -> Self {
        Self::new(bit_width, 1, false)
    }

    /// Create an APInt with all bits set (the maximum unsigned value).
    pub fn get_all_ones(bit_width: u32) -> Self {
        assert!(bit_width >= 1, "get_all_ones: bit_width must be >= 1");
        let nw = num_words(bit_width);
        let mut words = vec![u64::MAX; nw];
        let mask = last_word_mask(bit_width);
        if let Some(last) = words.last_mut() {
            *last &= mask;
        }
        APInt { bit_width, words }
    }

    /// Create the maximum unsigned value for the given width.
    pub fn get_max_value(bit_width: u32) -> Self {
        Self::get_all_ones(bit_width)
    }

    /// Create the minimum unsigned value (zero).
    pub fn get_min_value(bit_width: u32) -> Self {
        Self::get_zero(bit_width)
    }

    /// Create the maximum signed value: `2^(bit_width-1) - 1`.
    pub fn get_signed_max_value(bit_width: u32) -> Self {
        assert!(bit_width >= 1);
        let mut result = Self::get_all_ones(bit_width);
        // Clear the sign bit.
        if let Some(w) = result.words.last_mut() {
            let sign_bit_pos = (bit_width - 1) % 64;
            *w &= !(1u64 << sign_bit_pos);
        }
        result.clear_unused_bits();
        result
    }

    /// Create the minimum signed value: `-2^(bit_width-1)`.
    pub fn get_signed_min_value(bit_width: u32) -> Self {
        assert!(bit_width >= 1);
        let nw = num_words(bit_width);
        let mut words = vec![0u64; nw];
        // Set only the sign bit.
        let sign_word = ((bit_width - 1) / 64) as usize;
        let sign_bit = (bit_width - 1) % 64;
        words[sign_word] = 1u64 << sign_bit;
        APInt { bit_width, words }
    }

    /// Parse a string in the given radix.
    ///
    /// Supported radices: 2, 8, 10, 16.  Radix 0 means auto-detect from prefix:
    /// - `0x` / `0X` → 16
    /// - `0b` / `0B` → 2
    /// - `0o` / `0O` → 8
    /// - otherwise → 10
    ///
    /// The result has a bit width large enough to hold the parsed value without
    /// truncation.  If the string is empty or contains invalid digits, an error
    /// is returned.
    pub fn from_string(s: &str, radix: u8) -> Result<Self, String> {
        let s = s.trim();
        if s.is_empty() {
            return Err("empty string".to_string());
        }

        // Detect radix from prefix.
        let (radix, digits) = detect_radix_and_strip(s, radix)?;

        if digits.is_empty() {
            return Err("no digits after prefix".to_string());
        }

        // Parse each digit, building up the value.
        // We'll use repeated multiplication by radix and addition.
        // Start with a reasonable initial width and grow as needed.
        let bits_per_digit = radix.ilog2().max(1);
        let initial_width = (digits.len() as u32 * bits_per_digit).max(1);
        let nw = num_words(initial_width);
        let mut result = APInt {
            bit_width: initial_width,
            words: vec![0u64; nw],
        };

        for &b in digits.as_bytes() {
            let digit = match b {
                b'0'..=b'9' => (b - b'0') as u64,
                b'a'..=b'f' => (b - b'a' + 10) as u64,
                b'A'..=b'F' => (b - b'A' + 10) as u64,
                _ => return Err(format!("invalid digit '{}' for radix {}", b as char, radix)),
            };
            if digit >= radix as u64 {
                return Err(format!(
                    "digit '{}' out of range for radix {}",
                    b as char, radix
                ));
            }

            // result = result * radix + digit
            result = mul_by_scalar(&result, radix as u64);
            result = add_scalar(&result, digit);
        }

        // Trim result to minimal bit width.
        let actual_bits = result.active_bits();
        let new_width = (actual_bits as u32).max(1);
        if new_width < result.bit_width {
            result = result.trunc(new_width);
        }

        Ok(result)
    }

    /// Create from little-endian bytes.  The bytes are interpreted as an
    /// unsigned value and zero-extended or truncated to `bit_width`.
    pub fn from_bytes_le(bytes: &[u8], bit_width: u32) -> Self {
        assert!(bit_width >= 1);
        let nw = num_words(bit_width);
        let mut words = vec![0u64; nw];
        for (i, chunk) in bytes.chunks(8).enumerate() {
            if i >= nw {
                break;
            }
            let mut val: u64 = 0;
            for (j, &b) in chunk.iter().enumerate() {
                val |= (b as u64) << (j * 8);
            }
            words[i] = val;
        }
        let mut result = APInt { bit_width, words };
        result.clear_unused_bits();
        result
    }

    /// Create from big-endian bytes.  The bytes are interpreted as an
    /// unsigned value and zero-extended or truncated to `bit_width`.
    pub fn from_bytes_be(bytes: &[u8], bit_width: u32) -> Self {
        assert!(bit_width >= 1);
        let nw = num_words(bit_width);
        let mut words = vec![0u64; nw];
        for (chunk_idx, chunk) in bytes.rchunks(8).enumerate() {
            if chunk_idx >= nw {
                break;
            }
            let mut val: u64 = 0;
            for (j, &b) in chunk.iter().rev().enumerate() {
                val |= (b as u64) << (j * 8);
            }
            // chunk_idx 0 is the least significant chunk (LE word 0).
            words[chunk_idx] = val;
        }
        let mut result = APInt { bit_width, words };
        result.clear_unused_bits();
        result
    }

    /// Zero out any bits beyond `bit_width` in the highest word.
    pub fn clear_unused_bits(&mut self) {
        if self.words.is_empty() {
            self.words.push(0);
            return;
        }
        let mask = last_word_mask(self.bit_width);
        let last = self.words.last_mut().unwrap();
        *last &= mask;
    }

    // -----------------------------------------------------------------------
    // Internal constructors / helpers
    // -----------------------------------------------------------------------

    /// Create from a vector of words without checking bit width.
    /// Used internally when the width is known to be correct.
    pub(crate) fn from_words(bit_width: u32, words: Vec<u64>) -> Self {
        let mut result = APInt { bit_width, words };
        result.normalize();
        result.clear_unused_bits();
        result
    }

    /// Remove leading (high-order) zero words beyond the minimum required
    /// by `bit_width`.  Does not change `bit_width`.
    pub(crate) fn normalize(&mut self) {
        let needed = num_words(self.bit_width);
        // Strip excess zero words from the high end.
        while self.words.len() > needed && self.words.last() == Some(&0) {
            self.words.pop();
        }
        // Ensure minimum word count is maintained.
        while self.words.len() < needed {
            self.words.push(0);
        }
    }

    /// Panic if `self.bit_width != other.bit_width`.
    fn ensure_width_compatible(&self, other: &APInt) {
        if self.bit_width != other.bit_width {
            panic!(
                "APInt bit width mismatch: {} vs {}",
                self.bit_width, other.bit_width
            );
        }
    }

    /// Get the number of significant bits (position of MSB + 1).
    pub fn get_active_bits(&self) -> usize {
        significant_bits(&self.words)
    }

    fn active_bits(&self) -> usize {
        significant_bits(&self.words)
    }
}

// ---------------------------------------------------------------------------
// Internal scalar operations (used by from_string, sqrt, etc.)
// ---------------------------------------------------------------------------

/// Multiply an APInt by a scalar u64, returning a new APInt (may grow width).
fn mul_by_scalar(a: &APInt, scalar: u64) -> APInt {
    if scalar == 0 {
        return APInt::get_zero(a.bit_width);
    }
    if scalar == 1 {
        return a.clone();
    }
    let mut result_words = vec![0u64; a.words.len() + 1];
    let mut carry: u64 = 0;
    for (i, &w) in a.words.iter().enumerate() {
        let product = (w as u128) * (scalar as u128) + (carry as u128);
        result_words[i] = product as u64;
        carry = (product >> 64) as u64;
    }
    result_words[a.words.len()] = carry;
    let new_width = if carry != 0 {
        a.bit_width + 64
    } else {
        a.bit_width
    };
    let mut result = APInt {
        bit_width: new_width,
        words: result_words,
    };
    result.normalize();
    result
}

/// Add a scalar u64 to an APInt, returning a new APInt (may grow width).
fn add_scalar(a: &APInt, scalar: u64) -> APInt {
    if scalar == 0 {
        return a.clone();
    }
    let mut result_words = a.words.clone();
    let mut carry = scalar as u128;
    for w in result_words.iter_mut() {
        let sum = (*w as u128) + carry;
        *w = sum as u64;
        carry = sum >> 64;
        if carry == 0 {
            break;
        }
    }
    if carry != 0 {
        result_words.push(carry as u64);
    }
    let new_width = (result_words.len() * 64) as u32;
    let mut result = APInt {
        bit_width: new_width.max(a.bit_width),
        words: result_words,
    };
    result.normalize();
    result
}

/// Detect radix from string prefix and strip it.
/// Returns `(radix, remaining_digits)`.
fn detect_radix_and_strip<'a>(s: &'a str, radix: u8) -> Result<(u8, &'a str), String> {
    let lower = s.to_ascii_lowercase();
    if radix == 0 {
        // Auto-detect.
        if let Some(rest) = lower.strip_prefix("0x") {
            if rest.is_empty() {
                return Err("no digits after 0x".to_string());
            }
            return Ok((16, &s[2..]));
        }
        if let Some(rest) = lower.strip_prefix("0b") {
            if rest.is_empty() {
                return Err("no digits after 0b".to_string());
            }
            return Ok((2, &s[2..]));
        }
        if let Some(rest) = lower.strip_prefix("0o") {
            if rest.is_empty() {
                return Err("no digits after 0o".to_string());
            }
            return Ok((8, &s[2..]));
        }
        Ok((10, s))
    } else {
        // Strip known prefix regardless.
        if radix == 16 {
            if lower.strip_prefix("0x").is_some() {
                return Ok((16, &s[2..]));
            }
        }
        if radix == 2 {
            if lower.strip_prefix("0b").is_some() {
                return Ok((2, &s[2..]));
            }
        }
        if radix == 8 {
            if lower.strip_prefix("0o").is_some() {
                return Ok((8, &s[2..]));
            }
        }
        if radix != 2 && radix != 8 && radix != 10 && radix != 16 {
            return Err(format!("unsupported radix: {}", radix));
        }
        Ok((radix, s))
    }
}

// ---------------------------------------------------------------------------
// Arithmetic operations
// ---------------------------------------------------------------------------

impl APInt {
    /// Wrapping addition (modulo 2^bit_width).
    pub fn add(&self, other: &APInt) -> APInt {
        self.ensure_width_compatible(other);
        let (words, _carry) = add_words(&self.words, &other.words);
        APInt::from_words(self.bit_width, words)
    }

    /// Wrapping subtraction (modulo 2^bit_width).
    pub fn sub(&self, other: &APInt) -> APInt {
        self.ensure_width_compatible(other);
        let (words, _borrow) = sub_words(&self.words, &other.words);
        APInt::from_words(self.bit_width, words)
    }

    /// Wrapping multiplication (modulo 2^bit_width).
    pub fn mul(&self, other: &APInt) -> APInt {
        self.ensure_width_compatible(other);
        let full = mul_words(&self.words, &other.words);
        let nw = self.words.len();
        let truncated: Vec<u64> = full.into_iter().take(nw).collect();
        APInt::from_words(self.bit_width, truncated)
    }

    /// Unsigned division.  Panics on division by zero.
    pub fn udiv(&self, other: &APInt) -> APInt {
        self.ensure_width_compatible(other);
        if other.is_zero() {
            panic!("APInt::udiv: division by zero");
        }
        let (q, _r) = div_rem_multi(&self.words, &other.words);
        // q is already sized to self.words.len().
        let q: Vec<u64> = q.into_iter().take(self.words.len()).collect();
        APInt::from_words(self.bit_width, q)
    }

    /// Unsigned remainder.  Panics on division by zero.
    pub fn urem(&self, other: &APInt) -> APInt {
        self.ensure_width_compatible(other);
        if other.is_zero() {
            panic!("APInt::urem: division by zero");
        }
        let (_q, r) = div_rem_multi(&self.words, &other.words);
        let r: Vec<u64> = r.into_iter().take(self.words.len()).collect();
        APInt::from_words(self.bit_width, r)
    }

    /// Signed division (C99: truncates toward zero).
    /// Panics on division by zero.
    pub fn sdiv(&self, other: &APInt) -> APInt {
        self.ensure_width_compatible(other);
        if other.is_zero() {
            panic!("APInt::sdiv: division by zero");
        }
        let a_neg = self.is_negative();
        let b_neg = other.is_negative();
        let a_abs = if a_neg { self.negate() } else { self.clone() };
        let b_abs = if b_neg { other.negate() } else { other.clone() };
        let q = a_abs.udiv(&b_abs);
        if a_neg ^ b_neg {
            q.negate()
        } else {
            q
        }
    }

    /// Signed remainder (C99: `a % b` has the same sign as `a`).
    /// Panics on division by zero.
    pub fn srem(&self, other: &APInt) -> APInt {
        self.ensure_width_compatible(other);
        if other.is_zero() {
            panic!("APInt::srem: division by zero");
        }
        let a_neg = self.is_negative();
        let b_neg = other.is_negative();
        let a_abs = if a_neg { self.negate() } else { self.clone() };
        let b_abs = if b_neg { other.negate() } else { other.clone() };
        let r = a_abs.urem(&b_abs);
        if a_neg {
            r.negate()
        } else {
            r
        }
    }

    /// Two's complement negation.
    pub fn negate(&self) -> APInt {
        // -x = ~x + 1
        let one = APInt::from_u64(self.bit_width, 1);
        APInt::add(&self.not(), &one)
    }

    /// Unsigned addition with overflow flag.
    /// Returns `(result, overflow)` where overflow is `true` if the result
    /// exceeds bit_width bits.
    pub fn add_overflow(&self, other: &APInt) -> (APInt, bool) {
        self.ensure_width_compatible(other);
        let (words, carry) = add_words(&self.words, &other.words);

        let mut overflow = carry;
        if !overflow {
            // Within-word overflow: check if any bit beyond bit_width is set.
            let excess = excess_bits(self.bit_width);
            if excess > 0 {
                let last = words.last().copied().unwrap_or(0);
                overflow = (last >> (64 - excess)) != 0;
            }
        }

        let result = APInt::from_words(self.bit_width, words);
        (result, overflow)
    }

    /// Unsigned multiplication with overflow flag.
    /// Overflow if any non-zero bits exist beyond bit_width in the full product.
    pub fn mul_overflow(&self, other: &APInt) -> (APInt, bool) {
        self.ensure_width_compatible(other);
        let full = mul_words(&self.words, &other.words);
        let nw = self.words.len();
        let truncated: Vec<u64> = full.iter().take(nw).copied().collect();
        let result = APInt::from_words(self.bit_width, truncated);

        // Check if upper words are all zeros.
        let mut overflow = full[nw..].iter().any(|&w| w != 0);
        // Also check within-word overflow for non-multiple-of-64 widths.
        if !overflow {
            let rem = self.bit_width % 64;
            if rem != 0 {
                let last = full.get(nw - 1).copied().unwrap_or(0);
                overflow = (last >> rem) != 0;
            }
        }
        (result, overflow)
    }

    /// Signed subtraction with overflow flag.
    pub fn ssub_overflow(&self, other: &APInt) -> (APInt, bool) {
        self.ensure_width_compatible(other);
        let (words, _borrow) = sub_words(&self.words, &other.words);
        let result = APInt::from_words(self.bit_width, words);

        let a_sign = self.is_negative();
        let b_sign = other.is_negative();
        let r_sign = result.is_negative();
        // Signed overflow on sub when operands have different signs
        // and result sign differs from `a`'s sign.
        let overflow = (a_sign != b_sign) && (a_sign != r_sign);
        (result, overflow)
    }

    /// Signed addition with overflow flag.
    pub fn sadd_overflow(&self, other: &APInt) -> (APInt, bool) {
        self.ensure_width_compatible(other);
        let (words, _carry) = add_words(&self.words, &other.words);
        let result = APInt::from_words(self.bit_width, words);

        let a_sign = self.is_negative();
        let b_sign = other.is_negative();
        let r_sign = result.is_negative();
        // Signed overflow when operands have same sign and result sign differs.
        let overflow = (a_sign == b_sign) && (a_sign != r_sign);
        (result, overflow)
    }

    /// Signed multiplication with overflow flag.
    pub fn smul_overflow(&self, other: &APInt) -> (APInt, bool) {
        self.ensure_width_compatible(other);
        let full_words = mul_words(&self.words, &other.words);
        let nw = self.words.len();
        let truncated: Vec<u64> = full_words.iter().take(nw).copied().collect();
        let result = APInt::from_words(self.bit_width, truncated);

        let double_width = self.bit_width * 2;
        // Sign-extend result to double width.
        let sign = result.is_negative();
        let double_nw = num_words(double_width);
        let mut sext_words = vec![0u64; double_nw];
        sext_words[..result.words.len()].copy_from_slice(&result.words);
        if sign {
            for w in sext_words[result.words.len()..].iter_mut() {
                *w = u64::MAX;
            }
        }
        let mut sext_result = APInt {
            bit_width: double_width,
            words: sext_words,
        };
        sext_result.clear_unused_bits();

        let full = APInt {
            bit_width: double_width,
            words: full_words,
        };

        let overflow = sext_result != full;
        (result, overflow)
    }
}

// ---------------------------------------------------------------------------
// Bitwise operations
// ---------------------------------------------------------------------------

impl APInt {
    /// Bitwise AND.
    pub fn and(&self, other: &APInt) -> APInt {
        self.ensure_width_compatible(other);
        let words: Vec<u64> = self
            .words
            .iter()
            .zip(other.words.iter())
            .map(|(a, b)| a & b)
            .collect();
        APInt::from_words(self.bit_width, words)
    }

    /// Bitwise OR.
    pub fn or(&self, other: &APInt) -> APInt {
        self.ensure_width_compatible(other);
        let words: Vec<u64> = self
            .words
            .iter()
            .zip(other.words.iter())
            .map(|(a, b)| a | b)
            .collect();
        APInt::from_words(self.bit_width, words)
    }

    /// Bitwise XOR.
    pub fn xor(&self, other: &APInt) -> APInt {
        self.ensure_width_compatible(other);
        let words: Vec<u64> = self
            .words
            .iter()
            .zip(other.words.iter())
            .map(|(a, b)| a ^ b)
            .collect();
        APInt::from_words(self.bit_width, words)
    }

    /// Bitwise NOT (one's complement).
    pub fn not(&self) -> APInt {
        let words: Vec<u64> = self.words.iter().map(|w| !w).collect();
        APInt::from_words(self.bit_width, words)
    }

    /// Logical left shift by `shift` bits.
    pub fn shl(&self, shift: u32) -> APInt {
        if shift == 0 {
            return self.clone();
        }
        let nw = self.words.len();
        let word_shift = (shift / 64) as usize;
        let bit_shift = (shift % 64) as u32;

        let mut words = vec![0u64; nw];

        if word_shift >= nw {
            // Shifted all bits out — result is zero.
            return APInt::get_zero(self.bit_width);
        }

        if bit_shift == 0 {
            for i in (0..nw - word_shift).rev() {
                words[i + word_shift] = self.words[i];
            }
        } else {
            let inv_shift = 64 - bit_shift;
            for i in (0..nw - word_shift).rev() {
                let lo = self.words[i] << bit_shift;
                let hi = if i > 0 {
                    self.words[i - 1] >> inv_shift
                } else {
                    0
                };
                words[i + word_shift] = lo | hi;
            }
        }

        APInt::from_words(self.bit_width, words)
    }

    /// Logical right shift by `shift` bits (zero-fill).
    pub fn lshr(&self, shift: u32) -> APInt {
        if shift == 0 {
            return self.clone();
        }
        let nw = self.words.len();
        let word_shift = (shift / 64) as usize;
        let bit_shift = (shift % 64) as u32;

        let mut words = vec![0u64; nw];

        if word_shift >= nw {
            return APInt::get_zero(self.bit_width);
        }

        if bit_shift == 0 {
            for i in word_shift..nw {
                words[i - word_shift] = self.words[i];
            }
        } else {
            let inv_shift = 64 - bit_shift;
            for i in word_shift..nw {
                let lo = self.words[i] >> bit_shift;
                let hi = if i + 1 < nw {
                    self.words[i + 1] << inv_shift
                } else {
                    0
                };
                words[i - word_shift] = lo | hi;
            }
        }

        APInt::from_words(self.bit_width, words)
    }

    /// Arithmetic right shift (sign-extending).
    pub fn ashr(&self, shift: u32) -> APInt {
        if shift == 0 {
            return self.clone();
        }
        if shift >= self.bit_width {
            // All bits shifted out; result is all sign bits.
            if self.is_negative() {
                return APInt::get_all_ones(self.bit_width);
            } else {
                return APInt::get_zero(self.bit_width);
            }
        }
        let mut result = self.lshr(shift);
        if self.is_negative() {
            // Set the top `shift` bits to 1 (sign extension).
            let fill_width = self.bit_width - shift;
            let mask = APInt::get_all_ones(self.bit_width).shl(fill_width);
            result = result.or(&mask);
        }
        result
    }

    /// Rotate left by `rotate` bits.
    pub fn rotl(&self, rotate: u32) -> APInt {
        let rotate = rotate % self.bit_width;
        if rotate == 0 {
            return self.clone();
        }
        let left = self.shl(rotate);
        let right = self.lshr(self.bit_width - rotate);
        left.or(&right)
    }

    /// Rotate right by `rotate` bits.
    pub fn rotr(&self, rotate: u32) -> APInt {
        let rotate = rotate % self.bit_width;
        if rotate == 0 {
            return self.clone();
        }
        let right = self.lshr(rotate);
        let left = self.shl(self.bit_width - rotate);
        right.or(&left)
    }

    /// Truncate to a smaller bit width.
    ///
    /// # Panics
    /// Panics if `width > self.bit_width`.
    pub fn trunc(&self, width: u32) -> APInt {
        assert!(
            width <= self.bit_width,
            "APInt::trunc: new width {} exceeds current width {}",
            width,
            self.bit_width
        );
        if width == self.bit_width {
            return self.clone();
        }
        let nw = num_words(width);
        let words: Vec<u64> = self.words.iter().take(nw).copied().collect();
        APInt::from_words(width, words)
    }

    /// Sign-extend to a wider bit width.
    ///
    /// # Panics
    /// Panics if `width < self.bit_width`.
    pub fn sext(&self, width: u32) -> APInt {
        assert!(
            width >= self.bit_width,
            "APInt::sext: width must be >= current width"
        );
        if width == self.bit_width {
            return self.clone();
        }
        let nw = num_words(width);
        let mut words = vec![0u64; nw];
        words[..self.words.len()].copy_from_slice(&self.words);
        if self.is_negative() {
            // Fill all bits from self.bit_width to width-1 with 1s.
            let fill_all = APInt::get_all_ones(width);
            let mask = fill_all.shl(self.bit_width);
            let mut result = APInt {
                bit_width: width,
                words,
            };
            result = result.or(&mask);
            result.clear_unused_bits();
            result
        } else {
            APInt::from_words(width, words)
        }
    }

    /// Zero-extend to a wider bit width.
    ///
    /// # Panics
    /// Panics if `width < self.bit_width`.
    pub fn zext(&self, width: u32) -> APInt {
        assert!(
            width >= self.bit_width,
            "APInt::zext: width must be >= current width"
        );
        if width == self.bit_width {
            return self.clone();
        }
        let nw = num_words(width);
        let mut words = vec![0u64; nw];
        words[..self.words.len()].copy_from_slice(&self.words);
        APInt::from_words(width, words)
    }

    /// Extract a contiguous bit field as a new APInt.
    ///
    /// `lo_bit` is the least-significant bit of the field.
    /// `num_bits` is the number of bits to extract.
    ///
    /// # Panics
    /// Panics if `lo_bit + num_bits > self.bit_width`.
    pub fn extract_bits(&self, lo_bit: u32, num_bits: u32) -> APInt {
        assert!(
            lo_bit + num_bits <= self.bit_width,
            "APInt::extract_bits: range [{}, {}) exceeds bit_width {}",
            lo_bit,
            lo_bit + num_bits,
            self.bit_width
        );
        if num_bits == 0 {
            return APInt::get_zero(1);
        }
        // Shift right to align lo_bit with bit 0, then truncate.
        let shifted = self.lshr(lo_bit);
        shifted.trunc(num_bits)
    }
}

// ---------------------------------------------------------------------------
// Comparison methods
// ---------------------------------------------------------------------------

impl APInt {
    /// Equality comparison.
    pub fn eq(&self, other: &APInt) -> bool {
        self.bit_width == other.bit_width && self.words == other.words
    }

    /// Inequality comparison.
    pub fn ne(&self, other: &APInt) -> bool {
        !self.eq(other)
    }

    /// Unsigned less-than.
    pub fn ult(&self, other: &APInt) -> bool {
        self.ensure_width_compatible(other);
        unsigned_cmp(&self.words, &other.words) == Ordering::Less
    }

    /// Unsigned greater-than.
    pub fn ugt(&self, other: &APInt) -> bool {
        self.ensure_width_compatible(other);
        unsigned_cmp(&self.words, &other.words) == Ordering::Greater
    }

    /// Unsigned less-than-or-equal.
    pub fn ule(&self, other: &APInt) -> bool {
        self.ensure_width_compatible(other);
        matches!(
            unsigned_cmp(&self.words, &other.words),
            Ordering::Less | Ordering::Equal
        )
    }

    /// Unsigned greater-than-or-equal.
    pub fn uge(&self, other: &APInt) -> bool {
        self.ensure_width_compatible(other);
        matches!(
            unsigned_cmp(&self.words, &other.words),
            Ordering::Greater | Ordering::Equal
        )
    }

    /// Signed less-than.
    pub fn slt(&self, other: &APInt) -> bool {
        self.ensure_width_compatible(other);
        signed_cmp(&self.words, self.bit_width, &other.words, other.bit_width) == Ordering::Less
    }

    /// Signed greater-than.
    pub fn sgt(&self, other: &APInt) -> bool {
        self.ensure_width_compatible(other);
        signed_cmp(&self.words, self.bit_width, &other.words, other.bit_width) == Ordering::Greater
    }

    /// Signed less-than-or-equal.
    pub fn sle(&self, other: &APInt) -> bool {
        self.ensure_width_compatible(other);
        matches!(
            signed_cmp(&self.words, self.bit_width, &other.words, other.bit_width),
            Ordering::Less | Ordering::Equal
        )
    }

    /// Signed greater-than-or-equal.
    pub fn sge(&self, other: &APInt) -> bool {
        self.ensure_width_compatible(other);
        matches!(
            signed_cmp(&self.words, self.bit_width, &other.words, other.bit_width),
            Ordering::Greater | Ordering::Equal
        )
    }

    /// Returns `true` if the value is zero.
    pub fn is_zero(&self) -> bool {
        self.words.iter().all(|&w| w == 0)
    }

    /// Returns `true` if the value is one.
    pub fn is_one(&self) -> bool {
        self.words.first() == Some(&1) && self.words[1..].iter().all(|&w| w == 0)
    }

    /// Returns `true` if all bits are set (unsigned max).
    pub fn is_all_ones(&self) -> bool {
        let mask = last_word_mask(self.bit_width);
        let last = self.words.last().copied().unwrap_or(0);
        if last != mask {
            return false;
        }
        self.words[..self.words.len() - 1]
            .iter()
            .all(|&w| w == u64::MAX)
    }

    /// Returns `true` if the sign bit (bit `bit_width - 1`) is set.
    pub fn is_negative(&self) -> bool {
        if self.bit_width == 1 {
            return self.words[0] & 1 != 0;
        }
        let word = (self.bit_width - 1) / 64;
        let bit = (self.bit_width - 1) % 64;
        self.words
            .get(word as usize)
            .map(|w| (w >> bit) & 1 != 0)
            .unwrap_or(false)
    }

    /// Returns `true` if the value is non-negative (sign bit is zero).
    pub fn is_non_negative(&self) -> bool {
        !self.is_negative()
    }

    /// Returns `true` if the value is strictly positive (> 0).
    pub fn is_strictly_positive(&self) -> bool {
        !self.is_zero() && self.is_non_negative()
    }

    /// Returns `true` if the value is a power of two.
    pub fn is_power_of_2(&self) -> bool {
        if self.is_zero() {
            return false;
        }
        // Count population; must be exactly 1.
        // But special case: for signed min (only sign bit set), that's not
        // a power of two in the usual sense (since 2^N for N = bit_width-1
        // equals the unsigned value of the sign bit).  Power-of-2 test is
        // usually unsigned.
        self.count_population() == 1
    }

    /// Returns `true` if the value fits in a signed integer of `n` bits.
    pub fn is_signed_int_n(&self, n: u32) -> bool {
        if n == 0 {
            return self.is_zero();
        }
        if n >= self.bit_width {
            return true;
        }
        // After arithmetic right shift by (n-1), any remaining bits beyond n
        // should be equal to the sign bit at position n-1.
        let shifted = self.ashr(n - 1);
        shifted.is_zero() || shifted.is_all_ones()
    }

    /// Returns `true` if the value fits in an unsigned integer of `n` bits.
    pub fn is_int_n(&self, n: u32) -> bool {
        if n == 0 {
            return self.is_zero();
        }
        if n >= self.bit_width {
            return true;
        }
        // Bits beyond n-1 should be zero.
        let shifted = self.lshr(n);
        shifted.is_zero()
    }
}

/// Unsigned comparison of two word slices.
fn unsigned_cmp(a: &[u64], b: &[u64]) -> Ordering {
    let len = a.len().max(b.len());
    for i in (0..len).rev() {
        let aw = a.get(i).copied().unwrap_or(0);
        let bw = b.get(i).copied().unwrap_or(0);
        match aw.cmp(&bw) {
            Ordering::Equal => continue,
            ord => return ord,
        }
    }
    Ordering::Equal
}

/// Signed comparison of two word slices with given bit widths.
fn signed_cmp(a: &[u64], aw: u32, b: &[u64], bw: u32) -> Ordering {
    let a_neg = is_negative_words(a, aw);
    let b_neg = is_negative_words(b, bw);
    if a_neg != b_neg {
        return if a_neg {
            Ordering::Less
        } else {
            Ordering::Greater
        };
    }
    // Same sign; compare unsigned.
    unsigned_cmp(a, b)
}

/// Check if the sign bit is set in a word slice of given width.
fn is_negative_words(words: &[u64], bit_width: u32) -> bool {
    if bit_width == 0 {
        return false;
    }
    let word = ((bit_width - 1) / 64) as usize;
    let bit = (bit_width - 1) % 64;
    words
        .get(word)
        .map(|w| (w >> bit) & 1 != 0)
        .unwrap_or(false)
}

// ---------------------------------------------------------------------------
// Conversion
// ---------------------------------------------------------------------------

impl APInt {
    /// Truncate to a u64 (returns `None` if any high bits beyond 64 are set).
    pub fn to_u64(&self) -> Option<u64> {
        // Check that bits beyond 63 are zero.
        if self.words.len() > 1 && self.words[1..].iter().any(|&w| w != 0) {
            return None;
        }
        if self.bit_width > 64 && self.words.len() >= 2 && self.words[1] != 0 {
            return None;
        }
        // Also check if the 64th bit (if bit_width > 64) is set in word 0.
        // Wait, word 0 is bits 0..63. If bit_width > 64, all of word 0 is used.
        // If bit_width <= 64, the mask handles it.
        Some(self.words.first().copied().unwrap_or(0))
    }

    /// Truncate to an i64 (returns `None` if value does not fit in 64-bit signed).
    pub fn to_i64(&self) -> Option<i64> {
        if self.bit_width <= 64 {
            let val = self.words.first().copied().unwrap_or(0);
            if self.bit_width < 64 {
                // Sign-extend val from bit_width to 64 bits.
                let shift = 64 - self.bit_width;
                Some(((val << shift) as i64) >> shift)
            } else {
                Some(val as i64)
            }
        } else {
            // Need to check that all bits beyond the low 64 sign-extend correctly.
            let low = self.words[0];
            let sign_bit_64 = (low >> 63) & 1;
            // All higher words must equal the sign extension.
            let fill = if sign_bit_64 != 0 { u64::MAX } else { 0 };
            for &w in &self.words[1..] {
                if w != fill {
                    return None;
                }
            }
            // Also check bits in word 1 if bit_width isn't a multiple of 64.
            // Actually, the check above is sufficient since clear_unused_bits ensures
            // unused bits are zero, and fill check covers all higher words.
            Some(low as i64)
        }
    }

    /// Convert to a string in the given radix.
    ///
    /// If `signed` is true, the value is interpreted as a signed integer
    /// (negative values prefixed with `-`).  Otherwise, it is printed as unsigned.
    pub fn to_string(&self, radix: u8, signed: bool) -> String {
        if radix != 2 && radix != 8 && radix != 10 && radix != 16 {
            panic!("APInt::to_string: unsupported radix {}", radix);
        }
        if signed && self.is_negative() {
            let neg = self.negate();
            format!("-{}", neg.to_string(radix, false))
        } else {
            to_string_unsigned(&self.words, radix)
        }
    }

    /// Convert to little-endian bytes.
    pub fn to_bytes_le(&self) -> Vec<u8> {
        let byte_len = ((self.bit_width + 7) / 8) as usize;
        let mut bytes = vec![0u8; byte_len];
        for (i, &w) in self.words.iter().enumerate() {
            let base = i * 8;
            if base >= byte_len {
                break;
            }
            for j in 0..8 {
                let idx = base + j;
                if idx >= byte_len {
                    break;
                }
                bytes[idx] = (w >> (j * 8)) as u8;
            }
        }
        bytes
    }

    /// Convert to big-endian bytes.
    pub fn to_bytes_be(&self) -> Vec<u8> {
        let byte_len = ((self.bit_width + 7) / 8) as usize;
        let mut bytes = vec![0u8; byte_len];
        for (i, &w) in self.words.iter().enumerate() {
            for j in 0..8 {
                let byte_idx = i * 8 + j;
                if byte_idx >= byte_len {
                    break;
                }
                let be_idx = byte_len - 1 - byte_idx;
                bytes[be_idx] = (w >> (j * 8)) as u8;
            }
        }
        bytes
    }

    /// Return the value as a u64, saturated to `limit`.
    /// If the value is > `limit`, return `limit`.
    pub fn get_limited_value(&self, limit: u64) -> u64 {
        // If we can fit in u64, compare; otherwise we're definitely > limit.
        if let Some(val) = self.to_u64() {
            val.min(limit)
        } else if limit == u64::MAX {
            limit
        } else {
            // Value > u64::MAX > limit (since limit < u64::MAX)
            limit
        }
    }
}

/// Convert an unsigned word slice to a string in the given radix.
fn to_string_unsigned(words: &[u64], radix: u8) -> String {
    if words.iter().all(|&w| w == 0) {
        return "0".to_string();
    }

    // Repeatedly divide by radix, collecting remainders.
    let mut digits: Vec<u8> = Vec::new();
    let mut current = words.to_vec();

    while !current.iter().all(|&w| w == 0) {
        let (_quotient, rem) = div_rem_single(&current, radix as u64);
        digits.push(rem as u8);
        let (q, _) = div_rem_single(&current, radix as u64);
        current = q;
        // Trim leading zeros.
        while current.len() > 1 && current.last() == Some(&0) {
            current.pop();
        }
    }

    digits.reverse();
    let chars: String = digits
        .into_iter()
        .map(|d| {
            if d < 10 {
                (b'0' + d) as char
            } else {
                (b'a' + (d - 10)) as char
            }
        })
        .collect();
    chars
}

// ---------------------------------------------------------------------------
// Bit-level access
// ---------------------------------------------------------------------------

impl APInt {
    /// Get the value of a single bit.
    ///
    /// # Panics
    /// Panics if `bit >= self.bit_width`.
    pub fn get_bit(&self, bit: u32) -> bool {
        assert!(
            bit < self.bit_width,
            "get_bit: bit {} out of range (width {})",
            bit,
            self.bit_width
        );
        let word = (bit / 64) as usize;
        let bit_in_word = bit % 64;
        (self.words[word] >> bit_in_word) & 1 != 0
    }

    /// Set a single bit to 1.
    ///
    /// # Panics
    /// Panics if `bit >= self.bit_width`.
    pub fn set_bit(&mut self, bit: u32) {
        assert!(
            bit < self.bit_width,
            "set_bit: bit {} out of range (width {})",
            bit,
            self.bit_width
        );
        let word = (bit / 64) as usize;
        let bit_in_word = bit % 64;
        // Ensure words vector is large enough.
        if word >= self.words.len() {
            self.words.resize(word + 1, 0);
        }
        self.words[word] |= 1u64 << bit_in_word;
    }

    /// Clear a single bit to 0.
    ///
    /// # Panics
    /// Panics if `bit >= self.bit_width`.
    pub fn clear_bit(&mut self, bit: u32) {
        assert!(
            bit < self.bit_width,
            "clear_bit: bit {} out of range (width {})",
            bit,
            self.bit_width
        );
        let word = (bit / 64) as usize;
        let bit_in_word = bit % 64;
        if word < self.words.len() {
            self.words[word] &= !(1u64 << bit_in_word);
        }
    }

    /// Return the number of 64-bit words used.
    pub fn get_num_words(&self) -> usize {
        self.words.len()
    }

    /// Return a reference to the raw word data.
    pub fn get_raw_data(&self) -> &[u64] {
        &self.words
    }

    /// Count leading zeros (before the most significant set bit).
    pub fn count_leading_zeros(&self) -> u32 {
        let mut count = 0u32;
        for i in (0..self.words.len()).rev() {
            let w = self.words[i];
            if w == 0 {
                count += 64;
            } else {
                count += w.leading_zeros();
                break;
            }
        }
        // Subtract excess bits in the last word.
        let excess = excess_bits(self.bit_width);
        if count >= excess {
            count - excess
        } else {
            0
        }
    }

    /// Count trailing zeros (before the least significant set bit).
    pub fn count_trailing_zeros(&self) -> u32 {
        let mut count = 0u32;
        for &w in &self.words {
            if w == 0 {
                count += 64;
            } else {
                count += w.trailing_zeros();
                break;
            }
        }
        count.min(self.bit_width)
    }

    /// Count the number of set bits (population count / Hamming weight).
    pub fn count_population(&self) -> u32 {
        self.words.iter().map(|&w| w.count_ones()).sum()
    }

    /// Return the low `num_bits` as a new APInt.
    pub fn get_lo_bits(&self, num_bits: u32) -> APInt {
        assert!(num_bits <= self.bit_width);
        if num_bits == 0 {
            return APInt::get_zero(1);
        }
        self.trunc(num_bits)
    }

    /// Return the high `num_bits` as a new APInt.
    pub fn get_hi_bits(&self, num_bits: u32) -> APInt {
        assert!(num_bits <= self.bit_width);
        if num_bits == 0 {
            return APInt::get_zero(1);
        }
        let shift = self.bit_width - num_bits;
        let shifted = self.lshr(shift);
        shifted.trunc(num_bits)
    }
}

// ---------------------------------------------------------------------------
// Advanced operations
// ---------------------------------------------------------------------------

impl APInt {
    /// Greatest common divisor (Euclidean algorithm).
    pub fn gcd(&self, other: &APInt) -> APInt {
        self.ensure_width_compatible(other);
        let mut a = self.clone();
        let mut b = other.clone();
        if a.is_zero() {
            return b;
        }
        if b.is_zero() {
            return a;
        }
        // Ensure a >= b (unsigned).
        if a.ult(&b) {
            std::mem::swap(&mut a, &mut b);
        }
        while !b.is_zero() {
            let r = a.urem(&b);
            a = b;
            b = r;
        }
        a
    }

    /// Least common multiple.
    /// lcm(a, b) = a / gcd(a, b) * b (handles zero correctly).
    pub fn lcm(&self, other: &APInt) -> APInt {
        self.ensure_width_compatible(other);
        if self.is_zero() || other.is_zero() {
            return APInt::get_zero(self.bit_width);
        }
        let g = self.gcd(other);
        // (a / g) * b
        let a_div_g = self.udiv(&g);
        APInt::mul(&a_div_g, other)
    }

    /// Integer square root (floor).
    /// Uses Newton's method with division-based convergence check to avoid
    /// overflow from wrapping multiplication.
    pub fn sqrt(&self) -> APInt {
        if self.is_zero() {
            return self.clone();
        }
        // Initial guess: 2^(bit_len/2).
        let bit_len = self.active_bits() as u32;
        let mut x = APInt::from_u64(self.bit_width, 1).shl((bit_len + 1) / 2);

        // Newton iteration: x_{n+1} = (x_n + self/x_n) / 2
        loop {
            let q = self.udiv(&x);
            let x_next = APInt::add(&x, &q).lshr(1);
            if x_next.uge(&x) {
                break;
            }
            x = x_next;
        }
        // Adjust downward using x > self/x instead of x*x > self
        // to avoid wrapping multiplication.
        let one = APInt::from_u64(self.bit_width, 1);
        while x.ugt(&self.udiv(&x)) {
            x = APInt::sub(&x, &one);
        }
        x
    }

    /// Absolute value.
    pub fn abs(&self) -> APInt {
        if self.is_negative() {
            self.negate()
        } else {
            self.clone()
        }
    }

    /// Unsigned minimum.
    pub fn umin(&self, other: &APInt) -> APInt {
        if self.ult(other) {
            self.clone()
        } else {
            other.clone()
        }
    }

    /// Unsigned maximum.
    pub fn umax(&self, other: &APInt) -> APInt {
        if self.ugt(other) {
            self.clone()
        } else {
            other.clone()
        }
    }

    /// Signed minimum.
    pub fn smin(&self, other: &APInt) -> APInt {
        if self.slt(other) {
            self.clone()
        } else {
            other.clone()
        }
    }

    /// Signed maximum.
    pub fn smax(&self, other: &APInt) -> APInt {
        if self.sgt(other) {
            self.clone()
        } else {
            other.clone()
        }
    }
}

// ---------------------------------------------------------------------------
// Operator overloads
// ---------------------------------------------------------------------------

impl PartialEq for APInt {
    fn eq(&self, other: &APInt) -> bool {
        self.eq(other)
    }
}

impl Eq for APInt {}

impl Hash for APInt {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.bit_width.hash(state);
        for &w in &self.words {
            w.hash(state);
        }
    }
}

impl PartialOrd for APInt {
    fn partial_cmp(&self, other: &APInt) -> Option<Ordering> {
        if self.bit_width != other.bit_width {
            return None;
        }
        Some(unsigned_cmp(&self.words, &other.words))
    }
}

impl<'a, 'b> Add<&'b APInt> for &'a APInt {
    type Output = APInt;
    fn add(self, rhs: &'b APInt) -> APInt {
        APInt::add(self, rhs)
    }
}

impl<'a, 'b> Sub<&'b APInt> for &'a APInt {
    type Output = APInt;
    fn sub(self, rhs: &'b APInt) -> APInt {
        APInt::sub(self, rhs)
    }
}

impl<'a, 'b> Mul<&'b APInt> for &'a APInt {
    type Output = APInt;
    fn mul(self, rhs: &'b APInt) -> APInt {
        APInt::mul(self, rhs)
    }
}

impl<'a, 'b> BitAnd<&'b APInt> for &'a APInt {
    type Output = APInt;
    fn bitand(self, rhs: &'b APInt) -> APInt {
        APInt::and(self, rhs)
    }
}

impl<'a, 'b> BitOr<&'b APInt> for &'a APInt {
    type Output = APInt;
    fn bitor(self, rhs: &'b APInt) -> APInt {
        APInt::or(self, rhs)
    }
}

impl<'a, 'b> BitXor<&'b APInt> for &'a APInt {
    type Output = APInt;
    fn bitxor(self, rhs: &'b APInt) -> APInt {
        APInt::xor(self, rhs)
    }
}

impl<'a> Shl<u32> for &'a APInt {
    type Output = APInt;
    fn shl(self, shift: u32) -> APInt {
        APInt::shl(self, shift)
    }
}

impl<'a> Shr<u32> for &'a APInt {
    type Output = APInt;
    fn shr(self, shift: u32) -> APInt {
        APInt::lshr(self, shift)
    }
}

impl Not for APInt {
    type Output = APInt;
    fn not(self) -> APInt {
        APInt::not(&self)
    }
}

impl<'a> Not for &'a APInt {
    type Output = APInt;
    fn not(self) -> APInt {
        APInt::not(self)
    }
}

impl<'a> Neg for &'a APInt {
    type Output = APInt;
    fn neg(self) -> APInt {
        APInt::negate(self)
    }
}

impl fmt::Display for APInt {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.to_string(10, false))
    }
}

impl fmt::Debug for APInt {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "APInt({}b, 0x{})",
            self.bit_width,
            self.to_string(16, false)
        )
    }
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;

    // =======================================================================
    // Construction tests
    // =======================================================================

    #[test]
    #[should_panic(expected = "bit_width must be >= 1")]
    fn test_new_zero_width_panics() {
        APInt::new(0, 0, false);
    }

    #[test]
    fn test_new_1bit() {
        let a = APInt::new(1, 0, false);
        assert_eq!(a.to_u64(), Some(0));
        let b = APInt::new(1, 1, false);
        assert_eq!(b.to_u64(), Some(1));
    }

    #[test]
    fn test_from_u64() {
        let a = APInt::from_u64(64, 0xDEADBEEF);
        assert_eq!(a.to_u64(), Some(0xDEADBEEF));

        let b = APInt::from_u64(128, 0xFFFFFFFFFFFFFFFF);
        assert_eq!(b.to_u64(), Some(0xFFFFFFFFFFFFFFFF));
        // Upper word should be zero.
        assert_eq!(b.words.len(), 2);
        assert_eq!(b.words[1], 0);
    }

    #[test]
    fn test_from_i64_positive() {
        let a = APInt::from_i64(128, 42);
        assert_eq!(a.to_i64(), Some(42));
        assert_eq!(a.words.len(), 2);
        assert_eq!(a.words[1], 0);
    }

    #[test]
    fn test_from_i64_negative() {
        let a = APInt::from_i64(128, -1);
        assert_eq!(a.to_i64(), Some(-1));
        assert!(a.is_negative());
        // Should be sign-extended: all 128 bits are 1.
        assert_eq!(a.words[0], u64::MAX);
        assert_eq!(a.words[1], u64::MAX);
    }

    #[test]
    fn test_get_zero() {
        let z = APInt::get_zero(256);
        assert!(z.is_zero());
        assert_eq!(z.words.len(), 4);
        assert!(z.words.iter().all(|&w| w == 0));
    }

    #[test]
    fn test_get_one() {
        let o = APInt::get_one(65);
        assert!(o.is_one());
        assert_eq!(o.words[0], 1);
        assert_eq!(o.words[1], 0);
    }

    #[test]
    fn test_get_all_ones() {
        let a = APInt::get_all_ones(65);
        assert!(a.is_all_ones());
        assert_eq!(a.words[0], u64::MAX);
        assert_eq!(a.words[1], 1); // only one bit in second word
    }

    #[test]
    fn test_get_signed_max_value() {
        // 8-bit signed max = 127
        let a = APInt::get_signed_max_value(8);
        assert_eq!(a.to_u64(), Some(127));
        assert!(!a.is_negative());

        // 64-bit signed max
        let b = APInt::get_signed_max_value(64);
        assert_eq!(b.to_u64(), Some(i64::MAX as u64));
    }

    #[test]
    fn test_get_signed_min_value() {
        // 8-bit signed min = -128
        let a = APInt::get_signed_min_value(8);
        assert!(a.is_negative());
        assert_eq!(a.to_i64(), Some(-128));

        // 64-bit signed min
        let b = APInt::get_signed_min_value(64);
        assert_eq!(b.to_i64(), Some(i64::MIN));
    }

    // =======================================================================
    // String parsing tests
    // =======================================================================

    #[test]
    fn test_from_string_decimal() {
        let a = APInt::from_string("12345", 10).unwrap();
        assert_eq!(a.to_string(10, false), "12345");
    }

    #[test]
    fn test_from_string_hex_prefix() {
        let a = APInt::from_string("0xFF", 0).unwrap();
        assert_eq!(a.to_u64(), Some(255));
        assert_eq!(a.to_string(16, false), "ff");

        let b = APInt::from_string("0xDEAD", 0).unwrap();
        assert_eq!(b.to_u64(), Some(0xDEAD));
    }

    #[test]
    fn test_from_string_binary_prefix() {
        let a = APInt::from_string("0b1010", 0).unwrap();
        assert_eq!(a.to_u64(), Some(10));

        let b = APInt::from_string("0b11111111", 0).unwrap();
        assert_eq!(b.to_u64(), Some(255));
    }

    #[test]
    fn test_from_string_octal_prefix() {
        let a = APInt::from_string("0o77", 0).unwrap();
        assert_eq!(a.to_u64(), Some(63));
    }

    #[test]
    fn test_from_string_explicit_radix() {
        let a = APInt::from_string("1010", 2).unwrap();
        assert_eq!(a.to_u64(), Some(10));

        let b = APInt::from_string("77", 8).unwrap();
        assert_eq!(b.to_u64(), Some(63));

        let c = APInt::from_string("FF", 16).unwrap();
        assert_eq!(c.to_u64(), Some(255));
    }

    #[test]
    fn test_from_string_large_hex() {
        let a = APInt::from_string("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 0).unwrap();
        // 128-bit all-ones.
        assert_eq!(a.words.len(), 2);
        assert_eq!(a.words[0], u64::MAX);
        assert_eq!(a.words[1], u64::MAX);
    }

    #[test]
    fn test_from_string_empty() {
        assert!(APInt::from_string("", 10).is_err());
    }

    #[test]
    fn test_from_string_invalid_digit() {
        assert!(APInt::from_string("12G", 16).is_err());
        assert!(APInt::from_string("102", 2).is_err());
    }

    // =======================================================================
    // Bytes conversion tests
    // =======================================================================

    #[test]
    fn test_from_bytes_le() {
        let a = APInt::from_bytes_le(&[0x78, 0x56, 0x34, 0x12], 32);
        assert_eq!(a.to_u64(), Some(0x12345678));
    }

    #[test]
    fn test_from_bytes_be() {
        let a = APInt::from_bytes_be(&[0x12, 0x34, 0x56, 0x78], 32);
        assert_eq!(a.to_u64(), Some(0x12345678));
    }

    #[test]
    fn test_to_bytes_le_roundtrip() {
        let original = APInt::from_u64(64, 0xDEADBEEFCAFEBABE);
        let bytes = original.to_bytes_le();
        let roundtrip = APInt::from_bytes_le(&bytes, 64);
        assert_eq!(original, roundtrip);
    }

    #[test]
    fn test_to_bytes_be_roundtrip() {
        let original = APInt::from_u64(64, 0xDEADBEEFCAFEBABE);
        let bytes = original.to_bytes_be();
        let roundtrip = APInt::from_bytes_be(&bytes, 64);
        assert_eq!(original, roundtrip);
    }

    // =======================================================================
    // Arithmetic tests
    // =======================================================================

    #[test]
    fn test_add_basic() {
        let a = APInt::from_u64(64, 100);
        let b = APInt::from_u64(64, 200);
        assert_eq!(a.add(&b).to_u64(), Some(300));
    }

    #[test]
    fn test_add_wrapping() {
        let a = APInt::from_u64(8, 250);
        let b = APInt::from_u64(8, 10);
        // 250 + 10 = 260, wraps to 260 % 256 = 4
        assert_eq!(a.add(&b).to_u64(), Some(4));
    }

    #[test]
    fn test_sub_basic() {
        let a = APInt::from_u64(64, 500);
        let b = APInt::from_u64(64, 200);
        assert_eq!(a.sub(&b).to_u64(), Some(300));
    }

    #[test]
    fn test_sub_wrapping() {
        let a = APInt::from_u64(8, 5);
        let b = APInt::from_u64(8, 10);
        // 5 - 10 = -5 ≡ 251 (mod 256)
        assert_eq!(a.sub(&b).to_u64(), Some(251));
    }

    #[test]
    fn test_mul_basic() {
        let a = APInt::from_u64(64, 7);
        let b = APInt::from_u64(64, 9);
        assert_eq!(a.mul(&b).to_u64(), Some(63));
    }

    #[test]
    fn test_mul_wrapping() {
        let a = APInt::from_u64(8, 16);
        let b = APInt::from_u64(8, 16);
        // 16 * 16 = 256, wraps to 0
        assert_eq!(a.mul(&b).to_u64(), Some(0));
    }

    #[test]
    fn test_mul_65bit() {
        let a = APInt::from_u64(65, 3);
        let b = APInt::from_u64(65, 5);
        assert_eq!(a.mul(&b).to_u64(), Some(15));
    }

    #[test]
    fn test_udiv_basic() {
        let a = APInt::from_u64(64, 100);
        let b = APInt::from_u64(64, 7);
        assert_eq!(a.udiv(&b).to_u64(), Some(14));
    }

    #[test]
    #[should_panic(expected = "division by zero")]
    fn test_udiv_by_zero() {
        let a = APInt::from_u64(64, 100);
        let b = APInt::get_zero(64);
        a.udiv(&b);
    }

    #[test]
    fn test_urem_basic() {
        let a = APInt::from_u64(64, 100);
        let b = APInt::from_u64(64, 7);
        assert_eq!(a.urem(&b).to_u64(), Some(2));
    }

    #[test]
    fn test_sdiv_positive() {
        let a = APInt::from_i64(64, 100);
        let b = APInt::from_i64(64, 7);
        assert_eq!(a.sdiv(&b).to_i64(), Some(14));
    }

    #[test]
    fn test_sdiv_negative_dividend() {
        // C99: -100 / 7 = -14 (truncate toward zero)
        let a = APInt::from_i64(64, -100);
        let b = APInt::from_i64(64, 7);
        assert_eq!(a.sdiv(&b).to_i64(), Some(-14));
    }

    #[test]
    fn test_sdiv_negative_divisor() {
        // 100 / -7 = -14
        let a = APInt::from_i64(64, 100);
        let b = APInt::from_i64(64, -7);
        assert_eq!(a.sdiv(&b).to_i64(), Some(-14));
    }

    #[test]
    fn test_sdiv_both_negative() {
        // -100 / -7 = 14
        let a = APInt::from_i64(64, -100);
        let b = APInt::from_i64(64, -7);
        assert_eq!(a.sdiv(&b).to_i64(), Some(14));
    }

    #[test]
    fn test_srem_c99() {
        // C99: -100 % 7 = -2 (remainder has sign of dividend)
        let a = APInt::from_i64(64, -100);
        let b = APInt::from_i64(64, 7);
        assert_eq!(a.srem(&b).to_i64(), Some(-2));
    }

    #[test]
    fn test_negate() {
        let a = APInt::from_i64(64, 42);
        let n = a.negate();
        assert_eq!(n.to_i64(), Some(-42));
    }

    #[test]
    fn test_negate_zero() {
        let a = APInt::get_zero(64);
        let n = a.negate();
        assert!(n.is_zero());
    }

    #[test]
    fn test_negate_min_value() {
        // Negating signed min gives signed min (wrapping).
        let a = APInt::get_signed_min_value(64); // -2^63
        let n = a.negate();
        // In two's complement, negating the minimum gives itself.
        assert_eq!(n, a);
    }

    // =======================================================================
    // Overflow tests
    // =======================================================================

    #[test]
    fn test_add_overflow_no() {
        let a = APInt::from_u64(64, 100);
        let b = APInt::from_u64(64, 200);
        let (result, overflow) = a.add_overflow(&b);
        assert_eq!(result.to_u64(), Some(300));
        assert!(!overflow);
    }

    #[test]
    fn test_add_overflow_yes() {
        let a = APInt::from_u64(8, 200);
        let b = APInt::from_u64(8, 100);
        let (_result, overflow) = a.add_overflow(&b);
        // 200 + 100 = 300 > 255, overflow.
        assert!(overflow);
    }

    #[test]
    fn test_mul_overflow_no() {
        let a = APInt::from_u64(64, 100);
        let b = APInt::from_u64(64, 200);
        let (_result, overflow) = a.mul_overflow(&b);
        assert!(!overflow);
    }

    #[test]
    fn test_mul_overflow_yes() {
        let a = APInt::from_u64(8, 16);
        let b = APInt::from_u64(8, 16);
        let (_result, overflow) = a.mul_overflow(&b);
        assert!(overflow);
    }

    #[test]
    fn test_sadd_overflow_no() {
        let a = APInt::from_i64(64, 100);
        let b = APInt::from_i64(64, 200);
        let (_result, overflow) = a.sadd_overflow(&b);
        assert!(!overflow);
    }

    #[test]
    fn test_sadd_overflow_pos() {
        let a = APInt::get_signed_max_value(64); // i64::MAX
        let b = APInt::from_i64(64, 1);
        let (_result, overflow) = a.sadd_overflow(&b);
        assert!(overflow);
    }

    #[test]
    fn test_sadd_overflow_neg() {
        let a = APInt::get_signed_min_value(64); // i64::MIN
        let b = APInt::from_i64(64, -1);
        let (_result, overflow) = a.sadd_overflow(&b);
        assert!(overflow);
    }

    #[test]
    fn test_ssub_overflow_no() {
        let a = APInt::from_i64(64, 100);
        let b = APInt::from_i64(64, 50);
        let (_result, overflow) = a.ssub_overflow(&b);
        assert!(!overflow);
    }

    #[test]
    fn test_ssub_overflow_yes() {
        let a = APInt::get_signed_max_value(64); // i64::MAX
        let b = APInt::from_i64(64, -1);
        let (_result, overflow) = a.ssub_overflow(&b);
        // i64::MAX - (-1) = i64::MAX + 1 overflows
        assert!(overflow);
    }

    #[test]
    fn test_smul_overflow_no() {
        let a = APInt::from_i64(64, 100);
        let b = APInt::from_i64(64, 200);
        let (_result, overflow) = a.smul_overflow(&b);
        assert!(!overflow);
    }

    #[test]
    fn test_smul_overflow_yes() {
        let a = APInt::get_signed_max_value(64); // i64::MAX
        let b = APInt::from_i64(64, 2);
        let (_result, overflow) = a.smul_overflow(&b);
        assert!(overflow);
    }

    // =======================================================================
    // Bitwise tests
    // =======================================================================

    #[test]
    fn test_and() {
        let a = APInt::from_u64(64, 0xFF00);
        let b = APInt::from_u64(64, 0x0FF0);
        assert_eq!(a.and(&b).to_u64(), Some(0x0F00));
    }

    #[test]
    fn test_or() {
        let a = APInt::from_u64(64, 0xFF00);
        let b = APInt::from_u64(64, 0x0FF0);
        assert_eq!(a.or(&b).to_u64(), Some(0xFFF0));
    }

    #[test]
    fn test_xor() {
        let a = APInt::from_u64(64, 0xFF00);
        let b = APInt::from_u64(64, 0x0FF0);
        assert_eq!(a.xor(&b).to_u64(), Some(0xF0F0));
    }

    #[test]
    fn test_not() {
        let a = APInt::from_u64(8, 0x0F);
        // ~0x0F in 8 bits = 0xF0
        assert_eq!(a.not().to_u64(), Some(0xF0));
    }

    #[test]
    fn test_shl_basic() {
        let a = APInt::from_u64(64, 1);
        assert_eq!(a.shl(10).to_u64(), Some(1024));
    }

    #[test]
    fn test_shl_wrapping() {
        let a = APInt::from_u64(8, 0x01);
        assert_eq!(a.shl(8).to_u64(), Some(0)); // shifted all out
        assert_eq!(a.shl(9).to_u64(), Some(0));
    }

    #[test]
    fn test_shl_65bit() {
        let a = APInt::from_u64(65, 1);
        let s = a.shl(64);
        assert_eq!(s.words[0], 0);
        assert_eq!(s.words[1], 1);
    }

    #[test]
    fn test_lshr_basic() {
        let a = APInt::from_u64(64, 0x8000_0000_0000_0000);
        assert_eq!(a.lshr(63).to_u64(), Some(1));
    }

    #[test]
    fn test_lshr_zero_fill() {
        let a = APInt::from_u64(64, 0xFFFF_FFFF_FFFF_FFFF);
        assert_eq!(a.lshr(4).to_u64(), Some(0x0FFF_FFFF_FFFF_FFFF));
    }

    #[test]
    fn test_ashr_sign_extend() {
        // 8-bit: 0x80 = -128 (signed)
        let a = APInt::from_i64(8, -128);
        let s = a.ashr(1);
        // -128 >> 1 = -64 = 0xC0
        assert_eq!(s.to_i64(), Some(-64));

        let s2 = a.ashr(4);
        // -128 >> 4 = -8 = 0xF8
        assert_eq!(s2.to_i64(), Some(-8));
    }

    #[test]
    fn test_ashr_positive() {
        let a = APInt::from_u64(8, 0x40); // 64
        assert_eq!(a.ashr(1).to_u64(), Some(32));
        assert_eq!(a.ashr(6).to_u64(), Some(1));
        assert_eq!(a.ashr(7).to_u64(), Some(0));
    }

    #[test]
    fn test_rotl() {
        // 8-bit: 0b10000001 (129)
        let a = APInt::from_u64(8, 0x81);
        assert_eq!(a.rotl(1).to_u64(), Some(0x03)); // 0b00000011
        assert_eq!(a.rotl(2).to_u64(), Some(0x06)); // 0b00000110
    }

    #[test]
    fn test_rotr() {
        let a = APInt::from_u64(8, 0x81);
        assert_eq!(a.rotr(1).to_u64(), Some(0xC0)); // 0b11000000
        assert_eq!(a.rotr(2).to_u64(), Some(0x60)); // 0b01100000
    }

    #[test]
    fn test_trunc() {
        let a = APInt::from_u64(64, 0x123456789ABCDEF0);
        let t = a.trunc(32);
        assert_eq!(t.bit_width, 32);
        assert_eq!(t.to_u64(), Some(0x9ABCDEF0));
    }

    #[test]
    fn test_sext() {
        // 8-bit: 0xFF = -1
        let a = APInt::from_i64(8, -1);
        let s = a.sext(64);
        assert_eq!(s.bit_width, 64);
        assert_eq!(s.to_i64(), Some(-1));
    }

    #[test]
    fn test_zext() {
        let a = APInt::from_u64(8, 0xFF);
        let z = a.zext(64);
        assert_eq!(z.bit_width, 64);
        assert_eq!(z.to_u64(), Some(0xFF));
    }

    #[test]
    fn test_extract_bits() {
        // 64-bit: 0x123456789ABCDEF0
        let a = APInt::from_u64(64, 0x123456789ABCDEF0);
        let e = a.extract_bits(4, 8);
        // Bits [4..12) of ...DEF0: F0 = 1111_0000, bits 4..11 = 1111_1111? No.
        // Let's compute: 0x...DEF0 → bits 4..11: 0xEF = 239? Actually:
        // ...DEF0 in binary: ...1101_1110_1111_0000
        // bit 0 is LSB (0), bit 4..11: starting from bit 4: 1111_111? No...
        // 0x...DEF0 byte view: F0 = 11110000, EF = 11101111, DE = 11011110
        // bits [4..12): bits 4,5,6,7,8,9,10,11 = 1111 1110?
        // Let me just check that extract_bits returns correct width.
        assert_eq!(e.bit_width, 8);
        // The value should be (a >> 4) & 0xFF = 0x...DEF0 >> 4 = 0x...DEF = 0xEF = 239
        assert_eq!(e.to_u64(), Some(0xEF));
    }

    #[test]
    fn test_extract_bits_boundary() {
        let a = APInt::from_u64(65, u64::MAX);
        let e = a.extract_bits(60, 5);
        assert_eq!(e.bit_width, 5);
        // a has bits [0..63] = 1, bit 64 = 0
        // bits 60..64: 4 bits of 1 from word 0, 1 bit of 0 from word 1
        assert_eq!(e.to_u64(), Some(0x0F)); // lower 4 bits = 1, upper 1 bit = 0 → 0b01111 = 15
    }

    // =======================================================================
    // Comparison tests
    // =======================================================================

    #[test]
    fn test_eq() {
        let a = APInt::from_u64(64, 42);
        let b = APInt::from_u64(64, 42);
        let c = APInt::from_u64(64, 99);
        assert!(a.eq(&b));
        assert!(a.ne(&c));
    }

    #[test]
    fn test_ult() {
        let a = APInt::from_u64(64, 100);
        let b = APInt::from_u64(64, 200);
        assert!(a.ult(&b));
        assert!(!b.ult(&a));
    }

    #[test]
    fn test_ule() {
        let a = APInt::from_u64(64, 100);
        let b = APInt::from_u64(64, 100);
        assert!(a.ule(&b));
        assert!(b.ule(&a));
    }

    #[test]
    fn test_slt_positive() {
        let a = APInt::from_i64(64, 100);
        let b = APInt::from_i64(64, 200);
        assert!(a.slt(&b));
    }

    #[test]
    fn test_slt_negative() {
        let a = APInt::from_i64(64, -100);
        let b = APInt::from_i64(64, 50);
        assert!(a.slt(&b));
    }

    #[test]
    fn test_slt_both_negative() {
        let a = APInt::from_i64(64, -200);
        let b = APInt::from_i64(64, -100);
        assert!(a.slt(&b));
    }

    #[test]
    fn test_is_negative() {
        let a = APInt::from_i64(64, -1);
        assert!(a.is_negative());
        let b = APInt::from_u64(64, 1);
        assert!(!b.is_negative());
    }

    #[test]
    fn test_is_power_of_2() {
        assert!(APInt::from_u64(64, 1).is_power_of_2());
        assert!(APInt::from_u64(64, 2).is_power_of_2());
        assert!(APInt::from_u64(64, 1024).is_power_of_2());
        assert!(!APInt::from_u64(64, 0).is_power_of_2());
        assert!(!APInt::from_u64(64, 3).is_power_of_2());
        assert!(!APInt::from_u64(64, 1023).is_power_of_2());
    }

    #[test]
    fn test_is_signed_int_n() {
        let a = APInt::from_i64(64, 127);
        assert!(a.is_signed_int_n(8)); // fits in 8-bit signed
        let b = APInt::from_i64(64, 128);
        assert!(!b.is_signed_int_n(8)); // doesn't fit in 8-bit signed
        let c = APInt::from_i64(64, -128);
        assert!(c.is_signed_int_n(8));
        let d = APInt::from_i64(64, -129);
        assert!(!d.is_signed_int_n(8));
    }

    #[test]
    fn test_is_int_n() {
        let a = APInt::from_u64(64, 255);
        assert!(a.is_int_n(8)); // fits in 8-bit unsigned
        let b = APInt::from_u64(64, 256);
        assert!(!b.is_int_n(8));
    }

    // =======================================================================
    // Conversion tests
    // =======================================================================

    #[test]
    fn test_to_u64_exact() {
        assert_eq!(APInt::from_u64(32, 42).to_u64(), Some(42));
    }

    #[test]
    fn test_to_u64_none() {
        // Value too large for u64.
        let a = APInt::from_u64(128, 1).shl(65);
        assert_eq!(a.to_u64(), None);
    }

    #[test]
    fn test_to_i64_positive() {
        assert_eq!(APInt::from_i64(64, 42).to_i64(), Some(42));
    }

    #[test]
    fn test_to_i64_negative() {
        assert_eq!(APInt::from_i64(64, -42).to_i64(), Some(-42));
    }

    #[test]
    fn test_to_i64_narrow() {
        // 8-bit signed value, sign-extended to i64.
        let a = APInt::from_i64(8, -1);
        assert_eq!(a.to_i64(), Some(-1));
        let b = APInt::from_i64(8, 127);
        assert_eq!(b.to_i64(), Some(127));
    }

    #[test]
    fn test_get_limited_value() {
        let a = APInt::from_u64(64, 50);
        assert_eq!(a.get_limited_value(100), 50);
        assert_eq!(a.get_limited_value(40), 40); // saturated
    }

    // =======================================================================
    // Bit-level access tests
    // =======================================================================

    #[test]
    fn test_get_bit() {
        let a = APInt::from_u64(64, 0b1010);
        assert!(a.get_bit(1));
        assert!(!a.get_bit(0));
        assert!(a.get_bit(3));
        assert!(!a.get_bit(2));
    }

    #[test]
    fn test_set_bit() {
        let mut a = APInt::from_u64(64, 0);
        a.set_bit(5);
        assert_eq!(a.to_u64(), Some(32));
        a.set_bit(0);
        assert_eq!(a.to_u64(), Some(33));
    }

    #[test]
    fn test_clear_bit() {
        let mut a = APInt::from_u64(64, 0xFF);
        a.clear_bit(0);
        assert_eq!(a.to_u64(), Some(0xFE));
        a.clear_bit(7);
        assert_eq!(a.to_u64(), Some(0x7E));
    }

    #[test]
    fn test_count_leading_zeros() {
        assert_eq!(APInt::from_u64(64, 1).count_leading_zeros(), 63);
        assert_eq!(APInt::from_u64(64, 0).count_leading_zeros(), 64);
        assert_eq!(APInt::from_u64(8, 0x0F).count_leading_zeros(), 4);
    }

    #[test]
    fn test_count_trailing_zeros() {
        assert_eq!(APInt::from_u64(64, 8).count_trailing_zeros(), 3);
        assert_eq!(APInt::from_u64(64, 0).count_trailing_zeros(), 64);
        // For 8-bit, count trailing zeros caps at bit_width.
        assert_eq!(APInt::from_u64(8, 0).count_trailing_zeros(), 8);
    }

    #[test]
    fn test_count_population() {
        assert_eq!(APInt::from_u64(64, 0).count_population(), 0);
        assert_eq!(APInt::from_u64(64, 0xFF).count_population(), 8);
        assert_eq!(APInt::from_u64(64, u64::MAX).count_population(), 64);
    }

    #[test]
    fn test_get_lo_bits() {
        let a = APInt::from_u64(64, 0xDEADBEEF);
        assert_eq!(a.get_lo_bits(16).to_u64(), Some(0xBEEF));
    }

    #[test]
    fn test_get_hi_bits() {
        // 64-bit value: high 16 bits at positions 48-63.
        let a = APInt::from_u64(64, 0xDEAD000000000000);
        assert_eq!(a.get_hi_bits(16).to_u64(), Some(0xDEAD));
    }

    // =======================================================================
    // Advanced operation tests
    // =======================================================================

    #[test]
    fn test_gcd() {
        let a = APInt::from_u64(64, 48);
        let b = APInt::from_u64(64, 18);
        assert_eq!(a.gcd(&b).to_u64(), Some(6));
    }

    #[test]
    fn test_gcd_zero() {
        let a = APInt::from_u64(64, 0);
        let b = APInt::from_u64(64, 18);
        assert_eq!(a.gcd(&b).to_u64(), Some(18));
        assert_eq!(b.gcd(&a).to_u64(), Some(18));
    }

    #[test]
    fn test_gcd_coprime() {
        let a = APInt::from_u64(64, 17);
        let b = APInt::from_u64(64, 13);
        assert_eq!(a.gcd(&b).to_u64(), Some(1));
    }

    #[test]
    fn test_gcd_large() {
        let a = APInt::from_u64(128, 1071);
        let b = APInt::from_u64(128, 462);
        assert_eq!(a.gcd(&b).to_u64(), Some(21));
    }

    #[test]
    fn test_lcm() {
        let a = APInt::from_u64(64, 12);
        let b = APInt::from_u64(64, 18);
        assert_eq!(a.lcm(&b).to_u64(), Some(36));
    }

    #[test]
    fn test_lcm_zero() {
        let a = APInt::from_u64(64, 0);
        let b = APInt::from_u64(64, 18);
        assert_eq!(a.lcm(&b).to_u64(), Some(0));
    }

    #[test]
    fn test_sqrt_perfect_square() {
        assert_eq!(APInt::from_u64(64, 0).sqrt().to_u64(), Some(0));
        assert_eq!(APInt::from_u64(64, 1).sqrt().to_u64(), Some(1));
        assert_eq!(APInt::from_u64(64, 4).sqrt().to_u64(), Some(2));
        assert_eq!(APInt::from_u64(64, 9).sqrt().to_u64(), Some(3));
        assert_eq!(APInt::from_u64(64, 100).sqrt().to_u64(), Some(10));
        assert_eq!(APInt::from_u64(64, 10000).sqrt().to_u64(), Some(100));
    }

    #[test]
    fn test_sqrt_floor() {
        assert_eq!(APInt::from_u64(64, 2).sqrt().to_u64(), Some(1));
        assert_eq!(APInt::from_u64(64, 3).sqrt().to_u64(), Some(1));
        assert_eq!(APInt::from_u64(64, 99).sqrt().to_u64(), Some(9));
        assert_eq!(APInt::from_u64(64, 120).sqrt().to_u64(), Some(10));
    }

    #[test]
    fn test_sqrt_large() {
        // sqrt(2^64 - 1) = 2^32 - 1 = 0xFFFFFFFF
        let a = APInt::from_u64(64, u64::MAX);
        let s = a.sqrt();
        // s^2 <= a
        assert!(APInt::mul(&s, &s).ule(&a));
        // (s+1)^2 > a (may overflow, so check via division)
        let s1 = APInt::add(&s, &APInt::from_u64(64, 1));
        assert!(s1.ugt(&a.udiv(&s1)));
    }

    #[test]
    fn test_sqrt_128bit() {
        // sqrt(2^64 - 1) for a 128-bit value.
        let a = APInt::from_u64(128, u64::MAX);
        let s = a.sqrt();
        // s^2 <= a (use APInt::mul to avoid method resolution issues)
        assert!(APInt::mul(&s, &s).ule(&a));
        let s1 = APInt::add(&s, &APInt::from_u64(128, 1));
        assert!(s1.ugt(&a.udiv(&s1)));
    }

    #[test]
    fn test_abs_positive() {
        let a = APInt::from_i64(64, 42);
        assert_eq!(a.abs().to_i64(), Some(42));
    }

    #[test]
    fn test_abs_negative() {
        let a = APInt::from_i64(64, -42);
        assert_eq!(a.abs().to_i64(), Some(42));
    }

    #[test]
    fn test_umin_umax() {
        let a = APInt::from_u64(64, 10);
        let b = APInt::from_u64(64, 20);
        assert_eq!(a.umin(&b).to_u64(), Some(10));
        assert_eq!(a.umax(&b).to_u64(), Some(20));
    }

    #[test]
    fn test_smin_smax() {
        let a = APInt::from_i64(64, -10);
        let b = APInt::from_i64(64, 20);
        assert_eq!(a.smin(&b).to_i64(), Some(-10));
        assert_eq!(a.smax(&b).to_i64(), Some(20));
    }

    // =======================================================================
    // Operator overload tests
    // =======================================================================

    #[test]
    fn test_operator_add() {
        let a = APInt::from_u64(64, 10);
        let b = APInt::from_u64(64, 20);
        assert_eq!((&a + &b).to_u64(), Some(30));
    }

    #[test]
    fn test_operator_sub() {
        let a = APInt::from_u64(64, 100);
        let b = APInt::from_u64(64, 30);
        assert_eq!((&a - &b).to_u64(), Some(70));
    }

    #[test]
    fn test_operator_mul() {
        let a = APInt::from_u64(64, 6);
        let b = APInt::from_u64(64, 7);
        assert_eq!((&a * &b).to_u64(), Some(42));
    }

    #[test]
    fn test_operator_bitand() {
        let a = APInt::from_u64(64, 0xFF00);
        let b = APInt::from_u64(64, 0x0FF0);
        assert_eq!((&a & &b).to_u64(), Some(0x0F00));
    }

    #[test]
    fn test_operator_bitor() {
        let a = APInt::from_u64(64, 0xFF00);
        let b = APInt::from_u64(64, 0x0FF0);
        assert_eq!((&a | &b).to_u64(), Some(0xFFF0));
    }

    #[test]
    fn test_operator_bitxor() {
        let a = APInt::from_u64(64, 0xFF00);
        let b = APInt::from_u64(64, 0x0FF0);
        assert_eq!((&a ^ &b).to_u64(), Some(0xF0F0));
    }

    #[test]
    fn test_operator_not() {
        let a = APInt::from_u64(8, 0x0F);
        assert_eq!((!a).to_u64(), Some(0xF0));
    }

    #[test]
    fn test_operator_neg() {
        let a = APInt::from_i64(64, 42);
        assert_eq!((-&a).to_i64(), Some(-42));
    }

    #[test]
    fn test_operator_shl() {
        let a = APInt::from_u64(64, 1);
        assert_eq!((&a << 10).to_u64(), Some(1024));
    }

    #[test]
    fn test_operator_shr() {
        let a = APInt::from_u64(64, 1024);
        assert_eq!((&a >> 10).to_u64(), Some(1));
    }

    #[test]
    fn test_partial_ord() {
        let a = APInt::from_u64(64, 10);
        let b = APInt::from_u64(64, 20);
        assert!(a < b);
        assert!(b > a);
        assert!(a <= b);
        assert!(b >= a);
    }

    #[test]
    fn test_partial_ord_different_widths() {
        let a = APInt::from_u64(64, 10);
        let b = APInt::from_u64(32, 20);
        assert!(a.partial_cmp(&b).is_none());
    }

    #[test]
    fn test_display() {
        let a = APInt::from_u64(64, 12345);
        assert_eq!(format!("{}", a), "12345");
    }

    #[test]
    fn test_debug() {
        let a = APInt::from_u64(64, 255);
        let s = format!("{:?}", a);
        assert!(s.contains("64b"));
        assert!(s.contains("ff"));
    }

    #[test]
    fn test_clone() {
        let a = APInt::from_u64(64, 42);
        let b = a.clone();
        assert_eq!(a, b);
        // Ensure deep copy.
        // (We can't mutate through shared reference, but clone creates independent data.)
    }

    #[test]
    fn test_hash() {
        use std::collections::hash_map::DefaultHasher;
        let a = APInt::from_u64(64, 42);
        let b = APInt::from_u64(64, 42);
        let c = APInt::from_u64(64, 99);
        let mut ha = DefaultHasher::new();
        let mut hb = DefaultHasher::new();
        let mut hc = DefaultHasher::new();
        a.hash(&mut ha);
        b.hash(&mut hb);
        c.hash(&mut hc);
        assert_eq!(ha.finish(), hb.finish());
        assert_ne!(ha.finish(), hc.finish());
    }

    // =======================================================================
    // Edge case tests
    // =======================================================================

    #[test]
    fn test_1bit_values() {
        let zero = APInt::new(1, 0, false);
        let one = APInt::new(1, 1, false);
        assert!(zero.is_zero());
        assert!(one.is_one());
        // 1-bit: bit 0 is also the sign bit.
        // In 1-bit, 1 represents both unsigned 1 and signed -1.
        assert!(one.is_negative()); // sign bit IS the only bit
        assert_eq!(zero.add(&one).to_u64(), Some(1));
        assert_eq!(one.add(&one).to_u64(), Some(0)); // 1+1 = 0 (mod 2)
        assert_eq!(one.negate().to_u64(), Some(1)); // -1 ≡ 1 (mod 2)
    }

    #[test]
    fn test_33bit() {
        // 1 << 32 = bit 32 set (in word 0 for 33-bit width, which fits in 1 word).
        let a = APInt::from_u64(33, 1).shl(32);
        assert_eq!(a.words.len(), 1);
        assert_eq!(a.words[0], 1u64 << 32);
        // Verify clear_unused_bits doesn't destroy.
        let b = APInt::from_u64(33, u64::MAX);
        // 33 bits: word 0 uses all 33 bits, the rest (bits 33..63) should be zero.
        assert_eq!(b.words[0] & ((1u64 << 33) - 1), (1u64 << 33) - 1);
        assert_eq!(b.words[0] >> 33, 0); // upper bits zero
    }

    #[test]
    fn test_128bit_add() {
        let a = APInt::from_u64(128, u64::MAX);
        let b = APInt::from_u64(128, 1);
        let sum = a.add(&b);
        // Low word wraps to 0, carry into high word.
        assert_eq!(sum.words[0], 0);
        assert_eq!(sum.words[1], 1);
    }

    #[test]
    fn test_128bit_mul() {
        // (2^64 - 1) * 2 = 2^65 - 2
        let a = APInt::from_u64(128, u64::MAX);
        let b = APInt::from_u64(128, 2);
        let prod = a.mul(&b);
        assert_eq!(prod.words[0], u64::MAX - 1); // 0xFFFFFFFFFFFFFFFE
        assert_eq!(prod.words[1], 1);
    }

    #[test]
    fn test_256bit_ops() {
        let a = APInt::get_all_ones(256);
        let b = APInt::from_u64(256, 1);
        let sum = a.add(&b);
        assert!(sum.is_zero()); // all ones + 1 = 0 (wrapping)

        let zero = APInt::get_zero(256);
        let all_ones = APInt::get_all_ones(256);
        assert!(all_ones.and(&zero).is_zero());
        assert!(all_ones.or(&zero).is_all_ones());
    }

    #[test]
    fn test_1024bit_basic() {
        let a = APInt::from_u64(1024, 42);
        assert_eq!(a.to_u64(), Some(42));
        let shifted = a.shl(1000);
        assert_eq!(
            shifted.count_leading_zeros(),
            1024 - 1000 - 6 /* for 42 */
        );
    }

    #[test]
    fn test_mul_overflow_65bit() {
        let a = APInt::from_u64(65, 1u64 << 63);
        let b = APInt::from_u64(65, 2);
        let (_result, overflow) = a.mul_overflow(&b);
        // (2^63) * 2 = 2^64, which fits in 65 bits with no overflow.
        assert!(!overflow);
    }

    #[test]
    fn test_sdiv_special_cases() {
        // i64::MIN / -1 overflows (since -i64::MIN > i64::MAX).
        let a = APInt::get_signed_min_value(64);
        let b = APInt::from_i64(64, -1);
        // In wrapping arithmetic, the result of sdiv is the wrapped value.
        // i64::MIN / -1 = i64::MIN (since the true quotient 2^63 overflows).
        let q = a.sdiv(&b);
        assert_eq!(q.to_i64(), Some(i64::MIN));
    }

    #[test]
    fn test_rotr_full_width() {
        let a = APInt::from_u64(8, 0x81);
        assert_eq!(a.rotr(8).to_u64(), Some(0x81)); // full rotation
        assert_eq!(a.rotl(8).to_u64(), Some(0x81)); // full rotation
    }

    #[test]
    fn test_sqrt_one() {
        assert_eq!(APInt::from_u64(8, 1).sqrt().to_u64(), Some(1));
    }

    #[test]
    fn test_sqrt_max_u64() {
        let a = APInt::from_u64(64, u64::MAX);
        let s = a.sqrt();
        // sqrt(2^64 - 1) ≈ 2^32.
        let expected = 0xFFFF_FFFFu64; // floor(sqrt(2^64-1))
        assert_eq!(s.to_u64(), Some(expected));
    }

    // =======================================================================
    // get_raw_data / get_num_words tests
    // =======================================================================

    #[test]
    fn test_get_num_words() {
        assert_eq!(APInt::from_u64(1, 1).get_num_words(), 1);
        assert_eq!(APInt::from_u64(64, 1).get_num_words(), 1);
        assert_eq!(APInt::from_u64(65, 1).get_num_words(), 2);
        assert_eq!(APInt::from_u64(128, 1).get_num_words(), 2);
        assert_eq!(APInt::from_u64(129, 1).get_num_words(), 3);
    }

    #[test]
    fn test_get_raw_data() {
        let a = APInt::from_u64(128, 0xDEADBEEF);
        let raw = a.get_raw_data();
        assert_eq!(raw[0], 0xDEADBEEF);
        assert_eq!(raw[1], 0);
    }

    // =======================================================================
    // Edge cases for clear_unused_bits / normalize
    // =======================================================================

    #[test]
    fn test_clear_unused_bits_65bit() {
        let mut a = APInt {
            bit_width: 65,
            words: vec![u64::MAX, u64::MAX],
        };
        a.clear_unused_bits();
        // Only bit 0 of word 1 should survive.
        assert_eq!(a.words[0], u64::MAX);
        assert_eq!(a.words[1], 1);
    }

    #[test]
    fn test_clear_unused_bits_64bit() {
        let mut a = APInt {
            bit_width: 64,
            words: vec![u64::MAX],
        };
        a.clear_unused_bits();
        // All 64 bits used.
        assert_eq!(a.words[0], u64::MAX);
    }

    #[test]
    fn test_normalize_leading_zeros() {
        // bit_width=128 requires 2 words.  normalize should keep 2 words
        // even when the upper word is zero.
        let mut a = APInt {
            bit_width: 128,
            words: vec![42, 0, 0],
        };
        a.normalize();
        // Excess zero words beyond minimum are removed; minimum (2) is kept.
        assert_eq!(a.words.len(), 2);
        assert_eq!(a.words[0], 42);
        assert_eq!(a.words[1], 0);
    }

    #[test]
    fn test_normalize_keeps_nonzero() {
        let mut a = APInt {
            bit_width: 128,
            words: vec![42, 1],
        };
        a.normalize();
        assert_eq!(a.words.len(), 2);
    }

    #[test]
    fn test_ensure_width_compatible_panics() {
        let a = APInt::from_u64(64, 5);
        let b = APInt::from_u64(32, 5);
        // This should panic; we test by checking that it does not silently succeed.
        let result = std::panic::catch_unwind(|| {
            a.add(&b);
        });
        assert!(result.is_err());
    }

    // =======================================================================
    // is_strictly_positive tests
    // =======================================================================

    #[test]
    fn test_is_strictly_positive() {
        assert!(APInt::from_u64(64, 1).is_strictly_positive());
        assert!(APInt::from_u64(64, 42).is_strictly_positive());
        assert!(!APInt::from_u64(64, 0).is_strictly_positive());
        assert!(!APInt::from_i64(64, -1).is_strictly_positive());
    }

    // =======================================================================
    // Round-trip and consistency tests
    // =======================================================================

    #[test]
    fn test_add_sub_identity() {
        let a = APInt::from_u64(64, 12345);
        let b = APInt::from_u64(64, 6789);
        let sum = a.add(&b);
        let diff = sum.sub(&b);
        assert_eq!(a, diff);
    }

    #[test]
    fn test_mul_div_identity() {
        let a = APInt::from_u64(64, 12345);
        let b = APInt::from_u64(64, 73);
        let prod = a.mul(&b);
        let quot = prod.udiv(&b);
        assert_eq!(a, quot);
    }

    #[test]
    fn test_shl_lshr_identity() {
        // shl + lshr is identity only when top bits are not shifted out.
        let a = APInt::from_u64(64, 0x000056789ABCDEF0);
        assert_eq!(a.shl(16).lshr(16), a);
    }

    #[test]
    fn test_trunc_sext_identity() {
        // Truncating to smaller width then sign-extending back may not be identity
        // if the value was too large. But for fitting values it should work.
        let a = APInt::from_i64(64, 42);
        let t = a.trunc(16);
        let s = t.sext(64);
        assert_eq!(a, s);
    }

    #[test]
    fn test_trunc_zext_identity() {
        let a = APInt::from_u64(64, 0xABCD);
        let t = a.trunc(16);
        let z = t.zext(64);
        assert_eq!(a, z);
    }

    #[test]
    fn test_negate_twice() {
        let a = APInt::from_i64(64, 42);
        assert_eq!(a.negate().negate(), a);
        // Also for min value (where negate wraps).
        let min = APInt::get_signed_min_value(64);
        assert_eq!(min.negate().negate(), min);
    }

    #[test]
    fn test_bitwise_not_twice() {
        let a = APInt::from_u64(64, 0xDEADBEEF);
        assert_eq!(APInt::not(&APInt::not(&a)), a);
    }

    // =======================================================================
    // Display test for negative values
    // =======================================================================

    #[test]
    fn test_display_negative() {
        let a = APInt::from_i64(64, -42);
        // Display prints unsigned, so this would be 2^64 - 42.
        let s = format!("{}", a);
        assert!(!s.starts_with('-'));
        assert!(s.parse::<u128>().unwrap() > 0);
    }

    // =======================================================================
    // from_string radix auto-detect
    // =======================================================================

    #[test]
    fn test_from_string_auto_radix_decimal() {
        let a = APInt::from_string("42", 0).unwrap();
        assert_eq!(a.to_u64(), Some(42));
    }

    #[test]
    fn test_from_string_auto_radix_hex() {
        let a = APInt::from_string("0x2A", 0).unwrap();
        assert_eq!(a.to_u64(), Some(42));
    }

    #[test]
    fn test_from_string_auto_radix_binary() {
        let a = APInt::from_string("0b101010", 0).unwrap();
        assert_eq!(a.to_u64(), Some(42));
    }

    #[test]
    fn test_from_string_radix_16_explicit() {
        let a = APInt::from_string("0xFF", 16).unwrap();
        assert_eq!(a.to_u64(), Some(255));
    }

    #[test]
    fn test_to_string_radices() {
        let a = APInt::from_u64(64, 42);
        assert_eq!(a.to_string(2, false), "101010");
        assert_eq!(a.to_string(8, false), "52");
        assert_eq!(a.to_string(10, false), "42");
        assert_eq!(a.to_string(16, false), "2a");
    }

    #[test]
    fn test_to_string_signed() {
        let a = APInt::from_i64(64, -42);
        assert_eq!(a.to_string(10, true), "-42");
    }

    // =======================================================================
    // from_string leading zeros and whitespace
    // =======================================================================

    #[test]
    fn test_from_string_leading_zeros() {
        let a = APInt::from_string("00042", 10).unwrap();
        assert_eq!(a.to_u64(), Some(42));
    }

    // =======================================================================
    // Large division test
    // =======================================================================

    #[test]
    fn test_udiv_128bit() {
        // (2^128 - 1) / 3
        let a = APInt::get_all_ones(128);
        let b = APInt::from_u64(128, 3);
        let q = a.udiv(&b);
        // (2^128-1)/3 = 0x5555...5555 (128 bits of alternating 0/1).
        // In words: [0x5555555555555555, 0x5555555555555555]
        let mut expected_words = vec![0x5555555555555555u64; 2];
        expected_words[1] &= last_word_mask(128); // 128 is multiple of 64, so full mask.
        let expected = APInt {
            bit_width: 128,
            words: expected_words,
        };
        assert_eq!(q, expected);
    }

    #[test]
    fn test_urem_128bit() {
        let a = APInt::get_all_ones(128);
        let b = APInt::from_u64(128, 3);
        let r = a.urem(&b);
        // (2^128 - 1) % 3 = 0 (since 2^128 ≡ 1 mod 3, so 2^128-1 ≡ 0 mod 3)
        assert!(r.is_zero());
    }

    // =======================================================================
    // test mul_overflow with 1-bit edge case
    // =======================================================================

    #[test]
    fn test_mul_overflow_1bit() {
        let a = APInt::new(1, 1, false);
        let b = APInt::new(1, 1, false);
        let (_result, overflow) = a.mul_overflow(&b);
        // 1 * 1 = 1, no overflow.
        assert!(!overflow);
    }

    #[test]
    fn test_smul_overflow_32bit() {
        let a = APInt::from_i64(32, i32::MAX as i64);
        let b = APInt::from_i64(32, 2);
        let (_result, overflow) = a.smul_overflow(&b);
        assert!(overflow);
    }
}