num_bigint/

bigint.rs

#[allow(deprecated, unused_imports)]
use std::ascii::AsciiExt;
use std::cmp::Ordering::{self, Equal, Greater, Less};
use std::default::Default;
use std::fmt;
use std::iter::{Product, Sum};
use std::mem;
use std::ops::{
    Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div, DivAssign,
    Mul, MulAssign, Neg, Not, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub, SubAssign,
};
use std::str::{self, FromStr};
#[cfg(has_i128)]
use std::{i128, u128};
use std::{i64, u64};

#[cfg(feature = "serde")]
use serde;

use integer::{Integer, Roots};
use traits::{
    CheckedAdd, CheckedDiv, CheckedMul, CheckedSub, FromPrimitive, Num, One, Pow, Signed,
    ToPrimitive, Zero,
};

use self::Sign::{Minus, NoSign, Plus};

use super::ParseBigIntError;
use big_digit::{self, BigDigit, DoubleBigDigit};
use biguint;
use biguint::to_str_radix_reversed;
use biguint::{BigUint, IntDigits};

use IsizePromotion;
use UsizePromotion;

#[cfg(feature = "quickcheck")]
use quickcheck::{Arbitrary, Gen};

/// A Sign is a `BigInt`'s composing element.
#[derive(PartialEq, PartialOrd, Eq, Ord, Copy, Clone, Debug, Hash)]
pub enum Sign {
    Minus,
    NoSign,
    Plus,
}

impl Neg for Sign {
    type Output = Sign;

    /// Negate Sign value.
    #[inline]
    fn neg(self) -> Sign {
        match self {
            Minus => Plus,
            NoSign => NoSign,
            Plus => Minus,
        }
    }
}

impl Mul<Sign> for Sign {
    type Output = Sign;

    #[inline]
    fn mul(self, other: Sign) -> Sign {
        match (self, other) {
            (NoSign, _) | (_, NoSign) => NoSign,
            (Plus, Plus) | (Minus, Minus) => Plus,
            (Plus, Minus) | (Minus, Plus) => Minus,
        }
    }
}

#[cfg(feature = "serde")]
impl serde::Serialize for Sign {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: serde::Serializer,
    {
        // Note: do not change the serialization format, or it may break
        // forward and backward compatibility of serialized data!
        match *self {
            Sign::Minus => (-1i8).serialize(serializer),
            Sign::NoSign => 0i8.serialize(serializer),
            Sign::Plus => 1i8.serialize(serializer),
        }
    }
}

#[cfg(feature = "serde")]
impl<'de> serde::Deserialize<'de> for Sign {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        use serde::de::Error;
        use serde::de::Unexpected;

        let sign: i8 = serde::Deserialize::deserialize(deserializer)?;
        match sign {
            -1 => Ok(Sign::Minus),
            0 => Ok(Sign::NoSign),
            1 => Ok(Sign::Plus),
            _ => Err(D::Error::invalid_value(
                Unexpected::Signed(sign.into()),
                &"a sign of -1, 0, or 1",
            )),
        }
    }
}

/// A big signed integer type.
#[derive(Clone, Debug, Hash)]
pub struct BigInt {
    sign: Sign,
    data: BigUint,
}

#[cfg(feature = "quickcheck")]
impl Arbitrary for BigInt {
    fn arbitrary<G: Gen>(g: &mut G) -> Self {
        let positive = bool::arbitrary(g);
        let sign = if positive { Sign::Plus } else { Sign::Minus };
        Self::from_biguint(sign, BigUint::arbitrary(g))
    }

    #[allow(bare_trait_objects)] // `dyn` needs Rust 1.27 to parse, even when cfg-disabled
    fn shrink(&self) -> Box<Iterator<Item = Self>> {
        let sign = self.sign();
        let unsigned_shrink = self.data.shrink();
        Box::new(unsigned_shrink.map(move |x| BigInt::from_biguint(sign, x)))
    }
}

/// Return the magnitude of a `BigInt`.
///
/// This is in a private module, pseudo pub(crate)
#[cfg(feature = "rand")]
pub fn magnitude(i: &BigInt) -> &BigUint {
    &i.data
}

/// Return the owned magnitude of a `BigInt`.
///
/// This is in a private module, pseudo pub(crate)
#[cfg(feature = "rand")]
pub fn into_magnitude(i: BigInt) -> BigUint {
    i.data
}

impl PartialEq for BigInt {
    #[inline]
    fn eq(&self, other: &BigInt) -> bool {
        self.cmp(other) == Equal
    }
}

impl Eq for BigInt {}

impl PartialOrd for BigInt {
    #[inline]
    fn partial_cmp(&self, other: &BigInt) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for BigInt {
    #[inline]
    fn cmp(&self, other: &BigInt) -> Ordering {
        let scmp = self.sign.cmp(&other.sign);
        if scmp != Equal {
            return scmp;
        }

        match self.sign {
            NoSign => Equal,
            Plus => self.data.cmp(&other.data),
            Minus => other.data.cmp(&self.data),
        }
    }
}

impl Default for BigInt {
    #[inline]
    fn default() -> BigInt {
        Zero::zero()
    }
}

impl fmt::Display for BigInt {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.pad_integral(!self.is_negative(), "", &self.data.to_str_radix(10))
    }
}

impl fmt::Binary for BigInt {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.pad_integral(!self.is_negative(), "0b", &self.data.to_str_radix(2))
    }
}

impl fmt::Octal for BigInt {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.pad_integral(!self.is_negative(), "0o", &self.data.to_str_radix(8))
    }
}

impl fmt::LowerHex for BigInt {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.pad_integral(!self.is_negative(), "0x", &self.data.to_str_radix(16))
    }
}

impl fmt::UpperHex for BigInt {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut s = self.data.to_str_radix(16);
        s.make_ascii_uppercase();
        f.pad_integral(!self.is_negative(), "0x", &s)
    }
}

// Negation in two's complement.
// acc must be initialized as 1 for least-significant digit.
//
// When negating, a carry (acc == 1) means that all the digits
// considered to this point were zero. This means that if all the
// digits of a negative BigInt have been considered, carry must be
// zero as we cannot have negative zero.
//
//    01 -> ...f    ff
//    ff -> ...f    01
// 01 00 -> ...f ff 00
// 01 01 -> ...f fe ff
// 01 ff -> ...f fe 01
// ff 00 -> ...f 01 00
// ff 01 -> ...f 00 ff
// ff ff -> ...f 00 01
#[inline]
fn negate_carry(a: BigDigit, acc: &mut DoubleBigDigit) -> BigDigit {
    *acc += DoubleBigDigit::from(!a);
    let lo = *acc as BigDigit;
    *acc >>= big_digit::BITS;
    lo
}

// !-2 = !...f fe = ...0 01 = +1
// !-1 = !...f ff = ...0 00 =  0
// ! 0 = !...0 00 = ...f ff = -1
// !+1 = !...0 01 = ...f fe = -2
impl Not for BigInt {
    type Output = BigInt;

    fn not(mut self) -> BigInt {
        match self.sign {
            NoSign | Plus => {
                self.data += 1u32;
                self.sign = Minus;
            }
            Minus => {
                self.data -= 1u32;
                self.sign = if self.data.is_zero() { NoSign } else { Plus };
            }
        }
        self
    }
}

impl<'a> Not for &'a BigInt {
    type Output = BigInt;

    fn not(self) -> BigInt {
        match self.sign {
            NoSign | Plus => BigInt::from_biguint(Minus, &self.data + 1u32),
            Minus => BigInt::from_biguint(Plus, &self.data - 1u32),
        }
    }
}

// + 1 & -ff = ...0 01 & ...f 01 = ...0 01 = + 1
// +ff & - 1 = ...0 ff & ...f ff = ...0 ff = +ff
// answer is pos, has length of a
fn bitand_pos_neg(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
    let mut carry_b = 1;
    for (ai, &bi) in a.iter_mut().zip(b.iter()) {
        let twos_b = negate_carry(bi, &mut carry_b);
        *ai &= twos_b;
    }
    debug_assert!(b.len() > a.len() || carry_b == 0);
}

// - 1 & +ff = ...f ff & ...0 ff = ...0 ff = +ff
// -ff & + 1 = ...f 01 & ...0 01 = ...0 01 = + 1
// answer is pos, has length of b
fn bitand_neg_pos(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
    let mut carry_a = 1;
    for (ai, &bi) in a.iter_mut().zip(b.iter()) {
        let twos_a = negate_carry(*ai, &mut carry_a);
        *ai = twos_a & bi;
    }
    debug_assert!(a.len() > b.len() || carry_a == 0);
    if a.len() > b.len() {
        a.truncate(b.len());
    } else if b.len() > a.len() {
        let extra = &b[a.len()..];
        a.extend(extra.iter().cloned());
    }
}

// - 1 & -ff = ...f ff & ...f 01 = ...f 01 = - ff
// -ff & - 1 = ...f 01 & ...f ff = ...f 01 = - ff
// -ff & -fe = ...f 01 & ...f 02 = ...f 00 = -100
// answer is neg, has length of longest with a possible carry
fn bitand_neg_neg(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
    let mut carry_a = 1;
    let mut carry_b = 1;
    let mut carry_and = 1;
    for (ai, &bi) in a.iter_mut().zip(b.iter()) {
        let twos_a = negate_carry(*ai, &mut carry_a);
        let twos_b = negate_carry(bi, &mut carry_b);
        *ai = negate_carry(twos_a & twos_b, &mut carry_and);
    }
    debug_assert!(a.len() > b.len() || carry_a == 0);
    debug_assert!(b.len() > a.len() || carry_b == 0);
    if a.len() > b.len() {
        for ai in a[b.len()..].iter_mut() {
            let twos_a = negate_carry(*ai, &mut carry_a);
            *ai = negate_carry(twos_a, &mut carry_and);
        }
        debug_assert!(carry_a == 0);
    } else if b.len() > a.len() {
        let extra = &b[a.len()..];
        a.extend(extra.iter().map(|&bi| {
            let twos_b = negate_carry(bi, &mut carry_b);
            negate_carry(twos_b, &mut carry_and)
        }));
        debug_assert!(carry_b == 0);
    }
    if carry_and != 0 {
        a.push(1);
    }
}

forward_val_val_binop!(impl BitAnd for BigInt, bitand);
forward_ref_val_binop!(impl BitAnd for BigInt, bitand);

// do not use forward_ref_ref_binop_commutative! for bitand so that we can
// clone as needed, avoiding over-allocation
impl<'a, 'b> BitAnd<&'b BigInt> for &'a BigInt {
    type Output = BigInt;

    #[inline]
    fn bitand(self, other: &BigInt) -> BigInt {
        match (self.sign, other.sign) {
            (NoSign, _) | (_, NoSign) => BigInt::from_slice(NoSign, &[]),
            (Plus, Plus) => BigInt::from_biguint(Plus, &self.data & &other.data),
            (Plus, Minus) => self.clone() & other,
            (Minus, Plus) => other.clone() & self,
            (Minus, Minus) => {
                // forward to val-ref, choosing the larger to clone
                if self.len() >= other.len() {
                    self.clone() & other
                } else {
                    other.clone() & self
                }
            }
        }
    }
}

impl<'a> BitAnd<&'a BigInt> for BigInt {
    type Output = BigInt;

    #[inline]
    fn bitand(mut self, other: &BigInt) -> BigInt {
        self &= other;
        self
    }
}

