malachite_nz/integer_vector/arithmetic/shr.rs
1// Copyright © 2026 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_vector::IntegerVector;
11use core::ops::{Shr, ShrAssign};
12
13// Shifts every element right by `bits`, taking the floor.
14fn shr_ref<T: Copy>(v: &IntegerVector, bits: T) -> IntegerVector
15where
16 for<'a> &'a Integer: Shr<T, Output = Integer>,
17{
18 IntegerVector {
19 elements: v.elements.iter().map(|x| x >> bits).collect(),
20 }
21}
22
23// Shifts every element right by `bits`, taking the floor, in place.
24fn shr_assign<T: Copy>(v: &mut IntegerVector, bits: T)
25where
26 Integer: ShrAssign<T>,
27{
28 for x in &mut v.elements {
29 *x >>= bits;
30 }
31}
32
33macro_rules! impl_integer_vector_shr_unsigned {
34 ($t:ident) => {
35 impl Shr<$t> for IntegerVector {
36 type Output = IntegerVector;
37
38 /// Right-shifts an [`IntegerVector`] (divides it by a power of 2 and takes the floor),
39 /// taking it by value. Every element is shifted, and the dimension is unchanged.
40 ///
41 /// $f(v, k) = \lfloor v/2^k \rfloor$. The floor is taken entrywise, rounding toward
42 /// negative infinity; to round differently, use
43 /// [`entrywise_shr_round`](malachite_base::num::arithmetic::traits::EntrywiseShrRound).
44 ///
45 /// # Worst-case complexity
46 /// $T(n, k) = O(n + k)$
47 ///
48 /// $M(n, k) = O(n + k)$
49 ///
50 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the
51 /// elements, and $k$ is `self.dimension()`.
52 ///
53 /// # Examples
54 /// See [here](super::shr#shr). /// This is equivalent to
55 /// `_fmpz_vec_scalar_fdiv_q_2exp` from `fmpz_vec/scalar.c`, FLINT 3.6.0.
56 #[inline]
57 fn shr(mut self, bits: $t) -> IntegerVector {
58 self >>= bits;
59 self
60 }
61 }
62
63 impl Shr<$t> for &IntegerVector {
64 type Output = IntegerVector;
65
66 /// Right-shifts an [`IntegerVector`] (divides it by a power of 2 and takes the floor),
67 /// taking it by reference. Every element is shifted, and the dimension is unchanged.
68 ///
69 /// $f(v, k) = \lfloor v/2^k \rfloor$. The floor is taken entrywise, rounding toward
70 /// negative infinity; to round differently, use
71 /// [`entrywise_shr_round`](malachite_base::num::arithmetic::traits::EntrywiseShrRound).
72 ///
73 /// # Worst-case complexity
74 /// $T(n, k) = O(n + k)$
75 ///
76 /// $M(n, k) = O(n + k)$
77 ///
78 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the
79 /// elements, and $k$ is `self.dimension()`.
80 ///
81 /// # Examples
82 /// See [here](super::shr#shr). /// This is equivalent to
83 /// `_fmpz_vec_scalar_fdiv_q_2exp` from `fmpz_vec/scalar.c`, FLINT 3.6.0.
84 #[inline]
85 fn shr(self, bits: $t) -> IntegerVector {
86 shr_ref(self, bits)
87 }
88 }
89
90 impl ShrAssign<$t> for IntegerVector {
91 /// Right-shifts an [`IntegerVector`] (divides it by a power of 2 and takes the floor),
92 /// in place. Every element is shifted, and the dimension is unchanged.
93 ///
94 /// $v \gets \lfloor v/2^k \rfloor$. The floor is taken entrywise, rounding toward
95 /// negative infinity; to round differently, use
96 /// [`entrywise_shr_round`](malachite_base::num::arithmetic::traits::EntrywiseShrRound).
97 ///
98 /// # Worst-case complexity
99 /// $T(n, k) = O(n + k)$
100 ///
101 /// $M(k) = O(1)$
102 ///
103 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the
104 /// elements, and $k$ is `self.dimension()`.
105 ///
106 /// # Examples
107 /// See [here](super::shr#shr_assign). /// This is equivalent to
108 /// `_fmpz_vec_scalar_fdiv_q_2exp` from `fmpz_vec/scalar.c`, FLINT 3.6.0.
109 #[inline]
110 fn shr_assign(&mut self, bits: $t) {
111 shr_assign(self, bits);
112 }
113 }
114 };
115}
116apply_to_unsigneds!(impl_integer_vector_shr_unsigned);
117
118macro_rules! impl_integer_vector_shr_signed {
119 ($t:ident) => {
120 impl Shr<$t> for IntegerVector {
121 type Output = IntegerVector;
122
123 /// Right-shifts an [`IntegerVector`] (divides or multiplies it by a power of 2), taking
124 /// it by value. Every element is shifted, and the dimension is unchanged.
125 ///
126 /// $f(v, k) = \lfloor v/2^k \rfloor$. The floor is taken entrywise, rounding toward
127 /// negative infinity; to round differently, use
128 /// [`entrywise_shr_round`](malachite_base::num::arithmetic::traits::EntrywiseShrRound).
129 ///
130 /// A negative `bits` shifts left, multiplying every element by $2^{-k}$.
131 ///
132 /// # Worst-case complexity
133 /// $T(n, m, k) = O(n + km)$
134 ///
135 /// $M(n, m, k) = O(n + km)$
136 ///
137 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the
138 /// elements, $m$ is `bits.unsigned_abs()`, and $k$ is `self.dimension()`.
139 ///
140 /// # Examples
141 /// See [here](super::shr#shr).
142 #[inline]
143 fn shr(mut self, bits: $t) -> IntegerVector {
144 self >>= bits;
145 self
146 }
147 }
148
149 impl Shr<$t> for &IntegerVector {
150 type Output = IntegerVector;
151
152 /// Right-shifts an [`IntegerVector`] (divides or multiplies it by a power of 2), taking
153 /// it by reference. Every element is shifted, and the dimension is unchanged.
154 ///
155 /// $f(v, k) = \lfloor v/2^k \rfloor$. The floor is taken entrywise, rounding toward
156 /// negative infinity; to round differently, use
157 /// [`entrywise_shr_round`](malachite_base::num::arithmetic::traits::EntrywiseShrRound).
158 ///
159 /// A negative `bits` shifts left, multiplying every element by $2^{-k}$.
160 ///
161 /// # Worst-case complexity
162 /// $T(n, m, k) = O(n + km)$
163 ///
164 /// $M(n, m, k) = O(n + km)$
165 ///
166 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the
167 /// elements, $m$ is `bits.unsigned_abs()`, and $k$ is `self.dimension()`.
168 ///
169 /// # Examples
170 /// See [here](super::shr#shr).
171 #[inline]
172 fn shr(self, bits: $t) -> IntegerVector {
173 shr_ref(self, bits)
174 }
175 }
176
177 impl ShrAssign<$t> for IntegerVector {
178 /// Right-shifts an [`IntegerVector`] (divides or multiplies it by a power of 2), in
179 /// place. Every element is shifted, and the dimension is unchanged.
180 ///
181 /// $v \gets \lfloor v/2^k \rfloor$. The floor is taken entrywise, rounding toward
182 /// negative infinity; to round differently, use
183 /// [`entrywise_shr_round`](malachite_base::num::arithmetic::traits::EntrywiseShrRound).
184 ///
185 /// A negative `bits` shifts left, multiplying every element by $2^{-k}$.
186 ///
187 /// # Worst-case complexity
188 /// $T(n, m, k) = O(n + km)$
189 ///
190 /// $M(n, m, k) = O(n + km)$
191 ///
192 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the
193 /// elements, $m$ is `bits.unsigned_abs()`, and $k$ is `self.dimension()`.
194 ///
195 /// # Examples
196 /// See [here](super::shr#shr_assign).
197 #[inline]
198 fn shr_assign(&mut self, bits: $t) {
199 shr_assign(self, bits);
200 }
201 }
202 };
203}
204apply_to_signeds!(impl_integer_vector_shr_signed);