malachite_nz/integer/conversion/from_twos_complement_limbs.rs
1// Copyright © 2025 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::integer::Integer;
10use crate::integer::conversion::to_twos_complement_limbs::{
11 limbs_twos_complement, limbs_twos_complement_in_place,
12};
13use crate::natural::Natural;
14use crate::platform::Limb;
15use alloc::vec::Vec;
16use malachite_base::num::basic::integers::PrimitiveInt;
17use malachite_base::num::basic::traits::Zero;
18
19impl Integer {
20 /// Converts a slice of [limbs](crate#limbs) to an [`Integer`], in ascending order, so that less
21 /// significant limbs have lower indices in the input slice.
22 ///
23 /// The limbs are in two's complement, and the most significant bit of the limbs indicates the
24 /// sign; if the bit is zero, the [`Integer`] is non-negative, and if the bit is one it is
25 /// negative. If the slice is empty, zero is returned.
26 ///
27 /// This function borrows a slice. If taking ownership of a [`Vec`] is possible instead,
28 /// [`from_owned_twos_complement_limbs_asc`](`Self::from_owned_twos_complement_limbs_asc`) is
29 /// more efficient.
30 ///
31 /// This function is more efficient than
32 /// [`from_twos_complement_limbs_desc`](`Self::from_twos_complement_limbs_desc`).
33 ///
34 /// # Worst-case complexity
35 /// $T(n) = O(n)$
36 ///
37 /// $M(n) = O(n)$
38 ///
39 /// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
40 ///
41 /// # Examples
42 /// ```
43 /// use malachite_base::num::basic::integers::PrimitiveInt;
44 /// use malachite_nz::integer::Integer;
45 /// use malachite_nz::platform::Limb;
46 ///
47 /// if Limb::WIDTH == u32::WIDTH {
48 /// assert_eq!(Integer::from_twos_complement_limbs_asc(&[]), 0);
49 /// assert_eq!(Integer::from_twos_complement_limbs_asc(&[123]), 123);
50 /// assert_eq!(Integer::from_twos_complement_limbs_asc(&[4294967173]), -123);
51 /// // 10^12 = 232 * 2^32 + 3567587328
52 /// assert_eq!(
53 /// Integer::from_twos_complement_limbs_asc(&[3567587328, 232]),
54 /// 1000000000000u64
55 /// );
56 /// assert_eq!(
57 /// Integer::from_twos_complement_limbs_asc(&[727379968, 4294967063]),
58 /// -1000000000000i64
59 /// );
60 /// }
61 /// ```
62 pub fn from_twos_complement_limbs_asc(xs: &[Limb]) -> Self {
63 match xs {
64 &[] => Self::ZERO,
65 &[.., last] if !last.get_highest_bit() => Self::from(Natural::from_limbs_asc(xs)),
66 xs => -Natural::from_owned_limbs_asc(limbs_twos_complement(xs)),
67 }
68 }
69
70 /// Converts a slice of [limbs](crate#limbs) to an [`Integer`], in descending order, so that
71 /// less significant limbs have higher indices in the input slice.
72 ///
73 /// The limbs are in two's complement, and the most significant bit of the limbs indicates the
74 /// sign; if the bit is zero, the [`Integer`] is non-negative, and if the bit is one it is
75 /// negative. If the slice is empty, zero is returned.
76 ///
77 /// This function borrows a slice. If taking ownership of a [`Vec`] is possible instead,
78 /// [`from_owned_twos_complement_limbs_desc`](`Self::from_owned_twos_complement_limbs_desc`) is
79 /// more efficient.
80 ///
81 /// This function is less efficient than
82 /// [`from_twos_complement_limbs_asc`](`Self::from_twos_complement_limbs_asc`).
83 ///
84 /// # Worst-case complexity
85 /// $T(n) = O(n)$
86 ///
87 /// $M(n) = O(n)$
88 ///
89 /// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
90 ///
91 /// # Examples
92 /// ```
93 /// use malachite_base::num::basic::integers::PrimitiveInt;
94 /// use malachite_nz::integer::Integer;
95 /// use malachite_nz::platform::Limb;
96 ///
97 /// if Limb::WIDTH == u32::WIDTH {
98 /// assert_eq!(Integer::from_twos_complement_limbs_desc(&[]), 0);
99 /// assert_eq!(Integer::from_twos_complement_limbs_desc(&[123]), 123);
100 /// assert_eq!(
101 /// Integer::from_twos_complement_limbs_desc(&[4294967173]),
102 /// -123
103 /// );
104 /// // 10^12 = 232 * 2^32 + 3567587328
105 /// assert_eq!(
106 /// Integer::from_twos_complement_limbs_desc(&[232, 3567587328]),
107 /// 1000000000000u64
108 /// );
109 /// assert_eq!(
110 /// Integer::from_twos_complement_limbs_desc(&[4294967063, 727379968]),
111 /// -1000000000000i64
112 /// );
113 /// }
114 /// ```
115 pub fn from_twos_complement_limbs_desc(xs: &[Limb]) -> Self {
116 Self::from_owned_twos_complement_limbs_asc(xs.iter().copied().rev().collect())
117 }
118
119 /// Converts a slice of [limbs](crate#limbs) to an [`Integer`], in ascending order, so that less
120 /// significant limbs have lower indices in the input slice.
121 ///
122 /// The limbs are in two's complement, and the most significant bit of the limbs indicates the
123 /// sign; if the bit is zero, the [`Integer`] is non-negative, and if the bit is one it is
124 /// negative. If the slice is empty, zero is returned.
125 ///
126 /// This function takes ownership of a [`Vec`]. If it's necessary to borrow a slice instead, use
127 /// [`from_twos_complement_limbs_asc`](`Self::from_twos_complement_limbs_asc`)
128 ///
129 /// This function is more efficient than
130 /// [`from_owned_twos_complement_limbs_desc`](`Self::from_owned_twos_complement_limbs_desc`).
131 ///
132 /// # Worst-case complexity
133 /// $T(n) = O(n)$
134 ///
135 /// $M(n) = O(1)$
136 ///
137 /// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
138 ///
139 /// # Examples
140 /// ```
141 /// use malachite_base::num::basic::integers::PrimitiveInt;
142 /// use malachite_nz::integer::Integer;
143 /// use malachite_nz::platform::Limb;
144 ///
145 /// if Limb::WIDTH == u32::WIDTH {
146 /// assert_eq!(Integer::from_owned_twos_complement_limbs_asc(vec![]), 0);
147 /// assert_eq!(
148 /// Integer::from_owned_twos_complement_limbs_asc(vec![123]),
149 /// 123
150 /// );
151 /// assert_eq!(
152 /// Integer::from_owned_twos_complement_limbs_asc(vec![4294967173]),
153 /// -123
154 /// );
155 /// // 10^12 = 232 * 2^32 + 3567587328
156 /// assert_eq!(
157 /// Integer::from_owned_twos_complement_limbs_asc(vec![3567587328, 232]),
158 /// 1000000000000i64
159 /// );
160 /// assert_eq!(
161 /// Integer::from_owned_twos_complement_limbs_asc(vec![727379968, 4294967063]),
162 /// -1000000000000i64
163 /// );
164 /// }
165 /// ```
166 pub fn from_owned_twos_complement_limbs_asc(mut xs: Vec<Limb>) -> Self {
167 match *xs.as_slice() {
168 [] => Self::ZERO,
169 [.., last] if !last.get_highest_bit() => Self::from(Natural::from_owned_limbs_asc(xs)),
170 _ => {
171 assert!(!limbs_twos_complement_in_place(&mut xs));
172 -Natural::from_owned_limbs_asc(xs)
173 }
174 }
175 }
176
177 /// Converts a slice of [limbs](crate#limbs) to an [`Integer`], in descending order, so that
178 /// less significant limbs have higher indices in the input slice.
179 ///
180 /// The limbs are in two's complement, and the most significant bit of the limbs indicates the
181 /// sign; if the bit is zero, the [`Integer`] is non-negative, and if the bit is one it is
182 /// negative. If the slice is empty, zero is returned.
183 ///
184 /// This function takes ownership of a [`Vec`]. If it's necessary to borrow a slice instead, use
185 /// [`from_twos_complement_limbs_desc`](`Self::from_twos_complement_limbs_desc`).
186 ///
187 /// This function is less efficient than
188 /// [`from_owned_twos_complement_limbs_asc`](`Self::from_owned_twos_complement_limbs_asc`).
189 ///
190 /// # Worst-case complexity
191 /// $T(n) = O(n)$
192 ///
193 /// $M(n) = O(1)$
194 ///
195 /// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
196 ///
197 /// # Examples
198 /// ```
199 /// use malachite_base::num::basic::integers::PrimitiveInt;
200 /// use malachite_nz::integer::Integer;
201 /// use malachite_nz::platform::Limb;
202 ///
203 /// if Limb::WIDTH == u32::WIDTH {
204 /// assert_eq!(Integer::from_owned_twos_complement_limbs_desc(vec![]), 0);
205 /// assert_eq!(
206 /// Integer::from_owned_twos_complement_limbs_desc(vec![123]),
207 /// 123
208 /// );
209 /// assert_eq!(
210 /// Integer::from_owned_twos_complement_limbs_desc(vec![4294967173]),
211 /// -123
212 /// );
213 /// // 10^12 = 232 * 2^32 + 3567587328
214 /// assert_eq!(
215 /// Integer::from_owned_twos_complement_limbs_desc(vec![232, 3567587328]),
216 /// 1000000000000i64
217 /// );
218 /// assert_eq!(
219 /// Integer::from_owned_twos_complement_limbs_desc(vec![4294967063, 727379968]),
220 /// -1000000000000i64
221 /// );
222 /// }
223 /// ```
224 pub fn from_owned_twos_complement_limbs_desc(mut xs: Vec<Limb>) -> Self {
225 xs.reverse();
226 Self::from_owned_twos_complement_limbs_asc(xs)
227 }
228}