forward_val_assign!(impl BitAndAssign for BigInt, bitand_assign);

impl<'a> BitAndAssign<&'a BigInt> for BigInt {
    fn bitand_assign(&mut self, other: &BigInt) {
        match (self.sign, other.sign) {
            (NoSign, _) => {}
            (_, NoSign) => self.assign_from_slice(NoSign, &[]),
            (Plus, Plus) => {
                self.data &= &other.data;
                if self.data.is_zero() {
                    self.sign = NoSign;
                }
            }
            (Plus, Minus) => {
                bitand_pos_neg(self.digits_mut(), other.digits());
                self.normalize();
            }
            (Minus, Plus) => {
                bitand_neg_pos(self.digits_mut(), other.digits());
                self.sign = Plus;
                self.normalize();
            }
            (Minus, Minus) => {
                bitand_neg_neg(self.digits_mut(), other.digits());
                self.normalize();
            }
        }
    }
}

// + 1 | -ff = ...0 01 | ...f 01 = ...f 01 = -ff
// +ff | - 1 = ...0 ff | ...f ff = ...f ff = - 1
// answer is neg, has length of b
fn bitor_pos_neg(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
    let mut carry_b = 1;
    let mut carry_or = 1;
    for (ai, &bi) in a.iter_mut().zip(b.iter()) {
        let twos_b = negate_carry(bi, &mut carry_b);
        *ai = negate_carry(*ai | twos_b, &mut carry_or);
    }
    debug_assert!(b.len() > a.len() || carry_b == 0);
    if a.len() > b.len() {
        a.truncate(b.len());
    } else if b.len() > a.len() {
        let extra = &b[a.len()..];
        a.extend(extra.iter().map(|&bi| {
            let twos_b = negate_carry(bi, &mut carry_b);
            negate_carry(twos_b, &mut carry_or)
        }));
        debug_assert!(carry_b == 0);
    }
    // for carry_or to be non-zero, we would need twos_b == 0
    debug_assert!(carry_or == 0);
}

// - 1 | +ff = ...f ff | ...0 ff = ...f ff = - 1
// -ff | + 1 = ...f 01 | ...0 01 = ...f 01 = -ff
// answer is neg, has length of a
fn bitor_neg_pos(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
    let mut carry_a = 1;
    let mut carry_or = 1;
    for (ai, &bi) in a.iter_mut().zip(b.iter()) {
        let twos_a = negate_carry(*ai, &mut carry_a);
        *ai = negate_carry(twos_a | bi, &mut carry_or);
    }
    debug_assert!(a.len() > b.len() || carry_a == 0);
    if a.len() > b.len() {
        for ai in a[b.len()..].iter_mut() {
            let twos_a = negate_carry(*ai, &mut carry_a);
            *ai = negate_carry(twos_a, &mut carry_or);
        }
        debug_assert!(carry_a == 0);
    }
    // for carry_or to be non-zero, we would need twos_a == 0
    debug_assert!(carry_or == 0);
}

// - 1 | -ff = ...f ff | ...f 01 = ...f ff = -1
// -ff | - 1 = ...f 01 | ...f ff = ...f ff = -1
// answer is neg, has length of shortest
fn bitor_neg_neg(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
    let mut carry_a = 1;
    let mut carry_b = 1;
    let mut carry_or = 1;
    for (ai, &bi) in a.iter_mut().zip(b.iter()) {
        let twos_a = negate_carry(*ai, &mut carry_a);
        let twos_b = negate_carry(bi, &mut carry_b);
        *ai = negate_carry(twos_a | twos_b, &mut carry_or);
    }
    debug_assert!(a.len() > b.len() || carry_a == 0);
    debug_assert!(b.len() > a.len() || carry_b == 0);
    if a.len() > b.len() {
        a.truncate(b.len());
    }
    // for carry_or to be non-zero, we would need twos_a == 0 or twos_b == 0
    debug_assert!(carry_or == 0);
}

forward_val_val_binop!(impl BitOr for BigInt, bitor);
forward_ref_val_binop!(impl BitOr for BigInt, bitor);

// do not use forward_ref_ref_binop_commutative! for bitor so that we can
// clone as needed, avoiding over-allocation
impl<'a, 'b> BitOr<&'b BigInt> for &'a BigInt {
    type Output = BigInt;

    #[inline]
    fn bitor(self, other: &BigInt) -> BigInt {
        match (self.sign, other.sign) {
            (NoSign, _) => other.clone(),
            (_, NoSign) => self.clone(),
            (Plus, Plus) => BigInt::from_biguint(Plus, &self.data | &other.data),
            (Plus, Minus) => other.clone() | self,
            (Minus, Plus) => self.clone() | other,
            (Minus, Minus) => {
                // forward to val-ref, choosing the smaller to clone
                if self.len() <= other.len() {
                    self.clone() | other
                } else {
                    other.clone() | self
                }
            }
        }
    }
}

impl<'a> BitOr<&'a BigInt> for BigInt {
    type Output = BigInt;

    #[inline]
    fn bitor(mut self, other: &BigInt) -> BigInt {
        self |= other;
        self
    }
}

forward_val_assign!(impl BitOrAssign for BigInt, bitor_assign);

impl<'a> BitOrAssign<&'a BigInt> for BigInt {
    fn bitor_assign(&mut self, other: &BigInt) {
        match (self.sign, other.sign) {
            (_, NoSign) => {}
            (NoSign, _) => self.assign_from_slice(other.sign, other.digits()),
            (Plus, Plus) => self.data |= &other.data,
            (Plus, Minus) => {
                bitor_pos_neg(self.digits_mut(), other.digits());
                self.sign = Minus;
                self.normalize();
            }
            (Minus, Plus) => {
                bitor_neg_pos(self.digits_mut(), other.digits());
                self.normalize();
            }
            (Minus, Minus) => {
                bitor_neg_neg(self.digits_mut(), other.digits());
                self.normalize();
            }
        }
    }
}

// + 1 ^ -ff = ...0 01 ^ ...f 01 = ...f 00 = -100
// +ff ^ - 1 = ...0 ff ^ ...f ff = ...f 00 = -100
// answer is neg, has length of longest with a possible carry
fn bitxor_pos_neg(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
    let mut carry_b = 1;
    let mut carry_xor = 1;
    for (ai, &bi) in a.iter_mut().zip(b.iter()) {
        let twos_b = negate_carry(bi, &mut carry_b);
        *ai = negate_carry(*ai ^ twos_b, &mut carry_xor);
    }
    debug_assert!(b.len() > a.len() || carry_b == 0);
    if a.len() > b.len() {
        for ai in a[b.len()..].iter_mut() {
            let twos_b = !0;
            *ai = negate_carry(*ai ^ twos_b, &mut carry_xor);
        }
    } else if b.len() > a.len() {
        let extra = &b[a.len()..];
        a.extend(extra.iter().map(|&bi| {
            let twos_b = negate_carry(bi, &mut carry_b);
            negate_carry(twos_b, &mut carry_xor)
        }));
        debug_assert!(carry_b == 0);
    }
    if carry_xor != 0 {
        a.push(1);
    }
}

// - 1 ^ +ff = ...f ff ^ ...0 ff = ...f 00 = -100
// -ff ^ + 1 = ...f 01 ^ ...0 01 = ...f 00 = -100
// answer is neg, has length of longest with a possible carry
fn bitxor_neg_pos(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
    let mut carry_a = 1;
    let mut carry_xor = 1;
    for (ai, &bi) in a.iter_mut().zip(b.iter()) {
        let twos_a = negate_carry(*ai, &mut carry_a);
        *ai = negate_carry(twos_a ^ bi, &mut carry_xor);
    }
    debug_assert!(a.len() > b.len() || carry_a == 0);
    if a.len() > b.len() {
        for ai in a[b.len()..].iter_mut() {
            let twos_a = negate_carry(*ai, &mut carry_a);
            *ai = negate_carry(twos_a, &mut carry_xor);
        }
        debug_assert!(carry_a == 0);
    } else if b.len() > a.len() {
        let extra = &b[a.len()..];
        a.extend(extra.iter().map(|&bi| {
            let twos_a = !0;
            negate_carry(twos_a ^ bi, &mut carry_xor)
        }));
    }
    if carry_xor != 0 {
        a.push(1);
    }
}

// - 1 ^ -ff = ...f ff ^ ...f 01 = ...0 fe = +fe
// -ff & - 1 = ...f 01 ^ ...f ff = ...0 fe = +fe
// answer is pos, has length of longest
fn bitxor_neg_neg(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
    let mut carry_a = 1;
    let mut carry_b = 1;
    for (ai, &bi) in a.iter_mut().zip(b.iter()) {
        let twos_a = negate_carry(*ai, &mut carry_a);
        let twos_b = negate_carry(bi, &mut carry_b);
        *ai = twos_a ^ twos_b;
    }
    debug_assert!(a.len() > b.len() || carry_a == 0);
    debug_assert!(b.len() > a.len() || carry_b == 0);
    if a.len() > b.len() {
        for ai in a[b.len()..].iter_mut() {
            let twos_a = negate_carry(*ai, &mut carry_a);
            let twos_b = !0;
            *ai = twos_a ^ twos_b;
        }
        debug_assert!(carry_a == 0);
    } else if b.len() > a.len() {
        let extra = &b[a.len()..];
        a.extend(extra.iter().map(|&bi| {
            let twos_a = !0;
            let twos_b = negate_carry(bi, &mut carry_b);
            twos_a ^ twos_b
        }));
        debug_assert!(carry_b == 0);
    }
}

forward_all_binop_to_val_ref_commutative!(impl BitXor for BigInt, bitxor);

impl<'a> BitXor<&'a BigInt> for BigInt {
    type Output = BigInt;

    #[inline]
    fn bitxor(mut self, other: &BigInt) -> BigInt {
        self ^= other;
        self
    }
}

forward_val_assign!(impl BitXorAssign for BigInt, bitxor_assign);

impl<'a> BitXorAssign<&'a BigInt> for BigInt {
    fn bitxor_assign(&mut self, other: &BigInt) {
        match (self.sign, other.sign) {
            (_, NoSign) => {}
            (NoSign, _) => self.assign_from_slice(other.sign, other.digits()),
            (Plus, Plus) => {
                self.data ^= &other.data;
                if self.data.is_zero() {
                    self.sign = NoSign;
                }
            }
            (Plus, Minus) => {
                bitxor_pos_neg(self.digits_mut(), other.digits());
                self.sign = Minus;
                self.normalize();
            }
            (Minus, Plus) => {
                bitxor_neg_pos(self.digits_mut(), other.digits());
                self.normalize();
            }
            (Minus, Minus) => {
                bitxor_neg_neg(self.digits_mut(), other.digits());
                self.sign = Plus;
                self.normalize();
            }
        }
    }
}

impl FromStr for BigInt {
    type Err = ParseBigIntError;

    #[inline]
    fn from_str(s: &str) -> Result<BigInt, ParseBigIntError> {
        BigInt::from_str_radix(s, 10)
    }
}

impl Num for BigInt {
    type FromStrRadixErr = ParseBigIntError;

    /// Creates and initializes a BigInt.
    #[inline]
    fn from_str_radix(mut s: &str, radix: u32) -> Result<BigInt, ParseBigIntError> {
        let sign = if s.starts_with('-') {
            let tail = &s[1..];
            if !tail.starts_with('+') {
                s = tail
            }
            Minus
        } else {
            Plus
        };
        let bu = BigUint::from_str_radix(s, radix)?;
        Ok(BigInt::from_biguint(sign, bu))
    }
}

