dashu_int/
bits.rs

1//! Bitwise operators.
2
3use dashu_base::BitTest;
4
5use crate::{arch::word::Word, helper_macros, ibig::IBig, ops::PowerOfTwo, ubig::UBig, Sign::*};
6use core::{
7    cmp::Ordering,
8    mem,
9    ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not},
10};
11
12// Ops for UBig
13
14impl UBig {
15    /// Set the `n`-th bit, n starts from 0.
16    ///
17    /// # Examples
18    ///
19    /// ```
20    /// # use dashu_int::UBig;
21    /// let mut a = UBig::from(0b100u8);
22    /// a.set_bit(0);
23    /// assert_eq!(a, UBig::from(0b101u8));
24    /// a.set_bit(10);
25    /// assert_eq!(a, UBig::from(0b10000000101u16));
26    /// ```
27    #[inline]
28    pub fn set_bit(&mut self, n: usize) {
29        self.0 = mem::take(self).into_repr().set_bit(n);
30    }
31
32    /// Clear the `n`-th bit, `n` starts from 0.
33    ///
34    /// # Examples
35    ///
36    /// ```
37    /// # use dashu_int::UBig;
38    /// let mut a = UBig::from(0b101u8);
39    /// a.clear_bit(0);
40    /// assert_eq!(a, UBig::from(0b100u8));
41    /// ```
42    #[inline]
43    pub fn clear_bit(&mut self, n: usize) {
44        self.0 = mem::take(self).into_repr().clear_bit(n);
45    }
46
47    /// Returns the number of trailing zeros in the binary representation.
48    ///
49    /// In other words, it is the largest `n` such that 2 to the power of `n` divides the number.
50    ///
51    /// For 0, it returns `None`.
52    ///
53    /// # Examples
54    ///
55    /// ```
56    /// # use dashu_int::UBig;
57    /// assert_eq!(UBig::from(17u8).trailing_zeros(), Some(0));
58    /// assert_eq!(UBig::from(48u8).trailing_zeros(), Some(4));
59    /// assert_eq!(UBig::from(0b101000000u16).trailing_zeros(), Some(6));
60    /// assert_eq!(UBig::ZERO.trailing_zeros(), None);
61    /// ```
62    ///
63    /// # Availability
64    ///
65    /// Const since Rust 1.64
66    #[rustversion::attr(since(1.64), const)]
67    #[inline]
68    pub fn trailing_zeros(&self) -> Option<usize> {
69        self.repr().trailing_zeros()
70    }
71
72    /// Returns the number of trailing ones in the binary representation.
73    ///
74    /// In other words, it is the number of trailing zeros of it added by one.
75    ///
76    /// This method never returns [None].
77    ///
78    /// # Examples
79    ///
80    /// ```
81    /// # use dashu_int::UBig;
82    /// assert_eq!(UBig::from(17u8).trailing_ones(), Some(1));
83    /// assert_eq!(UBig::from(48u8).trailing_ones(), Some(0));
84    /// assert_eq!(UBig::from(0b101001111u16).trailing_ones(), Some(4));
85    /// assert_eq!(UBig::ZERO.trailing_ones(), Some(0));
86    /// ```
87    ///
88    /// # Availability
89    ///
90    /// Const since Rust 1.64
91    #[rustversion::attr(since(1.64), const)]
92    #[inline]
93    pub fn trailing_ones(&self) -> Option<usize> {
94        Some(self.repr().trailing_ones())
95    }
96
97    /// Split this integer into low bits and high bits.
98    ///
99    /// Its returns are equal to `(self & ((1 << n) - 1), self >> n)`.
100    ///
101    /// # Examples
102    ///
103    /// ```
104    /// # use dashu_int::UBig;
105    /// let (lo, hi) = UBig::from(0b10100011u8).split_bits(4);
106    /// assert_eq!(hi, UBig::from(0b1010u8));
107    /// assert_eq!(lo, UBig::from(0b0011u8));
108    ///
109    /// let x = UBig::from(0x90ffff3450897234u64);
110    /// let (lo, hi) = x.clone().split_bits(21);
111    /// assert_eq!(hi, (&x) >> 21);
112    /// assert_eq!(lo, x & ((UBig::ONE << 21) - 1u8));
113    /// ```
114    #[inline]
115    pub fn split_bits(self, n: usize) -> (UBig, UBig) {
116        let (lo, hi) = self.into_repr().split_bits(n);
117        (UBig(lo), UBig(hi))
118    }
119
120    /// Clear the high bits from `n+1`-th bit.
121    ///
122    /// This operation is equivalent to getting the lowest n bits on the integer
123    /// i.e. `self &= ((1 << n) - 1)`.
124    ///
125    /// # Examples
126    ///
127    /// ```
128    /// # use dashu_int::UBig;
129    /// let mut x = UBig::from(0b10100011u8);
130    /// x.clear_high_bits(4);
131    /// assert_eq!(x, UBig::from(0b0011u8));
132    ///
133    /// let mut x = UBig::from(0x90ffff3450897234u64);
134    /// let lo = (&x) & ((UBig::ONE << 21) - 1u8);
135    /// x.clear_high_bits(21);
136    /// assert_eq!(x, lo);
137    /// ```
138    #[inline]
139    pub fn clear_high_bits(&mut self, n: usize) {
140        self.0 = mem::take(self).into_repr().clear_high_bits(n);
141    }
142
143    /// Count the 1 bits in the integer
144    ///
145    /// # Examples
146    ///
147    /// ```
148    /// # use dashu_base::BitTest;
149    /// # use dashu_int::UBig;
150    /// assert_eq!(UBig::from(0b10100011u8).count_ones(), 4);
151    /// assert_eq!(UBig::from(0x90ffff3450897234u64).count_ones(), 33);
152    ///
153    /// let x = (UBig::ONE << 150) - 1u8;
154    /// assert_eq!(x.count_ones(), x.bit_len());
155    /// ```
156    #[inline]
157    pub fn count_ones(&self) -> usize {
158        self.repr().count_ones()
159    }
160
161    /// Count the 0 bits in the integer after the leading bit 1.
162    ///
163    /// If the integer is zero, [None] will be returned.
164    ///
165    /// # Examples
166    ///
167    /// ```
168    /// # use dashu_base::BitTest;
169    /// # use dashu_int::UBig;
170    /// assert_eq!(UBig::from(0b10100011u8).count_zeros(), Some(4));
171    /// assert_eq!(UBig::from(0x90ffff3450897234u64).count_zeros(), Some(31));
172    ///
173    /// let x = (UBig::ONE << 150) - 1u8;
174    /// assert_eq!(x.count_zeros(), Some(0));
175    /// ```
176    pub fn count_zeros(&self) -> Option<usize> {
177        self.repr().count_zeros()
178    }
179}
180
181helper_macros::forward_ubig_binop_to_repr!(impl BitAnd, bitand);
182helper_macros::forward_ubig_binop_to_repr!(impl BitOr, bitor);
183helper_macros::forward_ubig_binop_to_repr!(impl BitXor, bitxor);
184helper_macros::forward_ubig_binop_to_repr!(impl AndNot, and_not);
185helper_macros::impl_binop_assign_by_taking!(impl BitAndAssign<UBig> for UBig, bitand_assign, bitand);
186helper_macros::impl_binop_assign_by_taking!(impl BitOrAssign<UBig> for UBig, bitor_assign, bitor);
187helper_macros::impl_binop_assign_by_taking!(impl BitXorAssign<UBig> for UBig, bitxor_assign, bitxor);
188
189impl BitTest for UBig {
190    #[inline]
191    fn bit(&self, n: usize) -> bool {
192        self.repr().bit(n)
193    }
194    #[inline]
195    fn bit_len(&self) -> usize {
196        self.repr().bit_len()
197    }
198}
199
200impl PowerOfTwo for UBig {
201    #[inline]
202    fn is_power_of_two(&self) -> bool {
203        self.repr().is_power_of_two()
204    }
205
206    #[inline]
207    fn next_power_of_two(self) -> UBig {
208        UBig(self.into_repr().next_power_of_two())
209    }
210}
211
212// Ops for IBig
213
214impl IBig {
215    /// Returns the number of trailing zeros in the two's complement binary representation.
216    ///
217    /// In other words, it is the largest `n` such that 2 to the power of `n` divides the number.
218    ///
219    /// For 0, it returns `None`.
220    ///
221    /// # Examples
222    ///
223    /// ```
224    /// # use dashu_int::IBig;
225    /// assert_eq!(IBig::from(17).trailing_zeros(), Some(0));
226    /// assert_eq!(IBig::from(-48).trailing_zeros(), Some(4));
227    /// assert_eq!(IBig::from(-0b101000000).trailing_zeros(), Some(6));
228    /// assert_eq!(IBig::ZERO.trailing_zeros(), None);
229    /// ```
230    ///
231    /// # Availability
232    ///
233    /// Const since Rust 1.64
234    #[rustversion::attr(since(1.64), const)]
235    #[inline]
236    pub fn trailing_zeros(&self) -> Option<usize> {
237        self.as_sign_repr().1.trailing_zeros()
238    }
239
240    /// Returns the number of trailing ones in the two's complement binary representation.
241    ///
242    /// For positive `self`, it's equivalent to `self.unsigned_abs().trailing_zeros()`.
243    /// For negative `self`, it's equivalent to `(!self.unsigned_abs() + 1).trailing_zeros()`.
244    ///
245    /// For -1, it returns `None`.
246    ///
247    /// # Examples
248    ///
249    /// ```
250    /// # use dashu_int::IBig;
251    /// assert_eq!(IBig::from(17).trailing_ones(), Some(1));
252    /// assert_eq!(IBig::from(-48).trailing_ones(), Some(0));
253    /// assert_eq!(IBig::from(-0b101000001).trailing_ones(), Some(6));
254    /// assert_eq!(IBig::NEG_ONE.trailing_ones(), None);
255    /// ```
256    ///
257    /// # Availability
258    ///
259    /// Const since Rust 1.64
260    #[rustversion::attr(since(1.64), const)]
261    pub fn trailing_ones(&self) -> Option<usize> {
262        let (sign, repr) = self.as_sign_repr();
263        match sign {
264            Positive => Some(repr.trailing_ones()),
265            Negative => repr.trailing_ones_neg(),
266        }
267    }
268}
269
270impl BitTest for IBig {
271    #[inline]
272    fn bit(&self, n: usize) -> bool {
273        let (sign, repr) = self.as_sign_repr();
274        match sign {
275            Positive => repr.bit(n),
276            Negative => {
277                let zeros = repr.trailing_zeros().unwrap();
278                match n.cmp(&zeros) {
279                    Ordering::Equal => true,
280                    Ordering::Greater => !repr.bit(n),
281                    Ordering::Less => false,
282                }
283            }
284        }
285    }
286
287    #[inline]
288    fn bit_len(&self) -> usize {
289        self.as_sign_repr().1.bit_len()
290    }
291}
292
293/// Bitwise AND NOT operation. For internal use only, used for implementing
294/// bit operations on IBig.
295///
296/// `x.and_not(y)` is equivalent to `x & !y` for primitive integers.
297trait AndNot<Rhs = Self> {
298    type Output;
299
300    fn and_not(self, rhs: Rhs) -> Self::Output;
301}
302
303mod repr {
304    use super::*;
305    use crate::{
306        arch::word::DoubleWord,
307        buffer::Buffer,
308        math::{self, ceil_div, ones_dword, ones_word},
309        primitive::{lowest_dword, split_dword, DWORD_BITS_USIZE, WORD_BITS_USIZE},
310        repr::{
311            Repr,
312            TypedRepr::{self, *},
313            TypedReprRef::{self, *},
314        },
315        shift_ops,
316    };
317
318    impl<'a> TypedReprRef<'a> {
319        #[inline]
320        pub fn bit(self, n: usize) -> bool {
321            match self {
322                RefSmall(dword) => n < DWORD_BITS_USIZE && dword & 1 << n != 0,
323                RefLarge(buffer) => {
324                    let idx = n / WORD_BITS_USIZE;
325                    idx < buffer.len() && buffer[idx] & 1 << (n % WORD_BITS_USIZE) != 0
326                }
327            }
328        }
329
330        #[inline]
331        pub fn bit_len(self) -> usize {
332            match self {
333                RefSmall(dword) => math::bit_len(dword) as usize,
334                RefLarge(words) => {
335                    words.len() * WORD_BITS_USIZE - words.last().unwrap().leading_zeros() as usize
336                }
337            }
338        }
339
340        /// Check if low n-bits are not all zeros
341        #[inline]
342        pub fn are_low_bits_nonzero(self, n: usize) -> bool {
343            match self {
344                Self::RefSmall(dword) => are_dword_low_bits_nonzero(dword, n),
345                Self::RefLarge(words) => are_slice_low_bits_nonzero(words, n),
346            }
347        }
348
349        /// Check if the underlying number is a power of two
350        #[inline]
351        pub fn is_power_of_two(self) -> bool {
352            match self {
353                RefSmall(dword) => dword.is_power_of_two(),
354                RefLarge(words) => {
355                    words[..words.len() - 1].iter().all(|x| *x == 0)
356                        && words.last().unwrap().is_power_of_two()
357                }
358            }
359        }
360
361        pub const fn trailing_zeros(self) -> Option<usize> {
362            match self {
363                RefSmall(0) => None,
364                RefSmall(dword) => Some(dword.trailing_zeros() as usize),
365                RefLarge(words) => Some(trailing_zeros_large(words)),
366            }
367        }
368
369        pub const fn trailing_ones(self) -> usize {
370            match self {
371                RefSmall(dword) => dword.trailing_ones() as usize,
372                RefLarge(words) => trailing_ones_large(words),
373            }
374        }
375
376        pub fn count_ones(self) -> usize {
377            match self {
378                RefSmall(dword) => dword.count_ones() as usize,
379                RefLarge(words) => words.iter().map(|w| w.count_ones() as usize).sum(),
380            }
381        }
382
383        pub fn count_zeros(self) -> Option<usize> {
384            match self {
385                RefSmall(0) => None,
386                RefSmall(dword) => Some((dword.count_zeros() - dword.leading_zeros()) as usize),
387                RefLarge(words) => {
388                    let zeros: usize = words.iter().map(|w| w.count_zeros() as usize).sum();
389                    Some(zeros - words.last().unwrap().leading_zeros() as usize)
390                }
391            }
392        }
393
394        /// Number of trailing ones in (-self)
395        pub const fn trailing_ones_neg(self) -> Option<usize> {
396            match self {
397                RefSmall(0) => Some(0),
398                RefSmall(1) => None,
399                RefSmall(dword) => Some((!dword + 1).trailing_ones() as usize),
400                RefLarge(words) => {
401                    if words[0] & 1 == 0 {
402                        Some(0)
403                    } else {
404                        Some(trailing_zeros_large_shifted_by_one(words) + 1)
405                    }
406                }
407            }
408        }
409    }
410
411    impl TypedRepr {
412        #[inline]
413        pub fn next_power_of_two(self) -> Repr {
414            match self {
415                Small(dword) => match dword.checked_next_power_of_two() {
416                    Some(p) => Repr::from_dword(p),
417                    None => {
418                        let mut buffer = Buffer::allocate(3);
419                        buffer.push_zeros(2);
420                        buffer.push(1);
421                        Repr::from_buffer(buffer)
422                    }
423                },
424                Large(buffer) => next_power_of_two_large(buffer),
425            }
426        }
427
428        pub fn set_bit(self, n: usize) -> Repr {
429            match self {
430                Small(dword) => {
431                    if n < DWORD_BITS_USIZE {
432                        Repr::from_dword(dword | 1 << n)
433                    } else {
434                        with_bit_dword_spilled(dword, n)
435                    }
436                }
437                Large(buffer) => with_bit_large(buffer, n),
438            }
439        }
440
441        pub fn clear_bit(self, n: usize) -> Repr {
442            match self {
443                Small(dword) => {
444                    if n < DWORD_BITS_USIZE {
445                        Repr::from_dword(dword & !(1 << n))
446                    } else {
447                        Repr::from_dword(dword)
448                    }
449                }
450                Large(mut buffer) => {
451                    let idx = n / WORD_BITS_USIZE;
452                    if idx < buffer.len() {
453                        buffer[idx] &= !(1 << (n % WORD_BITS_USIZE));
454                    }
455                    Repr::from_buffer(buffer)
456                }
457            }
458        }
459
460        pub fn clear_high_bits(self, n: usize) -> Repr {
461            match self {
462                Small(dword) => {
463                    if n < DWORD_BITS_USIZE {
464                        Repr::from_dword(dword & ones_dword(n as u32))
465                    } else {
466                        Repr::from_dword(dword)
467                    }
468                }
469                Large(buffer) => clear_high_bits_large(buffer, n),
470            }
471        }
472
473        pub fn split_bits(self, n: usize) -> (Repr, Repr) {
474            match self {
475                Small(dword) => {
476                    if n < DWORD_BITS_USIZE {
477                        (
478                            Repr::from_dword(dword & ones_dword(n as u32)),
479                            Repr::from_dword(dword >> n),
480                        )
481                    } else {
482                        (Repr::from_dword(dword), Repr::zero())
483                    }
484                }
485                Large(buffer) => {
486                    if n == 0 {
487                        (Repr::zero(), Repr::from_buffer(buffer))
488                    } else {
489                        let hi = shift_ops::repr::shr_large_ref(&buffer, n);
490                        let lo = clear_high_bits_large(buffer, n);
491                        (lo, hi)
492                    }
493                }
494            }
495        }
496    }
497
498    #[inline]
499    fn are_dword_low_bits_nonzero(dword: DoubleWord, n: usize) -> bool {
500        // For n >= DWORD_BITS, every bit of the dword is "low" so just test for any
501        // set bit. `ones_dword(DWORD_BITS as u32)` would underflow its shift, so we
502        // must early-return here rather than rely on it.
503        if n >= DWORD_BITS_USIZE {
504            return dword != 0;
505        }
506        dword & ones_dword(n as u32) != 0
507    }
508
509    fn are_slice_low_bits_nonzero(words: &[Word], n: usize) -> bool {
510        let n_words = n / WORD_BITS_USIZE;
511        if n_words >= words.len() {
512            true
513        } else {
514            let n_top = (n % WORD_BITS_USIZE) as u32;
515            words[..n_words].iter().any(|x| *x != 0) || words[n_words] & ones_word(n_top) != 0
516        }
517    }
518
519    fn next_power_of_two_large(mut buffer: Buffer) -> Repr {
520        debug_assert!(*buffer.last().unwrap() != 0);
521
522        let n = buffer.len();
523        let mut iter = buffer[..n - 1].iter_mut().skip_while(|x| **x == 0);
524
525        let carry = match iter.next() {
526            None => 0,
527            Some(x) => {
528                *x = 0;
529                for x in iter {
530                    *x = 0;
531                }
532                1
533            }
534        };
535
536        let last = buffer.last_mut().unwrap();
537        match last
538            .checked_add(carry)
539            .and_then(|x| x.checked_next_power_of_two())
540        {
541            Some(p) => *last = p,
542            None => {
543                *last = 0;
544                buffer.push_resizing(1);
545            }
546        }
547
548        Repr::from_buffer(buffer)
549    }
550
551    fn with_bit_dword_spilled(dword: DoubleWord, n: usize) -> Repr {
552        debug_assert!(n >= DWORD_BITS_USIZE);
553        let idx = n / WORD_BITS_USIZE;
554        let mut buffer = Buffer::allocate(idx + 1);
555        let (lo, hi) = split_dword(dword);
556        buffer.push(lo);
557        buffer.push(hi);
558        buffer.push_zeros(idx - 2);
559        buffer.push(1 << (n % WORD_BITS_USIZE));
560        Repr::from_buffer(buffer)
561    }
562
563    fn with_bit_large(mut buffer: Buffer, n: usize) -> Repr {
564        let idx = n / WORD_BITS_USIZE;
565        if idx < buffer.len() {
566            buffer[idx] |= 1 << (n % WORD_BITS_USIZE);
567        } else {
568            buffer.ensure_capacity(idx + 1);
569            buffer.push_zeros(idx - buffer.len());
570            buffer.push(1 << (n % WORD_BITS_USIZE));
571        }
572        Repr::from_buffer(buffer)
573    }
574
575    /// Count the trailing zero bits in the words.
576    /// Panics if the input is zero.
577    #[inline]
578    const fn trailing_zeros_large(words: &[Word]) -> usize {
579        // Const equivalent to:
580        // let zero_words = words.iter().position(|&word| word != 0).unwrap();
581        let mut zero_words = 0;
582        while zero_words < words.len() {
583            if words[zero_words] != 0 {
584                break;
585            }
586            zero_words += 1;
587        }
588
589        let zero_bits = words[zero_words].trailing_zeros() as usize;
590        zero_words * WORD_BITS_USIZE + zero_bits
591    }
592
593    /// Count the trailing zero bits in the words shifted right by one.
594    /// Panics if the input is zero.
595    #[inline]
596    const fn trailing_zeros_large_shifted_by_one(words: &[Word]) -> usize {
597        debug_assert!(words.len() >= 2);
598        let zero_begin = (words[0] >> 1).trailing_zeros() as usize;
599        if zero_begin < (WORD_BITS_USIZE - 1) {
600            zero_begin
601        } else {
602            let mut zero_words = 1;
603            while zero_words < words.len() {
604                if words[zero_words] != 0 {
605                    break;
606                }
607                zero_words += 1;
608            }
609
610            let zero_bits = words[zero_words].trailing_zeros() as usize;
611            (zero_words - 1) * WORD_BITS_USIZE + zero_bits + zero_begin - 1
612        }
613    }
614
615    /// Count the trailing one bits in the words.
616    #[inline]
617    const fn trailing_ones_large(words: &[Word]) -> usize {
618        // Const equivalent to:
619        // let one_words = words.iter().position(|&word| word != Word::MAX).unwrap();
620        let mut one_words = 1;
621        while one_words < words.len() {
622            if words[one_words] != Word::MAX {
623                break;
624            }
625            one_words += 1;
626        }
627
628        let one_bits = words[one_words].trailing_ones() as usize;
629        one_words * WORD_BITS_USIZE + one_bits
630    }
631
632    #[inline]
633    fn clear_high_bits_large(mut buffer: Buffer, n: usize) -> Repr {
634        let n_words = ceil_div(n, WORD_BITS_USIZE);
635        if n_words > buffer.len() {
636            Repr::from_buffer(buffer)
637        } else {
638            buffer.truncate(n_words);
639            if n % WORD_BITS_USIZE != 0 {
640                let last = buffer.last_mut().unwrap();
641                *last &= ones_word((n % WORD_BITS_USIZE) as u32);
642            }
643            Repr::from_buffer(buffer)
644        }
645    }
646
647    impl BitAnd<TypedRepr> for TypedRepr {
648        type Output = Repr;
649
650        #[inline]
651        fn bitand(self, rhs: TypedRepr) -> Repr {
652            match (self, rhs) {
653                (Small(dword0), Small(dword1)) => Repr::from_dword(dword0 & dword1),
654                (Small(dword0), Large(buffer1)) => {
655                    Repr::from_dword(dword0 & buffer1.lowest_dword())
656                }
657                (Large(buffer0), Small(dword1)) => {
658                    Repr::from_dword(buffer0.lowest_dword() & dword1)
659                }
660                (Large(buffer0), Large(buffer1)) => {
661                    if buffer0.len() <= buffer1.len() {
662                        bitand_large(buffer0, &buffer1)
663                    } else {
664                        bitand_large(buffer1, &buffer0)
665                    }
666                }
667            }
668        }
669    }
670
671    impl<'r> BitAnd<TypedReprRef<'r>> for TypedRepr {
672        type Output = Repr;
673
674        #[inline]
675        fn bitand(self, rhs: TypedReprRef) -> Repr {
676            match (self, rhs) {
677                (Small(dword0), RefSmall(dword1)) => Repr::from_dword(dword0 & dword1),
678                (Small(dword0), RefLarge(buffer1)) => {
679                    Repr::from_dword(dword0 & lowest_dword(buffer1))
680                }
681                (Large(buffer0), RefSmall(dword1)) => {
682                    Repr::from_dword(buffer0.lowest_dword() & dword1)
683                }
684                (Large(buffer0), RefLarge(buffer1)) => bitand_large(buffer0, buffer1),
685            }
686        }
687    }
688
689    impl<'l> BitAnd<TypedRepr> for TypedReprRef<'l> {
690        type Output = Repr;
691
692        #[inline]
693        fn bitand(self, rhs: TypedRepr) -> Repr {
694            // bitand is commutative
695            rhs.bitand(self)
696        }
697    }
698
699    impl<'l, 'r> BitAnd<TypedReprRef<'r>> for TypedReprRef<'l> {
700        type Output = Repr;
701
702        #[inline]
703        fn bitand(self, rhs: TypedReprRef) -> Repr {
704            match (self, rhs) {
705                (RefSmall(dword0), RefSmall(dword1)) => Repr::from_dword(dword0 & dword1),
706                (RefSmall(dword0), RefLarge(buffer1)) => {
707                    Repr::from_dword(dword0 & lowest_dword(buffer1))
708                }
709                (RefLarge(buffer0), RefSmall(dword1)) => {
710                    Repr::from_dword(lowest_dword(buffer0) & dword1)
711                }
712                (RefLarge(buffer0), RefLarge(buffer1)) => {
713                    if buffer0.len() <= buffer1.len() {
714                        bitand_large(buffer0.into(), buffer1)
715                    } else {
716                        bitand_large(buffer1.into(), buffer0)
717                    }
718                }
719            }
720        }
721    }
722
723    fn bitand_large(mut buffer: Buffer, rhs: &[Word]) -> Repr {
724        if buffer.len() > rhs.len() {
725            buffer.truncate(rhs.len());
726        }
727        for (x, y) in buffer.iter_mut().zip(rhs.iter()) {
728            *x &= *y;
729        }
730        Repr::from_buffer(buffer)
731    }
732
733    impl BitOr<TypedRepr> for TypedRepr {
734        type Output = Repr;
735
736        #[inline]
737        fn bitor(self, rhs: TypedRepr) -> Repr {
738            match (self, rhs) {
739                (Small(dword0), Small(dword1)) => Repr::from_dword(dword0 | dword1),
740                (Small(dword0), Large(buffer1)) => bitor_large_dword(buffer1, dword0),
741                (Large(buffer0), Small(dword1)) => bitor_large_dword(buffer0, dword1),
742                (Large(buffer0), Large(buffer1)) => {
743                    if buffer0.len() >= buffer1.len() {
744                        bitor_large(buffer0, &buffer1)
745                    } else {
746                        bitor_large(buffer1, &buffer0)
747                    }
748                }
749            }
750        }
751    }
752
753    impl<'r> BitOr<TypedReprRef<'r>> for TypedRepr {
754        type Output = Repr;
755
756        #[inline]
757        fn bitor(self, rhs: TypedReprRef) -> Repr {
758            match (self, rhs) {
759                (Small(dword0), RefSmall(dword1)) => Repr::from_dword(dword0 | dword1),
760                (Small(dword0), RefLarge(buffer1)) => bitor_large_dword(buffer1.into(), dword0),
761                (Large(buffer0), RefSmall(dword1)) => bitor_large_dword(buffer0, dword1),
762                (Large(buffer0), RefLarge(buffer1)) => bitor_large(buffer0, buffer1),
763            }
764        }
765    }
766
767    impl<'l> BitOr<TypedRepr> for TypedReprRef<'l> {
768        type Output = Repr;
769
770        #[inline]
771        fn bitor(self, rhs: TypedRepr) -> Repr {
772            // bitor is commutative
773            rhs.bitor(self)
774        }
775    }
776
777    impl<'l, 'r> BitOr<TypedReprRef<'r>> for TypedReprRef<'l> {
778        type Output = Repr;
779
780        #[inline]
781        fn bitor(self, rhs: TypedReprRef) -> Repr {
782            match (self, rhs) {
783                (RefSmall(dword0), RefSmall(dword1)) => Repr::from_dword(dword0 | dword1),
784                (RefSmall(dword0), RefLarge(buffer1)) => bitor_large_dword(buffer1.into(), dword0),
785                (RefLarge(buffer0), RefSmall(dword1)) => bitor_large_dword(buffer0.into(), dword1),
786                (RefLarge(buffer0), RefLarge(buffer1)) => {
787                    if buffer0.len() >= buffer1.len() {
788                        bitor_large(buffer0.into(), buffer1)
789                    } else {
790                        bitor_large(buffer1.into(), buffer0)
791                    }
792                }
793            }
794        }
795    }
796
797    fn bitor_large_dword(mut buffer: Buffer, rhs: DoubleWord) -> Repr {
798        debug_assert!(buffer.len() >= 2);
799
800        let (lo, hi) = split_dword(rhs);
801        let (b_lo, b_hi) = buffer.lowest_dword_mut();
802        *b_lo |= lo;
803        *b_hi |= hi;
804        Repr::from_buffer(buffer)
805    }
806
807    fn bitor_large(mut buffer: Buffer, rhs: &[Word]) -> Repr {
808        for (x, y) in buffer.iter_mut().zip(rhs.iter()) {
809            *x |= *y;
810        }
811        if rhs.len() > buffer.len() {
812            buffer.ensure_capacity(rhs.len());
813            buffer.push_slice(&rhs[buffer.len()..]);
814        }
815        Repr::from_buffer(buffer)
816    }
817
818    impl BitXor<TypedRepr> for TypedRepr {
819        type Output = Repr;
820
821        #[inline]
822        fn bitxor(self, rhs: TypedRepr) -> Repr {
823            match (self, rhs) {
824                (Small(dword0), Small(dword1)) => Repr::from_dword(dword0 ^ dword1),
825                (Small(dword0), Large(buffer1)) => bitxor_large_dword(buffer1, dword0),
826                (Large(buffer0), Small(dword1)) => bitxor_large_dword(buffer0, dword1),
827                (Large(buffer0), Large(buffer1)) => {
828                    if buffer0.len() >= buffer1.len() {
829                        bitxor_large(buffer0, &buffer1)
830                    } else {
831                        bitxor_large(buffer1, &buffer0)
832                    }
833                }
834            }
835        }
836    }
837
838    impl<'r> BitXor<TypedReprRef<'r>> for TypedRepr {
839        type Output = Repr;
840
841        #[inline]
842        fn bitxor(self, rhs: TypedReprRef) -> Repr {
843            match (self, rhs) {
844                (Small(dword0), RefSmall(dword1)) => Repr::from_dword(dword0 ^ dword1),
845                (Small(dword0), RefLarge(buffer1)) => bitxor_large_dword(buffer1.into(), dword0),
846                (Large(buffer0), RefSmall(dword1)) => bitxor_large_dword(buffer0, dword1),
847                (Large(buffer0), RefLarge(buffer1)) => bitxor_large(buffer0, buffer1),
848            }
849        }
850    }
851
852    impl<'l> BitXor<TypedRepr> for TypedReprRef<'l> {
853        type Output = Repr;
854
855        #[inline]
856        fn bitxor(self, rhs: TypedRepr) -> Repr {
857            // bitxor is commutative
858            rhs.bitxor(self)
859        }
860    }
861
862    impl<'l, 'r> BitXor<TypedReprRef<'r>> for TypedReprRef<'l> {
863        type Output = Repr;
864
865        #[inline]
866        fn bitxor(self, rhs: TypedReprRef) -> Repr {
867            match (self, rhs) {
868                (RefSmall(dword0), RefSmall(dword1)) => Repr::from_dword(dword0 ^ dword1),
869                (RefSmall(dword0), RefLarge(buffer1)) => bitxor_large_dword(buffer1.into(), dword0),
870                (RefLarge(buffer0), RefSmall(dword1)) => bitxor_large_dword(buffer0.into(), dword1),
871                (RefLarge(buffer0), RefLarge(buffer1)) => {
872                    if buffer0.len() >= buffer1.len() {
873                        bitxor_large(buffer0.into(), buffer1)
874                    } else {
875                        bitxor_large(buffer1.into(), buffer0)
876                    }
877                }
878            }
879        }
880    }
881
882    fn bitxor_large_dword(mut buffer: Buffer, rhs: DoubleWord) -> Repr {
883        debug_assert!(buffer.len() >= 2);
884
885        let (lo, hi) = split_dword(rhs);
886        let (b_lo, b_hi) = buffer.lowest_dword_mut();
887        *b_lo ^= lo;
888        *b_hi ^= hi;
889        Repr::from_buffer(buffer)
890    }
891
892    fn bitxor_large(mut buffer: Buffer, rhs: &[Word]) -> Repr {
893        for (x, y) in buffer.iter_mut().zip(rhs.iter()) {
894            *x ^= *y;
895        }
896        if rhs.len() > buffer.len() {
897            buffer.ensure_capacity(rhs.len());
898            buffer.push_slice(&rhs[buffer.len()..]);
899        }
900        Repr::from_buffer(buffer)
901    }
902
903    impl AndNot<TypedRepr> for TypedRepr {
904        type Output = Repr;
905
906        #[inline]
907        fn and_not(self, rhs: TypedRepr) -> Repr {
908            match (self, rhs) {
909                (Small(dword0), Small(dword1)) => Repr::from_dword(dword0 & !dword1),
910                (Small(dword0), Large(buffer1)) => {
911                    Repr::from_dword(dword0 & !buffer1.lowest_dword())
912                }
913                (Large(buffer0), Small(dword1)) => and_not_large_dword(buffer0, dword1),
914                (Large(buffer0), Large(buffer1)) => and_not_large(buffer0, &buffer1),
915            }
916        }
917    }
918
919    impl<'r> AndNot<TypedReprRef<'r>> for TypedRepr {
920        type Output = Repr;
921
922        #[inline]
923        fn and_not(self, rhs: TypedReprRef) -> Repr {
924            match (self, rhs) {
925                (Small(dword0), RefSmall(dword1)) => Repr::from_dword(dword0 & !dword1),
926                (Small(dword0), RefLarge(buffer1)) => {
927                    Repr::from_dword(dword0 & !lowest_dword(buffer1))
928                }
929                (Large(buffer0), RefSmall(dword1)) => and_not_large_dword(buffer0, dword1),
930                (Large(buffer0), RefLarge(buffer1)) => and_not_large(buffer0, buffer1),
931            }
932        }
933    }
934
935    impl<'l> AndNot<TypedRepr> for TypedReprRef<'l> {
936        type Output = Repr;
937
938        #[inline]
939        fn and_not(self, rhs: TypedRepr) -> Repr {
940            match (self, rhs) {
941                (RefSmall(dword0), Small(dword1)) => Repr::from_dword(dword0 & !dword1),
942                (RefSmall(dword0), Large(buffer1)) => {
943                    Repr::from_dword(dword0 & !buffer1.lowest_dword())
944                }
945                (RefLarge(buffer0), Small(dword1)) => and_not_large_dword(buffer0.into(), dword1),
946                (RefLarge(buffer0), Large(buffer1)) => and_not_large(buffer0.into(), &buffer1),
947            }
948        }
949    }
950
951    impl<'l, 'r> AndNot<TypedReprRef<'r>> for TypedReprRef<'l> {
952        type Output = Repr;
953
954        #[inline]
955        fn and_not(self, rhs: TypedReprRef) -> Repr {
956            match (self, rhs) {
957                (RefSmall(dword0), RefSmall(dword1)) => Repr::from_dword(dword0 & !dword1),
958                (RefSmall(dword0), RefLarge(buffer1)) => {
959                    Repr::from_dword(dword0 & !lowest_dword(buffer1))
960                }
961                (RefLarge(buffer0), RefSmall(dword1)) => {
962                    and_not_large_dword(buffer0.into(), dword1)
963                }
964                (RefLarge(buffer0), RefLarge(buffer1)) => and_not_large(buffer0.into(), buffer1),
965            }
966        }
967    }
968
969    fn and_not_large_dword(mut buffer: Buffer, rhs: DoubleWord) -> Repr {
970        debug_assert!(buffer.len() >= 2);
971
972        let (lo, hi) = split_dword(rhs);
973        let (b_lo, b_hi) = buffer.lowest_dword_mut();
974        *b_lo &= !lo;
975        *b_hi &= !hi;
976        Repr::from_buffer(buffer)
977    }
978
979    fn and_not_large(mut buffer: Buffer, rhs: &[Word]) -> Repr {
980        for (x, y) in buffer.iter_mut().zip(rhs.iter()) {
981            *x &= !*y;
982        }
983        Repr::from_buffer(buffer)
984    }
985}
986
987impl Not for IBig {
988    type Output = IBig;
989
990    #[inline]
991    fn not(self) -> IBig {
992        let (sign, mag) = self.into_sign_repr();
993        match sign {
994            Positive => IBig(mag.add_one().with_sign(Negative)),
995            Negative => IBig(mag.sub_one().with_sign(Positive)),
996        }
997    }
998}
999
1000impl Not for &IBig {
1001    type Output = IBig;
1002
1003    #[inline]
1004    fn not(self) -> IBig {
1005        let (sign, mag) = self.as_sign_repr();
1006        match sign {
1007            Positive => IBig(mag.add_one().with_sign(Negative)),
1008            Negative => IBig(mag.sub_one().with_sign(Positive)),
1009        }
1010    }
1011}
1012
1013macro_rules! impl_ibig_bitand {
1014    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {
1015        match ($sign0, $sign1) {
1016            (Positive, Positive) => IBig($mag0.bitand($mag1)),
1017            (Positive, Negative) => IBig($mag0.and_not($mag1.sub_one().into_typed())),
1018            (Negative, Positive) => IBig($mag1.and_not($mag0.sub_one().into_typed())),
1019            (Negative, Negative) => !IBig(
1020                $mag0
1021                    .sub_one()
1022                    .into_typed()
1023                    .bitor($mag1.sub_one().into_typed()),
1024            ),
1025        }
1026    };
1027}
1028macro_rules! impl_ibig_bitor {
1029    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {
1030        match ($sign0, $sign1) {
1031            (Positive, Positive) => IBig($mag0.bitor($mag1)),
1032            (Positive, Negative) => !IBig($mag1.sub_one().into_typed().and_not($mag0)),
1033            (Negative, Positive) => !IBig($mag0.sub_one().into_typed().and_not($mag1)),
1034            (Negative, Negative) => !IBig(
1035                $mag0
1036                    .sub_one()
1037                    .into_typed()
1038                    .bitand($mag1.sub_one().into_typed()),
1039            ),
1040        }
1041    };
1042}
1043macro_rules! impl_ibig_bitxor {
1044    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {
1045        match ($sign0, $sign1) {
1046            (Positive, Positive) => IBig($mag0.bitxor($mag1)),
1047            (Positive, Negative) => !IBig($mag0.bitxor($mag1.sub_one().into_typed())),
1048            (Negative, Positive) => !IBig($mag0.sub_one().into_typed().bitxor($mag1)),
1049            (Negative, Negative) => IBig(
1050                $mag0
1051                    .sub_one()
1052                    .into_typed()
1053                    .bitxor($mag1.sub_one().into_typed()),
1054            ),
1055        }
1056    };
1057}
1058helper_macros::forward_ibig_binop_to_repr!(impl BitAnd, bitand, Output = IBig, impl_ibig_bitand);
1059helper_macros::forward_ibig_binop_to_repr!(impl BitOr, bitor, Output = IBig, impl_ibig_bitor);
1060helper_macros::forward_ibig_binop_to_repr!(impl BitXor, bitxor, Output = IBig, impl_ibig_bitxor);
1061helper_macros::impl_binop_assign_by_taking!(impl BitAndAssign<IBig> for IBig, bitand_assign, bitand);
1062helper_macros::impl_binop_assign_by_taking!(impl BitOrAssign<IBig> for IBig, bitor_assign, bitor);
1063helper_macros::impl_binop_assign_by_taking!(impl BitXorAssign<IBig> for IBig, bitxor_assign, bitxor);
1064
1065// Ops between UBig & IBig
1066
1067macro_rules! impl_ubig_ibig_bitand {
1068    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {{
1069        debug_assert_eq!($sign0, Positive);
1070        match $sign1 {
1071            Positive => UBig($mag0.bitand($mag1)),
1072            Negative => UBig($mag0.and_not($mag1.sub_one().into_typed())),
1073        }
1074    }};
1075}
1076macro_rules! impl_ibig_ubig_bitand {
1077    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {{
1078        debug_assert_eq!($sign1, Positive);
1079        match $sign0 {
1080            Positive => UBig($mag1.bitand($mag0)),
1081            Negative => UBig($mag1.and_not($mag0.sub_one().into_typed())),
1082        }
1083    }};
1084}
1085helper_macros::forward_ubig_ibig_binop_to_repr!(
1086    impl BitAnd,
1087    bitand,
1088    Output = UBig,
1089    impl_ubig_ibig_bitand
1090);
1091helper_macros::forward_ubig_ibig_binop_to_repr!(impl BitOr, bitor, Output = IBig, impl_ibig_bitor);
1092helper_macros::forward_ubig_ibig_binop_to_repr!(
1093    impl BitXor,
1094    bitxor,
1095    Output = IBig,
1096    impl_ibig_bitxor
1097);
1098helper_macros::impl_binop_assign_by_taking!(impl BitAndAssign<IBig> for UBig, bitand_assign, bitand);
1099helper_macros::forward_ibig_ubig_binop_to_repr!(
1100    impl BitAnd,
1101    bitand,
1102    Output = UBig,
1103    impl_ibig_ubig_bitand
1104);
1105helper_macros::forward_ibig_ubig_binop_to_repr!(impl BitOr, bitor, Output = IBig, impl_ibig_bitor);
1106helper_macros::forward_ibig_ubig_binop_to_repr!(
1107    impl BitXor,
1108    bitxor,
1109    Output = IBig,
1110    impl_ibig_bitxor
1111);
1112helper_macros::impl_binop_assign_by_taking!(impl BitAndAssign<UBig> for IBig, bitand_assign, bitand);
1113helper_macros::impl_binop_assign_by_taking!(impl BitOrAssign<UBig> for IBig, bitor_assign, bitor);
1114helper_macros::impl_binop_assign_by_taking!(impl BitXorAssign<UBig> for IBig, bitxor_assign, bitxor);
1115
1116// Ops with primitives
1117
1118macro_rules! impl_bit_ops_primitive_with_ubig {
1119    ($($t:ty)*) => {$(
1120        helper_macros::impl_commutative_binop_with_primitive!(impl BitAnd<$t> for UBig, bitand -> $t);
1121        helper_macros::impl_commutative_binop_with_primitive!(impl BitOr<$t> for UBig, bitor);
1122        helper_macros::impl_commutative_binop_with_primitive!(impl BitXor<$t> for UBig, bitxor);
1123        helper_macros::impl_binop_assign_with_primitive!(impl BitAndAssign<$t> for UBig, bitand_assign);
1124        helper_macros::impl_binop_assign_with_primitive!(impl BitOrAssign<$t> for UBig, bitor_assign);
1125        helper_macros::impl_binop_assign_with_primitive!(impl BitXorAssign<$t> for UBig, bitxor_assign);
1126    )*};
1127}
1128impl_bit_ops_primitive_with_ubig!(u8 u16 u32 u64 u128 usize);
1129
1130macro_rules! impl_bit_ops_unsigned_with_ibig {
1131    ($($t:ty)*) => {$(
1132        helper_macros::impl_commutative_binop_with_primitive!(impl BitAnd<$t> for IBig, bitand -> $t);
1133        helper_macros::impl_commutative_binop_with_primitive!(impl BitOr<$t> for IBig, bitor);
1134        helper_macros::impl_commutative_binop_with_primitive!(impl BitXor<$t> for IBig, bitxor);
1135        helper_macros::impl_binop_assign_with_primitive!(impl BitAndAssign<$t> for IBig, bitand_assign);
1136        helper_macros::impl_binop_assign_with_primitive!(impl BitOrAssign<$t> for IBig, bitor_assign);
1137        helper_macros::impl_binop_assign_with_primitive!(impl BitXorAssign<$t> for IBig, bitxor_assign);
1138    )*};
1139}
1140impl_bit_ops_unsigned_with_ibig!(u8 u16 u32 u64 u128 usize);
1141
1142macro_rules! impl_bit_ops_signed_with_ibig {
1143    ($($t:ty)*) => {$(
1144        helper_macros::impl_commutative_binop_with_primitive!(impl BitAnd<$t> for IBig, bitand);
1145        helper_macros::impl_commutative_binop_with_primitive!(impl BitOr<$t> for IBig, bitor);
1146        helper_macros::impl_commutative_binop_with_primitive!(impl BitXor<$t> for IBig, bitxor);
1147        helper_macros::impl_binop_assign_with_primitive!(impl BitAndAssign<$t> for IBig, bitand_assign);
1148        helper_macros::impl_binop_assign_with_primitive!(impl BitOrAssign<$t> for IBig, bitor_assign);
1149        helper_macros::impl_binop_assign_with_primitive!(impl BitXorAssign<$t> for IBig, bitxor_assign);
1150    )*};
1151}
1152impl_bit_ops_signed_with_ibig!(i8 i16 i32 i64 i128 isize);
1153
1154#[cfg(test)]
1155mod tests {
1156    use super::*;
1157
1158    #[test]
1159    fn test_and_not() {
1160        let cases = [
1161            (UBig::from(0xf0f0u16), UBig::from(0xff00u16), UBig::from(0xf0u16)),
1162            (
1163                UBig::from(0xeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeu128),
1164                UBig::from(0xffu8),
1165                UBig::from(0xeeeeeeeeeeeeeeeeeeeeeeeeeeeeee00u128),
1166            ),
1167            (
1168                UBig::from(0xffu8),
1169                UBig::from(0xeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeu128),
1170                UBig::from(0x11u8),
1171            ),
1172            (
1173                UBig::from_str_radix("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee", 16).unwrap(),
1174                UBig::from_str_radix(
1175                    "dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd",
1176                    16,
1177                )
1178                .unwrap(),
1179                UBig::from_str_radix("22222222222222222222222222222222", 16).unwrap(),
1180            ),
1181            (
1182                UBig::from_str_radix(
1183                    "dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd",
1184                    16,
1185                )
1186                .unwrap(),
1187                UBig::from_str_radix("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee", 16).unwrap(),
1188                UBig::from_str_radix(
1189                    "dddddddddddddddddddddddddddddddd11111111111111111111111111111111",
1190                    16,
1191                )
1192                .unwrap(),
1193            ),
1194        ];
1195
1196        for (a, b, c) in cases.iter() {
1197            assert_eq!(UBig(a.repr().and_not(b.repr())), *c);
1198            assert_eq!(UBig(a.clone().into_repr().and_not(b.repr())), *c);
1199            assert_eq!(UBig(a.repr().and_not(b.clone().into_repr())), *c);
1200            let (a, b) = (a.clone(), b.clone());
1201            assert_eq!(UBig(a.into_repr().and_not(b.into_repr())), *c);
1202        }
1203    }
1204}
dashu_int/bits.rs

dashu_int/
bits.rs