impl Shl<usize> for BigInt {
    type Output = BigInt;

    #[inline]
    fn shl(mut self, rhs: usize) -> BigInt {
        self <<= rhs;
        self
    }
}

impl<'a> Shl<usize> for &'a BigInt {
    type Output = BigInt;

    #[inline]
    fn shl(self, rhs: usize) -> BigInt {
        BigInt::from_biguint(self.sign, &self.data << rhs)
    }
}

impl ShlAssign<usize> for BigInt {
    #[inline]
    fn shl_assign(&mut self, rhs: usize) {
        self.data <<= rhs;
    }
}

// Negative values need a rounding adjustment if there are any ones in the
// bits that are getting shifted out.
fn shr_round_down(i: &BigInt, rhs: usize) -> bool {
    i.is_negative()
        && biguint::trailing_zeros(&i.data)
            .map(|n| n < rhs)
            .unwrap_or(false)
}

impl Shr<usize> for BigInt {
    type Output = BigInt;

    #[inline]
    fn shr(mut self, rhs: usize) -> BigInt {
        self >>= rhs;
        self
    }
}

impl<'a> Shr<usize> for &'a BigInt {
    type Output = BigInt;

    #[inline]
    fn shr(self, rhs: usize) -> BigInt {
        let round_down = shr_round_down(self, rhs);
        let data = &self.data >> rhs;
        BigInt::from_biguint(self.sign, if round_down { data + 1u8 } else { data })
    }
}

impl ShrAssign<usize> for BigInt {
    #[inline]
    fn shr_assign(&mut self, rhs: usize) {
        let round_down = shr_round_down(self, rhs);
        self.data >>= rhs;
        if round_down {
            self.data += 1u8;
        } else if self.data.is_zero() {
            self.sign = NoSign;
        }
    }
}

impl Zero for BigInt {
    #[inline]
    fn zero() -> BigInt {
        BigInt::from_biguint(NoSign, Zero::zero())
    }

    #[inline]
    fn set_zero(&mut self) {
        self.data.set_zero();
        self.sign = NoSign;
    }

    #[inline]
    fn is_zero(&self) -> bool {
        self.sign == NoSign
    }
}

impl One for BigInt {
    #[inline]
    fn one() -> BigInt {
        BigInt::from_biguint(Plus, One::one())
    }

    #[inline]
    fn set_one(&mut self) {
        self.data.set_one();
        self.sign = Plus;
    }

    #[inline]
    fn is_one(&self) -> bool {
        self.sign == Plus && self.data.is_one()
    }
}

impl Signed for BigInt {
    #[inline]
    fn abs(&self) -> BigInt {
        match self.sign {
            Plus | NoSign => self.clone(),
            Minus => BigInt::from_biguint(Plus, self.data.clone()),
        }
    }

    #[inline]
    fn abs_sub(&self, other: &BigInt) -> BigInt {
        if *self <= *other {
            Zero::zero()
        } else {
            self - other
        }
    }

    #[inline]
    fn signum(&self) -> BigInt {
        match self.sign {
            Plus => BigInt::from_biguint(Plus, One::one()),
            Minus => BigInt::from_biguint(Minus, One::one()),
            NoSign => Zero::zero(),
        }
    }

    #[inline]
    fn is_positive(&self) -> bool {
        self.sign == Plus
    }

    #[inline]
    fn is_negative(&self) -> bool {
        self.sign == Minus
    }
}

/// Help function for pow
///
/// Computes the effect of the exponent on the sign.
#[inline]
fn powsign<T: Integer>(sign: Sign, other: &T) -> Sign {
    if other.is_zero() {
        Plus
    } else if sign != Minus {
        sign
    } else if other.is_odd() {
        sign
    } else {
        -sign
    }
}

macro_rules! pow_impl {
    ($T:ty) => {
        impl<'a> Pow<$T> for &'a BigInt {
            type Output = BigInt;

            #[inline]
            fn pow(self, rhs: $T) -> BigInt {
                BigInt::from_biguint(powsign(self.sign, &rhs), (&self.data).pow(rhs))
            }
        }

        impl<'a, 'b> Pow<&'b $T> for &'a BigInt {
            type Output = BigInt;

            #[inline]
            fn pow(self, rhs: &$T) -> BigInt {
                BigInt::from_biguint(powsign(self.sign, rhs), (&self.data).pow(rhs))
            }
        }
    };
}

pow_impl!(u8);
pow_impl!(u16);
pow_impl!(u32);
pow_impl!(u64);
pow_impl!(usize);
#[cfg(has_i128)]
pow_impl!(u128);
pow_impl!(BigUint);

// A convenience method for getting the absolute value of an i32 in a u32.
#[inline]
fn i32_abs_as_u32(a: i32) -> u32 {
    if a == i32::min_value() {
        a as u32
    } else {
        a.abs() as u32
    }
}

// A convenience method for getting the absolute value of an i64 in a u64.
#[inline]
fn i64_abs_as_u64(a: i64) -> u64 {
    if a == i64::min_value() {
        a as u64
    } else {
        a.abs() as u64
    }
}

// A convenience method for getting the absolute value of an i128 in a u128.
#[cfg(has_i128)]
#[inline]
fn i128_abs_as_u128(a: i128) -> u128 {
    if a == i128::min_value() {
        a as u128
    } else {
        a.abs() as u128
    }
}

// We want to forward to BigUint::add, but it's not clear how that will go until
// we compare both sign and magnitude.  So we duplicate this body for every
// val/ref combination, deferring that decision to BigUint's own forwarding.
macro_rules! bigint_add {
    ($a:expr, $a_owned:expr, $a_data:expr, $b:expr, $b_owned:expr, $b_data:expr) => {
        match ($a.sign, $b.sign) {
            (_, NoSign) => $a_owned,
            (NoSign, _) => $b_owned,
            // same sign => keep the sign with the sum of magnitudes
            (Plus, Plus) | (Minus, Minus) => BigInt::from_biguint($a.sign, $a_data + $b_data),
            // opposite signs => keep the sign of the larger with the difference of magnitudes
            (Plus, Minus) | (Minus, Plus) => match $a.data.cmp(&$b.data) {
                Less => BigInt::from_biguint($b.sign, $b_data - $a_data),
                Greater => BigInt::from_biguint($a.sign, $a_data - $b_data),
                Equal => Zero::zero(),
            },
        }
    };
}

impl<'a, 'b> Add<&'b BigInt> for &'a BigInt {
    type Output = BigInt;

    #[inline]
    fn add(self, other: &BigInt) -> BigInt {
        bigint_add!(
            self,
            self.clone(),
            &self.data,
            other,
            other.clone(),
            &other.data
        )
    }
}

impl<'a> Add<BigInt> for &'a BigInt {
    type Output = BigInt;

    #[inline]
    fn add(self, other: BigInt) -> BigInt {
        bigint_add!(self, self.clone(), &self.data, other, other, other.data)
    }
}

impl<'a> Add<&'a BigInt> for BigInt {
    type Output = BigInt;

    #[inline]
    fn add(self, other: &BigInt) -> BigInt {
        bigint_add!(self, self, self.data, other, other.clone(), &other.data)
    }
}

impl Add<BigInt> for BigInt {
    type Output = BigInt;

    #[inline]
    fn add(self, other: BigInt) -> BigInt {
        bigint_add!(self, self, self.data, other, other, other.data)
    }
}

impl<'a> AddAssign<&'a BigInt> for BigInt {
    #[inline]
    fn add_assign(&mut self, other: &BigInt) {
        let n = mem::replace(self, BigInt::zero());
        *self = n + other;
    }
}
forward_val_assign!(impl AddAssign for BigInt, add_assign);

promote_all_scalars!(impl Add for BigInt, add);
promote_all_scalars_assign!(impl AddAssign for BigInt, add_assign);
forward_all_scalar_binop_to_val_val_commutative!(impl Add<u32> for BigInt, add);
forward_all_scalar_binop_to_val_val_commutative!(impl Add<u64> for BigInt, add);
#[cfg(has_i128)]
forward_all_scalar_binop_to_val_val_commutative!(impl Add<u128> for BigInt, add);

impl Add<u32> for BigInt {
    type Output = BigInt;

    #[inline]
    fn add(self, other: u32) -> BigInt {
        match self.sign {
            NoSign => From::from(other),
            Plus => BigInt::from_biguint(Plus, self.data + other),
            Minus => match self.data.cmp(&From::from(other)) {
                Equal => Zero::zero(),
                Less => BigInt::from_biguint(Plus, other - self.data),
                Greater => BigInt::from_biguint(Minus, self.data - other),
            },
        }
    }
}
impl AddAssign<u32> for BigInt {
    #[inline]
    fn add_assign(&mut self, other: u32) {
        let n = mem::replace(self, BigInt::zero());
        *self = n + other;
    }
}

impl Add<u64> for BigInt {
    type Output = BigInt;

    #[inline]
    fn add(self, other: u64) -> BigInt {
        match self.sign {
            NoSign => From::from(other),
            Plus => BigInt::from_biguint(Plus, self.data + other),
            Minus => match self.data.cmp(&From::from(other)) {
                Equal => Zero::zero(),
                Less => BigInt::from_biguint(Plus, other - self.data),
                Greater => BigInt::from_biguint(Minus, self.data - other),
            },
        }
    }
}
impl AddAssign<u64> for BigInt {
    #[inline]
    fn add_assign(&mut self, other: u64) {
        let n = mem::replace(self, BigInt::zero());
        *self = n + other;
    }
}

#[cfg(has_i128)]
impl Add<u128> for BigInt {
    type Output = BigInt;

    #[inline]
    fn add(self, other: u128) -> BigInt {
        match self.sign {
            NoSign => From::from(other),
            Plus => BigInt::from_biguint(Plus, self.data + other),
            Minus => match self.data.cmp(&From::from(other)) {
                Equal => Zero::zero(),
                Less => BigInt::from_biguint(Plus, other - self.data),
                Greater => BigInt::from_biguint(Minus, self.data - other),
            },
        }
    }
}
#[cfg(has_i128)]
impl AddAssign<u128> for BigInt {
    #[inline]
    fn add_assign(&mut self, other: u128) {
        let n = mem::replace(self, BigInt::zero());
        *self = n + other;
    }
}

forward_all_scalar_binop_to_val_val_commutative!(impl Add<i32> for BigInt, add);
forward_all_scalar_binop_to_val_val_commutative!(impl Add<i64> for BigInt, add);
#[cfg(has_i128)]
forward_all_scalar_binop_to_val_val_commutative!(impl Add<i128> for BigInt, add);

impl Add<i32> for BigInt {
    type Output = BigInt;

    #[inline]
    fn add(self, other: i32) -> BigInt {
        if other >= 0 {
            self + other as u32
        } else {
            self - i32_abs_as_u32(other)
        }
    }
}
impl AddAssign<i32> for BigInt {
    #[inline]
    fn add_assign(&mut self, other: i32) {
        if other >= 0 {
            *self += other as u32;
        } else {
            *self -= i32_abs_as_u32(other);
        }
    }
}

impl Add<i64> for BigInt {
    type Output = BigInt;

    #[inline]
    fn add(self, other: i64) -> BigInt {
        if other >= 0 {
            self + other as u64
        } else {
            self - i64_abs_as_u64(other)
        }
    }
}
impl AddAssign<i64> for BigInt {
    #[inline]
    fn add_assign(&mut self, other: i64) {
        if other >= 0 {
            *self += other as u64;
        } else {
            *self -= i64_abs_as_u64(other);
        }
    }
}

#[cfg(has_i128)]
impl Add<i128> for BigInt {
    type Output = BigInt;

    #[inline]
    fn add(self, other: i128) -> BigInt {
        if other >= 0 {
            self + other as u128
        } else {
            self - i128_abs_as_u128(other)
        }
    }
}
#[cfg(has_i128)]
impl AddAssign<i128> for BigInt {
    #[inline]
    fn add_assign(&mut self, other: i128) {
        if other >= 0 {
            *self += other as u128;
        } else {
            *self -= i128_abs_as_u128(other);
        }
    }
}

// We want to forward to BigUint::sub, but it's not clear how that will go until
// we compare both sign and magnitude.  So we duplicate this body for every
// val/ref combination, deferring that decision to BigUint's own forwarding.
macro_rules! bigint_sub {
    ($a:expr, $a_owned:expr, $a_data:expr, $b:expr, $b_owned:expr, $b_data:expr) => {
        match ($a.sign, $b.sign) {
            (_, NoSign) => $a_owned,
            (NoSign, _) => -$b_owned,
            // opposite signs => keep the sign of the left with the sum of magnitudes
            (Plus, Minus) | (Minus, Plus) => BigInt::from_biguint($a.sign, $a_data + $b_data),
            // same sign => keep or toggle the sign of the left with the difference of magnitudes
            (Plus, Plus) | (Minus, Minus) => match $a.data.cmp(&$b.data) {
                Less => BigInt::from_biguint(-$a.sign, $b_data - $a_data),
                Greater => BigInt::from_biguint($a.sign, $a_data - $b_data),
                Equal => Zero::zero(),
            },
        }
    };
}

impl<'a, 'b> Sub<&'b BigInt> for &'a BigInt {
    type Output = BigInt;

    #[inline]
    fn sub(self, other: &BigInt) -> BigInt {
        bigint_sub!(
            self,
            self.clone(),
            &self.data,
            other,
            other.clone(),
            &other.data
        )
    }
}

impl<'a> Sub<BigInt> for &'a BigInt {
    type Output = BigInt;

    #[inline]
    fn sub(self, other: BigInt) -> BigInt {
        bigint_sub!(self, self.clone(), &self.data, other, other, other.data)
    }
}

impl<'a> Sub<&'a BigInt> for BigInt {
    type Output = BigInt;

    #[inline]
    fn sub(self, other: &BigInt) -> BigInt {
        bigint_sub!(self, self, self.data, other, other.clone(), &other.data)
    }
}

impl Sub<BigInt> for BigInt {
    type Output = BigInt;

    #[inline]
    fn sub(self, other: BigInt) -> BigInt {
        bigint_sub!(self, self, self.data, other, other, other.data)
    }
}

impl<'a> SubAssign<&'a BigInt> for BigInt {
    #[inline]
    fn sub_assign(&mut self, other: &BigInt) {
        let n = mem::replace(self, BigInt::zero());
        *self = n - other;
    }
}
forward_val_assign!(impl SubAssign for BigInt, sub_assign);

promote_all_scalars!(impl Sub for BigInt, sub);
promote_all_scalars_assign!(impl SubAssign for BigInt, sub_assign);
forward_all_scalar_binop_to_val_val!(impl Sub<u32> for BigInt, sub);
forward_all_scalar_binop_to_val_val!(impl Sub<u64> for BigInt, sub);
#[cfg(has_i128)]
forward_all_scalar_binop_to_val_val!(impl Sub<u128> for BigInt, sub);

impl Sub<u32> for BigInt {
    type Output = BigInt;

    #[inline]
    fn sub(self, other: u32) -> BigInt {
        match self.sign {
            NoSign => BigInt::from_biguint(Minus, From::from(other)),
            Minus => BigInt::from_biguint(Minus, self.data + other),
            Plus => match self.data.cmp(&From::from(other)) {
                Equal => Zero::zero(),
                Greater => BigInt::from_biguint(Plus, self.data - other),
                Less => BigInt::from_biguint(Minus, other - self.data),
            },
        }
    }
}
impl SubAssign<u32> for BigInt {
    #[inline]
    fn sub_assign(&mut self, other: u32) {
        let n = mem::replace(self, BigInt::zero());
        *self = n - other;
    }
}

impl Sub<BigInt> for u32 {
    type Output = BigInt;

    #[inline]
    fn sub(self, other: BigInt) -> BigInt {
        -(other - self)
    }
}

impl Sub<BigInt> for u64 {
    type Output = BigInt;

    #[inline]
    fn sub(self, other: BigInt) -> BigInt {
        -(other - self)
    }
}
#[cfg(has_i128)]
impl Sub<BigInt> for u128 {
    type Output = BigInt;

    #[inline]
    fn sub(self, other: BigInt) -> BigInt {
        -(other - self)
    }
}

impl Sub<u64> for BigInt {
    type Output = BigInt;

    #[inline]
    fn sub(self, other: u64) -> BigInt {
        match self.sign {
            NoSign => BigInt::from_biguint(Minus, From::from(other)),
            Minus => BigInt::from_biguint(Minus, self.data + other),
            Plus => match self.data.cmp(&From::from(other)) {
                Equal => Zero::zero(),
                Greater => BigInt::from_biguint(Plus, self.data - other),
                Less => BigInt::from_biguint(Minus, other - self.data),
            },
        }
    }
}
impl SubAssign<u64> for BigInt {
    #[inline]
    fn sub_assign(&mut self, other: u64) {
        let n = mem::replace(self, BigInt::zero());
        *self = n - other;
    }
}

#[cfg(has_i128)]
impl Sub<u128> for BigInt {
    type Output = BigInt;

    #[inline]
    fn sub(self, other: u128) -> BigInt {
        match self.sign {
            NoSign => BigInt::from_biguint(Minus, From::from(other)),
            Minus => BigInt::from_biguint(Minus, self.data + other),
            Plus => match self.data.cmp(&From::from(other)) {
                Equal => Zero::zero(),
                Greater => BigInt::from_biguint(Plus, self.data - other),
                Less => BigInt::from_biguint(Minus, other - self.data),
            },
        }
    }
}
#[cfg(has_i128)]
impl SubAssign<u128> for BigInt {
    #[inline]
    fn sub_assign(&mut self, other: u128) {
        let n = mem::replace(self, BigInt::zero());
        *self = n - other;
    }
}

forward_all_scalar_binop_to_val_val!(impl Sub<i32> for BigInt, sub);
forward_all_scalar_binop_to_val_val!(impl Sub<i64> for BigInt, sub);
#[cfg(has_i128)]
forward_all_scalar_binop_to_val_val!(impl Sub<i128> for BigInt, sub);

impl Sub<i32> for BigInt {
    type Output = BigInt;

    #[inline]
    fn sub(self, other: i32) -> BigInt {
        if other >= 0 {
            self - other as u32
        } else {
            self + i32_abs_as_u32(other)
        }
    }
}
impl SubAssign<i32> for BigInt {
    #[inline]
    fn sub_assign(&mut self, other: i32) {
        if other >= 0 {
            *self -= other as u32;
        } else {
            *self += i32_abs_as_u32(other);
        }
    }
}

impl Sub<BigInt> for i32 {
    type Output = BigInt;

    #[inline]
    fn sub(self, other: BigInt) -> BigInt {
        if self >= 0 {
            self as u32 - other
        } else {
            -other - i32_abs_as_u32(self)
        }
    }
}

impl Sub<i64> for BigInt {
    type Output = BigInt;

    #[inline]
    fn sub(self, other: i64) -> BigInt {
        if other >= 0 {
            self - other as u64
        } else {
            self + i64_abs_as_u64(other)
        }
    }
}
impl SubAssign<i64> for BigInt {
    #[inline]
    fn sub_assign(&mut self, other: i64) {
        if other >= 0 {
            *self -= other as u64;
        } else {
            *self += i64_abs_as_u64(other);
        }
    }
}

impl Sub<BigInt> for i64 {
    type Output = BigInt;

    #[inline]
    fn sub(self, other: BigInt) -> BigInt {
        if self >= 0 {
            self as u64 - other
        } else {
            -other - i64_abs_as_u64(self)
        }
    }
}

#[cfg(has_i128)]
impl Sub<i128> for BigInt {
    type Output = BigInt;

    #[inline]
    fn sub(self, other: i128) -> BigInt {
        if other >= 0 {
            self - other as u128
        } else {
            self + i128_abs_as_u128(other)
        }
    }
}
#[cfg(has_i128)]
impl SubAssign<i128> for BigInt {
    #[inline]
    fn sub_assign(&mut self, other: i128) {
        if other >= 0 {
            *self -= other as u128;
        } else {
            *self += i128_abs_as_u128(other);
        }
    }
}
#[cfg(has_i128)]
impl Sub<BigInt> for i128 {
    type Output = BigInt;

    #[inline]
    fn sub(self, other: BigInt) -> BigInt {
        if self >= 0 {
            self as u128 - other
        } else {
            -other - i128_abs_as_u128(self)
        }
    }
}

forward_all_binop_to_ref_ref!(impl Mul for BigInt, mul);

impl<'a, 'b> Mul<&'b BigInt> for &'a BigInt {
    type Output = BigInt;

    #[inline]
    fn mul(self, other: &BigInt) -> BigInt {
        BigInt::from_biguint(self.sign * other.sign, &self.data * &other.data)
    }
}

impl<'a> MulAssign<&'a BigInt> for BigInt {
    #[inline]
    fn mul_assign(&mut self, other: &BigInt) {
        *self = &*self * other;
    }
}
forward_val_assign!(impl MulAssign for BigInt, mul_assign);

promote_all_scalars!(impl Mul for BigInt, mul);
promote_all_scalars_assign!(impl MulAssign for BigInt, mul_assign);
forward_all_scalar_binop_to_val_val_commutative!(impl Mul<u32> for BigInt, mul);
forward_all_scalar_binop_to_val_val_commutative!(impl Mul<u64> for BigInt, mul);
#[cfg(has_i128)]
forward_all_scalar_binop_to_val_val_commutative!(impl Mul<u128> for BigInt, mul);

impl Mul<u32> for BigInt {
    type Output = BigInt;

    #[inline]
    fn mul(self, other: u32) -> BigInt {
        BigInt::from_biguint(self.sign, self.data * other)
    }
}

impl MulAssign<u32> for BigInt {
    #[inline]
    fn mul_assign(&mut self, other: u32) {
        self.data *= other;
        if self.data.is_zero() {
            self.sign = NoSign;
        }
    }
}

impl Mul<u64> for BigInt {
    type Output = BigInt;

    #[inline]
    fn mul(self, other: u64) -> BigInt {
        BigInt::from_biguint(self.sign, self.data * other)
    }
}

impl MulAssign<u64> for BigInt {
    #[inline]
    fn mul_assign(&mut self, other: u64) {
        self.data *= other;
        if self.data.is_zero() {
            self.sign = NoSign;
        }
    }
}
#[cfg(has_i128)]
impl Mul<u128> for BigInt {
    type Output = BigInt;

    #[inline]
    fn mul(self, other: u128) -> BigInt {
        BigInt::from_biguint(self.sign, self.data * other)
    }
}
#[cfg(has_i128)]
impl MulAssign<u128> for BigInt {
    #[inline]
    fn mul_assign(&mut self, other: u128) {
        self.data *= other;
        if self.data.is_zero() {
            self.sign = NoSign;
        }
    }
}

forward_all_scalar_binop_to_val_val_commutative!(impl Mul<i32> for BigInt, mul);
forward_all_scalar_binop_to_val_val_commutative!(impl Mul<i64> for BigInt, mul);
#[cfg(has_i128)]
forward_all_scalar_binop_to_val_val_commutative!(impl Mul<i128> for BigInt, mul);

impl Mul<i32> for BigInt {
    type Output = BigInt;

    #[inline]
    fn mul(self, other: i32) -> BigInt {
        if other >= 0 {
            self * other as u32
        } else {
            -(self * i32_abs_as_u32(other))
        }
    }
}

impl MulAssign<i32> for BigInt {
    #[inline]
    fn mul_assign(&mut self, other: i32) {
        if other >= 0 {
            *self *= other as u32;
        } else {
            self.sign = -self.sign;
            *self *= i32_abs_as_u32(other);
        }
    }
}

impl Mul<i64> for BigInt {
    type Output = BigInt;

    #[inline]
    fn mul(self, other: i64) -> BigInt {
        if other >= 0 {
            self * other as u64
        } else {
            -(self * i64_abs_as_u64(other))
        }
    }
}

impl MulAssign<i64> for BigInt {
    #[inline]
    fn mul_assign(&mut self, other: i64) {
        if other >= 0 {
            *self *= other as u64;
        } else {
            self.sign = -self.sign;
            *self *= i64_abs_as_u64(other);
        }
    }
}
#[cfg(has_i128)]
impl Mul<i128> for BigInt {
    type Output = BigInt;

    #[inline]
    fn mul(self, other: i128) -> BigInt {
        if other >= 0 {
            self * other as u128
        } else {
            -(self * i128_abs_as_u128(other))
        }
    }
}
#[cfg(has_i128)]
impl MulAssign<i128> for BigInt {
    #[inline]
    fn mul_assign(&mut self, other: i128) {
        if other >= 0 {
            *self *= other as u128;
        } else {
            self.sign = -self.sign;
            *self *= i128_abs_as_u128(other);
        }
    }
}

forward_all_binop_to_ref_ref!(impl Div for BigInt, div);

impl<'a, 'b> Div<&'b BigInt> for &'a BigInt {
    type Output = BigInt;

    #[inline]
    fn div(self, other: &BigInt) -> BigInt {
        let (q, _) = self.div_rem(other);
        q
    }
}

impl<'a> DivAssign<&'a BigInt> for BigInt {
    #[inline]
    fn div_assign(&mut self, other: &BigInt) {
        *self = &*self / other;
    }
}
forward_val_assign!(impl DivAssign for BigInt, div_assign);

promote_all_scalars!(impl Div for BigInt, div);
promote_all_scalars_assign!(impl DivAssign for BigInt, div_assign);
forward_all_scalar_binop_to_val_val!(impl Div<u32> for BigInt, div);
forward_all_scalar_binop_to_val_val!(impl Div<u64> for BigInt, div);
#[cfg(has_i128)]
forward_all_scalar_binop_to_val_val!(impl Div<u128> for BigInt, div);

impl Div<u32> for BigInt {
    type Output = BigInt;

    #[inline]
    fn div(self, other: u32) -> BigInt {
        BigInt::from_biguint(self.sign, self.data / other)
    }
}

impl DivAssign<u32> for BigInt {
    #[inline]
    fn div_assign(&mut self, other: u32) {
        self.data /= other;
        if self.data.is_zero() {
            self.sign = NoSign;
        }
    }
}

impl Div<BigInt> for u32 {
    type Output = BigInt;

    #[inline]
    fn div(self, other: BigInt) -> BigInt {
        BigInt::from_biguint(other.sign, self / other.data)
    }
}

impl Div<u64> for BigInt {
    type Output = BigInt;

    #[inline]
    fn div(self, other: u64) -> BigInt {
        BigInt::from_biguint(self.sign, self.data / other)
    }
}

impl DivAssign<u64> for BigInt {
    #[inline]
    fn div_assign(&mut self, other: u64) {
        self.data /= other;
        if self.data.is_zero() {
            self.sign = NoSign;
        }
    }
}

impl Div<BigInt> for u64 {
    type Output = BigInt;

    #[inline]
    fn div(self, other: BigInt) -> BigInt {
        BigInt::from_biguint(other.sign, self / other.data)
    }
}

#[cfg(has_i128)]
impl Div<u128> for BigInt {
    type Output = BigInt;

    #[inline]
    fn div(self, other: u128) -> BigInt {
        BigInt::from_biguint(self.sign, self.data / other)
    }
}

#[cfg(has_i128)]
impl DivAssign<u128> for BigInt {
    #[inline]
    fn div_assign(&mut self, other: u128) {
        self.data /= other;
        if self.data.is_zero() {
            self.sign = NoSign;
        }
    }
}

#[cfg(has_i128)]
impl Div<BigInt> for u128 {
    type Output = BigInt;

    #[inline]
    fn div(self, other: BigInt) -> BigInt {
        BigInt::from_biguint(other.sign, self / other.data)
    }
}

forward_all_scalar_binop_to_val_val!(impl Div<i32> for BigInt, div);
forward_all_scalar_binop_to_val_val!(impl Div<i64> for BigInt, div);
#[cfg(has_i128)]
forward_all_scalar_binop_to_val_val!(impl Div<i128> for BigInt, div);

impl Div<i32> for BigInt {
    type Output = BigInt;

    #[inline]
    fn div(self, other: i32) -> BigInt {
        if other >= 0 {
            self / other as u32
        } else {
            -(self / i32_abs_as_u32(other))
        }
    }
}

impl DivAssign<i32> for BigInt {
    #[inline]
    fn div_assign(&mut self, other: i32) {
        if other >= 0 {
            *self /= other as u32;
        } else {
            self.sign = -self.sign;
            *self /= i32_abs_as_u32(other);
        }
    }
}

impl Div<BigInt> for i32 {
    type Output = BigInt;

    #[inline]
    fn div(self, other: BigInt) -> BigInt {
        if self >= 0 {
            self as u32 / other
        } else {
            -(i32_abs_as_u32(self) / other)
        }
    }
}

impl Div<i64> for BigInt {
    type Output = BigInt;

    #[inline]
    fn div(self, other: i64) -> BigInt {
        if other >= 0 {
            self / other as u64
        } else {
            -(self / i64_abs_as_u64(other))
        }
    }
}

impl DivAssign<i64> for BigInt {
    #[inline]
    fn div_assign(&mut self, other: i64) {
        if other >= 0 {
            *self /= other as u64;
        } else {
            self.sign = -self.sign;
            *self /= i64_abs_as_u64(other);
        }
    }
}

impl Div<BigInt> for i64 {
    type Output = BigInt;

    #[inline]
    fn div(self, other: BigInt) -> BigInt {
        if self >= 0 {
            self as u64 / other
        } else {
            -(i64_abs_as_u64(self) / other)
        }
    }
}

#[cfg(has_i128)]
impl Div<i128> for BigInt {
    type Output = BigInt;

    #[inline]
    fn div(self, other: i128) -> BigInt {
        if other >= 0 {
            self / other as u128
        } else {
            -(self / i128_abs_as_u128(other))
        }
    }
}

#[cfg(has_i128)]
impl DivAssign<i128> for BigInt {
    #[inline]
    fn div_assign(&mut self, other: i128) {
        if other >= 0 {
            *self /= other as u128;
        } else {
            self.sign = -self.sign;
            *self /= i128_abs_as_u128(other);
        }
    }
}

#[cfg(has_i128)]
impl Div<BigInt> for i128 {
    type Output = BigInt;

    #[inline]
    fn div(self, other: BigInt) -> BigInt {
        if self >= 0 {
            self as u128 / other
        } else {
            -(i128_abs_as_u128(self) / other)
        }
    }
}

forward_all_binop_to_ref_ref!(impl Rem for BigInt, rem);

impl<'a, 'b> Rem<&'b BigInt> for &'a BigInt {
    type Output = BigInt;

    #[inline]
    fn rem(self, other: &BigInt) -> BigInt {
        let (_, r) = self.div_rem(other);
        r
    }
}

impl<'a> RemAssign<&'a BigInt> for BigInt {
    #[inline]
    fn rem_assign(&mut self, other: &BigInt) {
        *self = &*self % other;
    }
}
forward_val_assign!(impl RemAssign for BigInt, rem_assign);

promote_all_scalars!(impl Rem for BigInt, rem);
promote_all_scalars_assign!(impl RemAssign for BigInt, rem_assign);
forward_all_scalar_binop_to_val_val!(impl Rem<u32> for BigInt, rem);
forward_all_scalar_binop_to_val_val!(impl Rem<u64> for BigInt, rem);
#[cfg(has_i128)]
forward_all_scalar_binop_to_val_val!(impl Rem<u128> for BigInt, rem);

impl Rem<u32> for BigInt {
    type Output = BigInt;

    #[inline]
    fn rem(self, other: u32) -> BigInt {
        BigInt::from_biguint(self.sign, self.data % other)
    }
}

impl RemAssign<u32> for BigInt {
    #[inline]
    fn rem_assign(&mut self, other: u32) {
        self.data %= other;
        if self.data.is_zero() {
            self.sign = NoSign;
        }
    }
}

impl Rem<BigInt> for u32 {
    type Output = BigInt;

    #[inline]
    fn rem(self, other: BigInt) -> BigInt {
        BigInt::from_biguint(Plus, self % other.data)
    }
}

impl Rem<u64> for BigInt {
    type Output = BigInt;

    #[inline]
    fn rem(self, other: u64) -> BigInt {
        BigInt::from_biguint(self.sign, self.data % other)
    }
}

impl RemAssign<u64> for BigInt {
    #[inline]
    fn rem_assign(&mut self, other: u64) {
        self.data %= other;
        if self.data.is_zero() {
            self.sign = NoSign;
        }
    }
}

impl Rem<BigInt> for u64 {
    type Output = BigInt;

    #[inline]
    fn rem(self, other: BigInt) -> BigInt {
        BigInt::from_biguint(Plus, self % other.data)
    }
}

#[cfg(has_i128)]
impl Rem<u128> for BigInt {
    type Output = BigInt;

    #[inline]
    fn rem(self, other: u128) -> BigInt {
        BigInt::from_biguint(self.sign, self.data % other)
    }
}

#[cfg(has_i128)]
impl RemAssign<u128> for BigInt {
    #[inline]
    fn rem_assign(&mut self, other: u128) {
        self.data %= other;
        if self.data.is_zero() {
            self.sign = NoSign;
        }
    }
}

#[cfg(has_i128)]
impl Rem<BigInt> for u128 {
    type Output = BigInt;

    #[inline]
    fn rem(self, other: BigInt) -> BigInt {
        BigInt::from_biguint(Plus, self % other.data)
    }
}

forward_all_scalar_binop_to_val_val!(impl Rem<i32> for BigInt, rem);
forward_all_scalar_binop_to_val_val!(impl Rem<i64> for BigInt, rem);
#[cfg(has_i128)]
forward_all_scalar_binop_to_val_val!(impl Rem<i128> for BigInt, rem);

impl Rem<i32> for BigInt {
    type Output = BigInt;

    #[inline]
    fn rem(self, other: i32) -> BigInt {
        if other >= 0 {
            self % other as u32
        } else {
            self % i32_abs_as_u32(other)
        }
    }
}

impl RemAssign<i32> for BigInt {
    #[inline]
    fn rem_assign(&mut self, other: i32) {
        if other >= 0 {
            *self %= other as u32;
        } else {
            *self %= i32_abs_as_u32(other);
        }
    }
}

impl Rem<BigInt> for i32 {
    type Output = BigInt;

    #[inline]
    fn rem(self, other: BigInt) -> BigInt {
        if self >= 0 {
            self as u32 % other
        } else {
            -(i32_abs_as_u32(self) % other)
        }
    }
}

impl Rem<i64> for BigInt {
    type Output = BigInt;

    #[inline]
    fn rem(self, other: i64) -> BigInt {
        if other >= 0 {
            self % other as u64
        } else {
            self % i64_abs_as_u64(other)
        }
    }
}

impl RemAssign<i64> for BigInt {
    #[inline]
    fn rem_assign(&mut self, other: i64) {
        if other >= 0 {
            *self %= other as u64;
        } else {
            *self %= i64_abs_as_u64(other);
        }
    }
}

impl Rem<BigInt> for i64 {
    type Output = BigInt;

    #[inline]
    fn rem(self, other: BigInt) -> BigInt {
        if self >= 0 {
            self as u64 % other
        } else {
            -(i64_abs_as_u64(self) % other)
        }
    }
}

#[cfg(has_i128)]
impl Rem<i128> for BigInt {
    type Output = BigInt;

    #[inline]
    fn rem(self, other: i128) -> BigInt {
        if other >= 0 {
            self % other as u128
        } else {
            self % i128_abs_as_u128(other)
        }
    }
}
#[cfg(has_i128)]
impl RemAssign<i128> for BigInt {
    #[inline]
    fn rem_assign(&mut self, other: i128) {
        if other >= 0 {
            *self %= other as u128;
        } else {
            *self %= i128_abs_as_u128(other);
        }
    }
}
#[cfg(has_i128)]
impl Rem<BigInt> for i128 {
    type Output = BigInt;

    #[inline]
    fn rem(self, other: BigInt) -> BigInt {
        if self >= 0 {
            self as u128 % other
        } else {
            -(i128_abs_as_u128(self) % other)
        }
    }
}

impl Neg for BigInt {
    type Output = BigInt;

    #[inline]
    fn neg(mut self) -> BigInt {
        self.sign = -self.sign;
        self
    }
}

impl<'a> Neg for &'a BigInt {
    type Output = BigInt;

    #[inline]
    fn neg(self) -> BigInt {
        -self.clone()
    }
}

impl CheckedAdd for BigInt {
    #[inline]
    fn checked_add(&self, v: &BigInt) -> Option<BigInt> {
        Some(self.add(v))
    }
}

impl CheckedSub for BigInt {
    #[inline]
    fn checked_sub(&self, v: &BigInt) -> Option<BigInt> {
        Some(self.sub(v))
    }
}

impl CheckedMul for BigInt {
    #[inline]
    fn checked_mul(&self, v: &BigInt) -> Option<BigInt> {
        Some(self.mul(v))
    }
}

impl CheckedDiv for BigInt {
    #[inline]
    fn checked_div(&self, v: &BigInt) -> Option<BigInt> {
        if v.is_zero() {
            return None;
        }
        Some(self.div(v))
    }
}

impl Integer for BigInt {
    #[inline]
    fn div_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
        // r.sign == self.sign
        let (d_ui, r_ui) = self.data.div_mod_floor(&other.data);
        let d = BigInt::from_biguint(self.sign, d_ui);
        let r = BigInt::from_biguint(self.sign, r_ui);
        if other.is_negative() {
            (-d, r)
        } else {
            (d, r)
        }
    }

    #[inline]
    fn div_floor(&self, other: &BigInt) -> BigInt {
        let (d, _) = self.div_mod_floor(other);
        d
    }

    #[inline]
    fn mod_floor(&self, other: &BigInt) -> BigInt {
        let (_, m) = self.div_mod_floor(other);
        m
    }

    fn div_mod_floor(&self, other: &BigInt) -> (BigInt, BigInt) {
        // m.sign == other.sign
        let (d_ui, m_ui) = self.data.div_rem(&other.data);
        let d = BigInt::from_biguint(Plus, d_ui);
        let m = BigInt::from_biguint(Plus, m_ui);
        let one: BigInt = One::one();
        match (self.sign, other.sign) {
            (_, NoSign) => panic!(),
            (Plus, Plus) | (NoSign, Plus) => (d, m),
            (Plus, Minus) | (NoSign, Minus) => {
                if m.is_zero() {
                    (-d, Zero::zero())
                } else {
                    (-d - one, m + other)
                }
            }
            (Minus, Plus) => {
                if m.is_zero() {
                    (-d, Zero::zero())
                } else {
                    (-d - one, other - m)
                }
            }
            (Minus, Minus) => (d, -m),
        }
    }

    /// Calculates the Greatest Common Divisor (GCD) of the number and `other`.
    ///
    /// The result is always positive.
    #[inline]
    fn gcd(&self, other: &BigInt) -> BigInt {
        BigInt::from_biguint(Plus, self.data.gcd(&other.data))
    }

    /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
    #[inline]
    fn lcm(&self, other: &BigInt) -> BigInt {
        BigInt::from_biguint(Plus, self.data.lcm(&other.data))
    }

    /// Deprecated, use `is_multiple_of` instead.
    #[inline]
    fn divides(&self, other: &BigInt) -> bool {
        self.is_multiple_of(other)
    }

    /// Returns `true` if the number is a multiple of `other`.
    #[inline]
    fn is_multiple_of(&self, other: &BigInt) -> bool {
        self.data.is_multiple_of(&other.data)
    }

    /// Returns `true` if the number is divisible by `2`.
    #[inline]
    fn is_even(&self) -> bool {
        self.data.is_even()
    }

    /// Returns `true` if the number is not divisible by `2`.
    #[inline]
    fn is_odd(&self) -> bool {
        self.data.is_odd()
    }
}

impl Roots for BigInt {
    fn nth_root(&self, n: u32) -> Self {
        assert!(
            !(self.is_negative() && n.is_even()),
            "root of degree {} is imaginary",
            n
        );

        BigInt::from_biguint(self.sign, self.data.nth_root(n))
    }

    fn sqrt(&self) -> Self {
        assert!(!self.is_negative(), "square root is imaginary");

        BigInt::from_biguint(self.sign, self.data.sqrt())
    }

    fn cbrt(&self) -> Self {
        BigInt::from_biguint(self.sign, self.data.cbrt())
    }
}

impl ToPrimitive for BigInt {
    #[inline]
    fn to_i64(&self) -> Option<i64> {
        match self.sign {
            Plus => self.data.to_i64(),
            NoSign => Some(0),
            Minus => self.data.to_u64().and_then(|n| {
                let m: u64 = 1 << 63;
                if n < m {
                    Some(-(n as i64))
                } else if n == m {
                    Some(i64::MIN)
                } else {
                    None
                }
            }),
        }
    }

    #[inline]
    #[cfg(has_i128)]
    fn to_i128(&self) -> Option<i128> {
        match self.sign {
            Plus => self.data.to_i128(),
            NoSign => Some(0),
            Minus => self.data.to_u128().and_then(|n| {
                let m: u128 = 1 << 127;
                if n < m {
                    Some(-(n as i128))
                } else if n == m {
                    Some(i128::MIN)
                } else {
                    None
                }
            }),
        }
    }

    #[inline]
    fn to_u64(&self) -> Option<u64> {
        match self.sign {
            Plus => self.data.to_u64(),
            NoSign => Some(0),
            Minus => None,
        }
    }

    #[inline]
    #[cfg(has_i128)]
    fn to_u128(&self) -> Option<u128> {
        match self.sign {
            Plus => self.data.to_u128(),
            NoSign => Some(0),
            Minus => None,
        }
    }

    #[inline]
    fn to_f32(&self) -> Option<f32> {
        self.data
            .to_f32()
            .map(|n| if self.sign == Minus { -n } else { n })
    }

    #[inline]
    fn to_f64(&self) -> Option<f64> {
        self.data
            .to_f64()
            .map(|n| if self.sign == Minus { -n } else { n })
    }
}

impl FromPrimitive for BigInt {
    #[inline]
    fn from_i64(n: i64) -> Option<BigInt> {
        Some(BigInt::from(n))
    }

    #[inline]
    #[cfg(has_i128)]
    fn from_i128(n: i128) -> Option<BigInt> {
        Some(BigInt::from(n))
    }

    #[inline]
    fn from_u64(n: u64) -> Option<BigInt> {
        Some(BigInt::from(n))
    }

    #[inline]
    #[cfg(has_i128)]
    fn from_u128(n: u128) -> Option<BigInt> {
        Some(BigInt::from(n))
    }

    #[inline]
    fn from_f64(n: f64) -> Option<BigInt> {
        if n >= 0.0 {
            BigUint::from_f64(n).map(|x| BigInt::from_biguint(Plus, x))
        } else {
            BigUint::from_f64(-n).map(|x| BigInt::from_biguint(Minus, x))
        }
    }
}

impl From<i64> for BigInt {
    #[inline]
    fn from(n: i64) -> Self {
        if n >= 0 {
            BigInt::from(n as u64)
        } else {
            let u = u64::MAX - (n as u64) + 1;
            BigInt {
                sign: Minus,
                data: BigUint::from(u),
            }
        }
    }
}

#[cfg(has_i128)]
impl From<i128> for BigInt {
    #[inline]
    fn from(n: i128) -> Self {
        if n >= 0 {
            BigInt::from(n as u128)
        } else {
            let u = u128::MAX - (n as u128) + 1;
            BigInt {
                sign: Minus,
                data: BigUint::from(u),
            }
        }
    }
}

macro_rules! impl_bigint_from_int {
    ($T:ty) => {
        impl From<$T> for BigInt {
            #[inline]
            fn from(n: $T) -> Self {
                BigInt::from(n as i64)
            }
        }
    };
}

impl_bigint_from_int!(i8);
impl_bigint_from_int!(i16);
impl_bigint_from_int!(i32);
impl_bigint_from_int!(isize);

impl From<u64> for BigInt {
    #[inline]
    fn from(n: u64) -> Self {
        if n > 0 {
            BigInt {
                sign: Plus,
                data: BigUint::from(n),
            }
        } else {
            BigInt::zero()
        }
    }
}

#[cfg(has_i128)]
impl From<u128> for BigInt {
    #[inline]
    fn from(n: u128) -> Self {
        if n > 0 {
            BigInt {
                sign: Plus,
                data: BigUint::from(n),
            }
        } else {
            BigInt::zero()
        }
    }
}

macro_rules! impl_bigint_from_uint {
    ($T:ty) => {
        impl From<$T> for BigInt {
            #[inline]
            fn from(n: $T) -> Self {
                BigInt::from(n as u64)
            }
        }
    };
}

impl_bigint_from_uint!(u8);
impl_bigint_from_uint!(u16);
impl_bigint_from_uint!(u32);
impl_bigint_from_uint!(usize);

impl From<BigUint> for BigInt {
    #[inline]
    fn from(n: BigUint) -> Self {
        if n.is_zero() {
            BigInt::zero()
        } else {
            BigInt {
                sign: Plus,
                data: n,
            }
        }
    }
}

impl IntDigits for BigInt {
    #[inline]
    fn digits(&self) -> &[BigDigit] {
        self.data.digits()
    }
    #[inline]
    fn digits_mut(&mut self) -> &mut Vec<BigDigit> {
        self.data.digits_mut()
    }
    #[inline]
    fn normalize(&mut self) {
        self.data.normalize();
        if self.data.is_zero() {
            self.sign = NoSign;
        }
    }
    #[inline]
    fn capacity(&self) -> usize {
        self.data.capacity()
    }
    #[inline]
    fn len(&self) -> usize {
        self.data.len()
    }
}

#[cfg(feature = "serde")]
impl serde::Serialize for BigInt {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: serde::Serializer,
    {
        // Note: do not change the serialization format, or it may break
        // forward and backward compatibility of serialized data!
        (self.sign, &self.data).serialize(serializer)
    }
}

#[cfg(feature = "serde")]
impl<'de> serde::Deserialize<'de> for BigInt {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        let (sign, data) = serde::Deserialize::deserialize(deserializer)?;
        Ok(BigInt::from_biguint(sign, data))
    }
}

/// A generic trait for converting a value to a `BigInt`. This may return
/// `None` when converting from `f32` or `f64`, and will always succeed
/// when converting from any integer or unsigned primitive, or `BigUint`.
pub trait ToBigInt {
    /// Converts the value of `self` to a `BigInt`.
    fn to_bigint(&self) -> Option<BigInt>;
}

impl ToBigInt for BigInt {
    #[inline]
    fn to_bigint(&self) -> Option<BigInt> {
        Some(self.clone())
    }
}

impl ToBigInt for BigUint {
    #[inline]
    fn to_bigint(&self) -> Option<BigInt> {
        if self.is_zero() {
            Some(Zero::zero())
        } else {
            Some(BigInt {
                sign: Plus,
                data: self.clone(),
            })
        }
    }
}

impl biguint::ToBigUint for BigInt {
    #[inline]
    fn to_biguint(&self) -> Option<BigUint> {
        match self.sign() {
            Plus => Some(self.data.clone()),
            NoSign => Some(Zero::zero()),
            Minus => None,
        }
    }
}

macro_rules! impl_to_bigint {
    ($T:ty, $from_ty:path) => {
        impl ToBigInt for $T {
            #[inline]
            fn to_bigint(&self) -> Option<BigInt> {
                $from_ty(*self)
            }
        }
    };
}

impl_to_bigint!(isize, FromPrimitive::from_isize);
impl_to_bigint!(i8, FromPrimitive::from_i8);
impl_to_bigint!(i16, FromPrimitive::from_i16);
impl_to_bigint!(i32, FromPrimitive::from_i32);
impl_to_bigint!(i64, FromPrimitive::from_i64);
#[cfg(has_i128)]
impl_to_bigint!(i128, FromPrimitive::from_i128);

impl_to_bigint!(usize, FromPrimitive::from_usize);
impl_to_bigint!(u8, FromPrimitive::from_u8);
impl_to_bigint!(u16, FromPrimitive::from_u16);
impl_to_bigint!(u32, FromPrimitive::from_u32);
impl_to_bigint!(u64, FromPrimitive::from_u64);
#[cfg(has_i128)]
impl_to_bigint!(u128, FromPrimitive::from_u128);

impl_to_bigint!(f32, FromPrimitive::from_f32);
impl_to_bigint!(f64, FromPrimitive::from_f64);

impl BigInt {
    /// Creates and initializes a BigInt.
    ///
    /// The base 2<sup>32</sup> digits are ordered least significant digit first.
    #[inline]
    pub fn new(sign: Sign, digits: Vec<u32>) -> BigInt {
        BigInt::from_biguint(sign, BigUint::new(digits))
    }

    /// Creates and initializes a `BigInt`.
    ///
    /// The base 2<sup>32</sup> digits are ordered least significant digit first.
    #[inline]
    pub fn from_biguint(mut sign: Sign, mut data: BigUint) -> BigInt {
        if sign == NoSign {
            data.assign_from_slice(&[]);
        } else if data.is_zero() {
            sign = NoSign;
        }

        BigInt {
            sign: sign,
            data: data,
        }
    }

    /// Creates and initializes a `BigInt`.
    ///
    /// The base 2<sup>32</sup> digits are ordered least significant digit first.
    #[inline]
    pub fn from_slice(sign: Sign, slice: &[u32]) -> BigInt {
        BigInt::from_biguint(sign, BigUint::from_slice(slice))
    }

    /// Reinitializes a `BigInt`.
    ///
    /// The base 2<sup>32</sup> digits are ordered least significant digit first.
    #[inline]
    pub fn assign_from_slice(&mut self, sign: Sign, slice: &[u32]) {
        if sign == NoSign {
            self.data.assign_from_slice(&[]);
            self.sign = NoSign;
        } else {
            self.data.assign_from_slice(slice);
            self.sign = match self.data.is_zero() {
                true => NoSign,
                false => sign,
            }
        }
    }

    /// Creates and initializes a `BigInt`.
    ///
    /// The bytes are in big-endian byte order.
    ///
    /// # Examples
    ///
    /// ```
    /// use num_bigint::{BigInt, Sign};
    ///
    /// assert_eq!(BigInt::from_bytes_be(Sign::Plus, b"A"),
    ///            BigInt::parse_bytes(b"65", 10).unwrap());
    /// assert_eq!(BigInt::from_bytes_be(Sign::Plus, b"AA"),
    ///            BigInt::parse_bytes(b"16705", 10).unwrap());
    /// assert_eq!(BigInt::from_bytes_be(Sign::Plus, b"AB"),
    ///            BigInt::parse_bytes(b"16706", 10).unwrap());
    /// assert_eq!(BigInt::from_bytes_be(Sign::Plus, b"Hello world!"),
    ///            BigInt::parse_bytes(b"22405534230753963835153736737", 10).unwrap());
    /// ```
    #[inline]
    pub fn from_bytes_be(sign: Sign, bytes: &[u8]) -> BigInt {
        BigInt::from_biguint(sign, BigUint::from_bytes_be(bytes))
    }

    /// Creates and initializes a `BigInt`.
    ///
    /// The bytes are in little-endian byte order.
    #[inline]
    pub fn from_bytes_le(sign: Sign, bytes: &[u8]) -> BigInt {
        BigInt::from_biguint(sign, BigUint::from_bytes_le(bytes))
    }

    /// Creates and initializes a `BigInt` from an array of bytes in
    /// two's complement binary representation.
    ///
    /// The digits are in big-endian base 2<sup>8</sup>.
    #[inline]
    pub fn from_signed_bytes_be(digits: &[u8]) -> BigInt {
        let sign = match digits.first() {
            Some(v) if *v > 0x7f => Sign::Minus,
            Some(_) => Sign::Plus,
            None => return BigInt::zero(),
        };

        if sign == Sign::Minus {
            // two's-complement the content to retrieve the magnitude
            let mut digits = Vec::from(digits);
            twos_complement_be(&mut digits);
            BigInt::from_biguint(sign, BigUint::from_bytes_be(&*digits))
        } else {
            BigInt::from_biguint(sign, BigUint::from_bytes_be(digits))
        }
    }

    /// Creates and initializes a `BigInt` from an array of bytes in two's complement.
    ///
    /// The digits are in little-endian base 2<sup>8</sup>.
    #[inline]
    pub fn from_signed_bytes_le(digits: &[u8]) -> BigInt {
        let sign = match digits.last() {
            Some(v) if *v > 0x7f => Sign::Minus,
            Some(_) => Sign::Plus,
            None => return BigInt::zero(),
        };

        if sign == Sign::Minus {
            // two's-complement the content to retrieve the magnitude
            let mut digits = Vec::from(digits);
            twos_complement_le(&mut digits);
            BigInt::from_biguint(sign, BigUint::from_bytes_le(&*digits))
        } else {
            BigInt::from_biguint(sign, BigUint::from_bytes_le(digits))
        }
    }

    /// Creates and initializes a `BigInt`.
    ///
    /// # Examples
    ///
    /// ```
    /// use num_bigint::{BigInt, ToBigInt};
    ///
    /// assert_eq!(BigInt::parse_bytes(b"1234", 10), ToBigInt::to_bigint(&1234));
    /// assert_eq!(BigInt::parse_bytes(b"ABCD", 16), ToBigInt::to_bigint(&0xABCD));
    /// assert_eq!(BigInt::parse_bytes(b"G", 16), None);
    /// ```
    #[inline]
    pub fn parse_bytes(buf: &[u8], radix: u32) -> Option<BigInt> {
        str::from_utf8(buf)
            .ok()
            .and_then(|s| BigInt::from_str_radix(s, radix).ok())
    }

    /// Creates and initializes a `BigInt`. Each u8 of the input slice is
    /// interpreted as one digit of the number
    /// and must therefore be less than `radix`.
    ///
    /// The bytes are in big-endian byte order.
    /// `radix` must be in the range `2...256`.
    ///
    /// # Examples
    ///
    /// ```
    /// use num_bigint::{BigInt, Sign};
    ///
    /// let inbase190 = vec![15, 33, 125, 12, 14];
    /// let a = BigInt::from_radix_be(Sign::Minus, &inbase190, 190).unwrap();
    /// assert_eq!(a.to_radix_be(190), (Sign:: Minus, inbase190));
    /// ```
    pub fn from_radix_be(sign: Sign, buf: &[u8], radix: u32) -> Option<BigInt> {
        BigUint::from_radix_be(buf, radix).map(|u| BigInt::from_biguint(sign, u))
    }

    /// Creates and initializes a `BigInt`. Each u8 of the input slice is
    /// interpreted as one digit of the number
    /// and must therefore be less than `radix`.
    ///
    /// The bytes are in little-endian byte order.
    /// `radix` must be in the range `2...256`.
    ///
    /// # Examples
    ///
    /// ```
    /// use num_bigint::{BigInt, Sign};
    ///
    /// let inbase190 = vec![14, 12, 125, 33, 15];
    /// let a = BigInt::from_radix_be(Sign::Minus, &inbase190, 190).unwrap();
    /// assert_eq!(a.to_radix_be(190), (Sign::Minus, inbase190));
    /// ```
    pub fn from_radix_le(sign: Sign, buf: &[u8], radix: u32) -> Option<BigInt> {
        BigUint::from_radix_le(buf, radix).map(|u| BigInt::from_biguint(sign, u))
    }

    /// Returns the sign and the byte representation of the `BigInt` in big-endian byte order.
    ///
    /// # Examples
    ///
    /// ```
    /// use num_bigint::{ToBigInt, Sign};
    ///
    /// let i = -1125.to_bigint().unwrap();
    /// assert_eq!(i.to_bytes_be(), (Sign::Minus, vec![4, 101]));
    /// ```
    #[inline]
    pub fn to_bytes_be(&self) -> (Sign, Vec<u8>) {
        (self.sign, self.data.to_bytes_be())
    }

    /// Returns the sign and the byte representation of the `BigInt` in little-endian byte order.
    ///
    /// # Examples
    ///
    /// ```
    /// use num_bigint::{ToBigInt, Sign};
    ///
    /// let i = -1125.to_bigint().unwrap();
    /// assert_eq!(i.to_bytes_le(), (Sign::Minus, vec![101, 4]));
    /// ```
    #[inline]
    pub fn to_bytes_le(&self) -> (Sign, Vec<u8>) {
        (self.sign, self.data.to_bytes_le())
    }

    /// Returns the sign and the `u32` digits representation of the `BigInt` ordered least
    /// significant digit first.
    ///
    /// # Examples
    ///
    /// ```
    /// use num_bigint::{BigInt, Sign};
    ///
    /// assert_eq!(BigInt::from(-1125).to_u32_digits(), (Sign::Minus, vec![1125]));
    /// assert_eq!(BigInt::from(4294967295u32).to_u32_digits(), (Sign::Plus, vec![4294967295]));
    /// assert_eq!(BigInt::from(4294967296u64).to_u32_digits(), (Sign::Plus, vec![0, 1]));
    /// assert_eq!(BigInt::from(-112500000000i64).to_u32_digits(), (Sign::Minus, vec![830850304, 26]));
    /// assert_eq!(BigInt::from(112500000000i64).to_u32_digits(), (Sign::Plus, vec![830850304, 26]));
    /// ```
    #[inline]
    pub fn to_u32_digits(&self) -> (Sign, Vec<u32>) {
        (self.sign, self.data.to_u32_digits())
    }

    /// Returns the two's-complement byte representation of the `BigInt` in big-endian byte order.
    ///
    /// # Examples
    ///
    /// ```
    /// use num_bigint::ToBigInt;
    ///
    /// let i = -1125.to_bigint().unwrap();
    /// assert_eq!(i.to_signed_bytes_be(), vec![251, 155]);
    /// ```
    #[inline]
    pub fn to_signed_bytes_be(&self) -> Vec<u8> {
        let mut bytes = self.data.to_bytes_be();
        let first_byte = bytes.first().cloned().unwrap_or(0);
        if first_byte > 0x7f
            && !(first_byte == 0x80
                && bytes.iter().skip(1).all(Zero::is_zero)
                && self.sign == Sign::Minus)
        {
            // msb used by magnitude, extend by 1 byte
            bytes.insert(0, 0);
        }
        if self.sign == Sign::Minus {
            twos_complement_be(&mut bytes);
        }
        bytes
    }

    /// Returns the two's-complement byte representation of the `BigInt` in little-endian byte order.
    ///
    /// # Examples
    ///
    /// ```
    /// use num_bigint::ToBigInt;
    ///
    /// let i = -1125.to_bigint().unwrap();
    /// assert_eq!(i.to_signed_bytes_le(), vec![155, 251]);
    /// ```
    #[inline]
    pub fn to_signed_bytes_le(&self) -> Vec<u8> {
        let mut bytes = self.data.to_bytes_le();
        let last_byte = bytes.last().cloned().unwrap_or(0);
        if last_byte > 0x7f
            && !(last_byte == 0x80
                && bytes.iter().rev().skip(1).all(Zero::is_zero)
                && self.sign == Sign::Minus)
        {
            // msb used by magnitude, extend by 1 byte
            bytes.push(0);
        }
        if self.sign == Sign::Minus {
            twos_complement_le(&mut bytes);
        }
        bytes
    }

    /// Returns the integer formatted as a string in the given radix.
    /// `radix` must be in the range `2...36`.
    ///
    /// # Examples
    ///
    /// ```
    /// use num_bigint::BigInt;
    ///
    /// let i = BigInt::parse_bytes(b"ff", 16).unwrap();
    /// assert_eq!(i.to_str_radix(16), "ff");
    /// ```
    #[inline]
    pub fn to_str_radix(&self, radix: u32) -> String {
        let mut v = to_str_radix_reversed(&self.data, radix);

        if self.is_negative() {
            v.push(b'-');
        }

        v.reverse();
        unsafe { String::from_utf8_unchecked(v) }
    }

    /// Returns the integer in the requested base in big-endian digit order.
    /// The output is not given in a human readable alphabet but as a zero
    /// based u8 number.
    /// `radix` must be in the range `2...256`.
    ///
    /// # Examples
    ///
    /// ```
    /// use num_bigint::{BigInt, Sign};
    ///
    /// assert_eq!(BigInt::from(-0xFFFFi64).to_radix_be(159),
    ///            (Sign::Minus, vec![2, 94, 27]));
    /// // 0xFFFF = 65535 = 2*(159^2) + 94*159 + 27
    /// ```
    #[inline]
    pub fn to_radix_be(&self, radix: u32) -> (Sign, Vec<u8>) {
        (self.sign, self.data.to_radix_be(radix))
    }

    /// Returns the integer in the requested base in little-endian digit order.
    /// The output is not given in a human readable alphabet but as a zero
    /// based u8 number.
    /// `radix` must be in the range `2...256`.
    ///
    /// # Examples
    ///
    /// ```
    /// use num_bigint::{BigInt, Sign};
    ///
    /// assert_eq!(BigInt::from(-0xFFFFi64).to_radix_le(159),
    ///            (Sign::Minus, vec![27, 94, 2]));
    /// // 0xFFFF = 65535 = 27 + 94*159 + 2*(159^2)
    /// ```
    #[inline]
    pub fn to_radix_le(&self, radix: u32) -> (Sign, Vec<u8>) {
        (self.sign, self.data.to_radix_le(radix))
    }

    /// Returns the sign of the `BigInt` as a `Sign`.
    ///
    /// # Examples
    ///
    /// ```
    /// use num_bigint::{ToBigInt, Sign};
    ///
    /// assert_eq!(ToBigInt::to_bigint(&1234).unwrap().sign(), Sign::Plus);
    /// assert_eq!(ToBigInt::to_bigint(&-4321).unwrap().sign(), Sign::Minus);
    /// assert_eq!(ToBigInt::to_bigint(&0).unwrap().sign(), Sign::NoSign);
    /// ```
    #[inline]
    pub fn sign(&self) -> Sign {
        self.sign
    }

    /// Determines the fewest bits necessary to express the `BigInt`,
    /// not including the sign.
    #[inline]
    pub fn bits(&self) -> usize {
        self.data.bits()
    }

    /// Converts this `BigInt` into a `BigUint`, if it's not negative.
    #[inline]
    pub fn to_biguint(&self) -> Option<BigUint> {
        match self.sign {
            Plus => Some(self.data.clone()),
            NoSign => Some(Zero::zero()),
            Minus => None,
        }
    }

    #[inline]
    pub fn checked_add(&self, v: &BigInt) -> Option<BigInt> {
        Some(self.add(v))
    }

    #[inline]
    pub fn checked_sub(&self, v: &BigInt) -> Option<BigInt> {
        Some(self.sub(v))
    }

    #[inline]
    pub fn checked_mul(&self, v: &BigInt) -> Option<BigInt> {
        Some(self.mul(v))
    }

    #[inline]
    pub fn checked_div(&self, v: &BigInt) -> Option<BigInt> {
        if v.is_zero() {
            return None;
        }
        Some(self.div(v))
    }

    /// Returns `(self ^ exponent) mod modulus`
    ///
    /// Note that this rounds like `mod_floor`, not like the `%` operator,
    /// which makes a difference when given a negative `self` or `modulus`.
    /// The result will be in the interval `[0, modulus)` for `modulus > 0`,
    /// or in the interval `(modulus, 0]` for `modulus < 0`
    ///
    /// Panics if the exponent is negative or the modulus is zero.
    pub fn modpow(&self, exponent: &Self, modulus: &Self) -> Self {
        assert!(
            !exponent.is_negative(),
            "negative exponentiation is not supported!"
        );
        assert!(!modulus.is_zero(), "divide by zero!");

        let result = self.data.modpow(&exponent.data, &modulus.data);
        if result.is_zero() {
            return BigInt::zero();
        }

        // The sign of the result follows the modulus, like `mod_floor`.
        let (sign, mag) = match (
            self.is_negative() && exponent.is_odd(),
            modulus.is_negative(),
        ) {
            (false, false) => (Plus, result),
            (true, false) => (Plus, &modulus.data - result),
            (false, true) => (Minus, &modulus.data - result),
            (true, true) => (Minus, result),
        };
        BigInt::from_biguint(sign, mag)
    }

    /// Returns the truncated principal square root of `self` --
    /// see [Roots::sqrt](https://docs.rs/num-integer/0.1/num_integer/trait.Roots.html#method.sqrt).
    pub fn sqrt(&self) -> Self {
        Roots::sqrt(self)
    }

    /// Returns the truncated principal cube root of `self` --
    /// see [Roots::cbrt](https://docs.rs/num-integer/0.1/num_integer/trait.Roots.html#method.cbrt).
    pub fn cbrt(&self) -> Self {
        Roots::cbrt(self)
    }

    /// Returns the truncated principal `n`th root of `self` --
    /// See [Roots::nth_root](https://docs.rs/num-integer/0.1/num_integer/trait.Roots.html#tymethod.nth_root).
    pub fn nth_root(&self, n: u32) -> Self {
        Roots::nth_root(self, n)
    }
}

impl_sum_iter_type!(BigInt);
impl_product_iter_type!(BigInt);

/// Perform in-place two's complement of the given binary representation,
/// in little-endian byte order.
#[inline]
fn twos_complement_le(digits: &mut [u8]) {
    twos_complement(digits)
}

/// Perform in-place two's complement of the given binary representation
/// in big-endian byte order.
#[inline]
fn twos_complement_be(digits: &mut [u8]) {
    twos_complement(digits.iter_mut().rev())
}

/// Perform in-place two's complement of the given digit iterator
/// starting from the least significant byte.
#[inline]
fn twos_complement<'a, I>(digits: I)
where
    I: IntoIterator<Item = &'a mut u8>,
{
    let mut carry = true;
    for d in digits {
        *d = d.not();
        if carry {
            *d = d.wrapping_add(1);
            carry = d.is_zero();
        }
    }
}

#[test]
fn test_from_biguint() {
    fn check(inp_s: Sign, inp_n: usize, ans_s: Sign, ans_n: usize) {
        let inp = BigInt::from_biguint(inp_s, FromPrimitive::from_usize(inp_n).unwrap());
        let ans = BigInt {
            sign: ans_s,
            data: FromPrimitive::from_usize(ans_n).unwrap(),
        };
        assert_eq!(inp, ans);
    }
    check(Plus, 1, Plus, 1);
    check(Plus, 0, NoSign, 0);
    check(Minus, 1, Minus, 1);
    check(NoSign, 1, NoSign, 0);
}

#[test]
fn test_from_slice() {
    fn check(inp_s: Sign, inp_n: u32, ans_s: Sign, ans_n: u32) {
        let inp = BigInt::from_slice(inp_s, &[inp_n]);
        let ans = BigInt {
            sign: ans_s,
            data: FromPrimitive::from_u32(ans_n).unwrap(),
        };
        assert_eq!(inp, ans);
    }
    check(Plus, 1, Plus, 1);
    check(Plus, 0, NoSign, 0);
    check(Minus, 1, Minus, 1);
    check(NoSign, 1, NoSign, 0);
}

#[test]
fn test_assign_from_slice() {
    fn check(inp_s: Sign, inp_n: u32, ans_s: Sign, ans_n: u32) {
        let mut inp = BigInt::from_slice(Minus, &[2627_u32, 0_u32, 9182_u32, 42_u32]);
        inp.assign_from_slice(inp_s, &[inp_n]);
        let ans = BigInt {
            sign: ans_s,
            data: FromPrimitive::from_u32(ans_n).unwrap(),
        };
        assert_eq!(inp, ans);
    }
    check(Plus, 1, Plus, 1);
    check(Plus, 0, NoSign, 0);
    check(Minus, 1, Minus, 1);
    check(NoSign, 1, NoSign, 0);
}