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        let n = n.min(WORD_BITS_USIZE) as u32;
501        dword & ones_dword(n) != 0
502    }
503
504    fn are_slice_low_bits_nonzero(words: &[Word], n: usize) -> bool {
505        let n_words = n / WORD_BITS_USIZE;
506        if n_words >= words.len() {
507            true
508        } else {
509            let n_top = (n % WORD_BITS_USIZE) as u32;
510            words[..n_words].iter().any(|x| *x != 0) || words[n_words] & ones_word(n_top) != 0
511        }
512    }
513
514    fn next_power_of_two_large(mut buffer: Buffer) -> Repr {
515        debug_assert!(*buffer.last().unwrap() != 0);
516
517        let n = buffer.len();
518        let mut iter = buffer[..n - 1].iter_mut().skip_while(|x| **x == 0);
519
520        let carry = match iter.next() {
521            None => 0,
522            Some(x) => {
523                *x = 0;
524                for x in iter {
525                    *x = 0;
526                }
527                1
528            }
529        };
530
531        let last = buffer.last_mut().unwrap();
532        match last
533            .checked_add(carry)
534            .and_then(|x| x.checked_next_power_of_two())
535        {
536            Some(p) => *last = p,
537            None => {
538                *last = 0;
539                buffer.push_resizing(1);
540            }
541        }
542
543        Repr::from_buffer(buffer)
544    }
545
546    fn with_bit_dword_spilled(dword: DoubleWord, n: usize) -> Repr {
547        debug_assert!(n >= DWORD_BITS_USIZE);
548        let idx = n / WORD_BITS_USIZE;
549        let mut buffer = Buffer::allocate(idx + 1);
550        let (lo, hi) = split_dword(dword);
551        buffer.push(lo);
552        buffer.push(hi);
553        buffer.push_zeros(idx - 2);
554        buffer.push(1 << (n % WORD_BITS_USIZE));
555        Repr::from_buffer(buffer)
556    }
557
558    fn with_bit_large(mut buffer: Buffer, n: usize) -> Repr {
559        let idx = n / WORD_BITS_USIZE;
560        if idx < buffer.len() {
561            buffer[idx] |= 1 << (n % WORD_BITS_USIZE);
562        } else {
563            buffer.ensure_capacity(idx + 1);
564            buffer.push_zeros(idx - buffer.len());
565            buffer.push(1 << (n % WORD_BITS_USIZE));
566        }
567        Repr::from_buffer(buffer)
568    }
569
570    /// Count the trailing zero bits in the words.
571    /// Panics if the input is zero.
572    #[inline]
573    const fn trailing_zeros_large(words: &[Word]) -> usize {
574        // Const equivalent to:
575        // let zero_words = words.iter().position(|&word| word != 0).unwrap();
576        let mut zero_words = 0;
577        while zero_words < words.len() {
578            if words[zero_words] != 0 {
579                break;
580            }
581            zero_words += 1;
582        }
583
584        let zero_bits = words[zero_words].trailing_zeros() as usize;
585        zero_words * WORD_BITS_USIZE + zero_bits
586    }
587
588    /// Count the trailing zero bits in the words shifted right by one.
589    /// Panics if the input is zero.
590    #[inline]
591    const fn trailing_zeros_large_shifted_by_one(words: &[Word]) -> usize {
592        debug_assert!(words.len() >= 2);
593        let zero_begin = (words[0] >> 1).trailing_zeros() as usize;
594        if zero_begin < (WORD_BITS_USIZE - 1) {
595            zero_begin
596        } else {
597            let mut zero_words = 1;
598            while zero_words < words.len() {
599                if words[zero_words] != 0 {
600                    break;
601                }
602                zero_words += 1;
603            }
604
605            let zero_bits = words[zero_words].trailing_zeros() as usize;
606            (zero_words - 1) * WORD_BITS_USIZE + zero_bits + zero_begin - 1
607        }
608    }
609
610    /// Count the trailing one bits in the words.
611    #[inline]
612    const fn trailing_ones_large(words: &[Word]) -> usize {
613        // Const equivalent to:
614        // let one_words = words.iter().position(|&word| word != Word::MAX).unwrap();
615        let mut one_words = 1;
616        while one_words < words.len() {
617            if words[one_words] != Word::MAX {
618                break;
619            }
620            one_words += 1;
621        }
622
623        let one_bits = words[one_words].trailing_ones() as usize;
624        one_words * WORD_BITS_USIZE + one_bits
625    }
626
627    #[inline]
628    fn clear_high_bits_large(mut buffer: Buffer, n: usize) -> Repr {
629        let n_words = ceil_div(n, WORD_BITS_USIZE);
630        if n_words > buffer.len() {
631            Repr::from_buffer(buffer)
632        } else {
633            buffer.truncate(n_words);
634            if n % WORD_BITS_USIZE != 0 {
635                let last = buffer.last_mut().unwrap();
636                *last &= ones_word((n % WORD_BITS_USIZE) as u32);
637            }
638            Repr::from_buffer(buffer)
639        }
640    }
641
642    impl BitAnd<TypedRepr> for TypedRepr {
643        type Output = Repr;
644
645        #[inline]
646        fn bitand(self, rhs: TypedRepr) -> Repr {
647            match (self, rhs) {
648                (Small(dword0), Small(dword1)) => Repr::from_dword(dword0 & dword1),
649                (Small(dword0), Large(buffer1)) => {
650                    Repr::from_dword(dword0 & buffer1.lowest_dword())
651                }
652                (Large(buffer0), Small(dword1)) => {
653                    Repr::from_dword(buffer0.lowest_dword() & dword1)
654                }
655                (Large(buffer0), Large(buffer1)) => {
656                    if buffer0.len() <= buffer1.len() {
657                        bitand_large(buffer0, &buffer1)
658                    } else {
659                        bitand_large(buffer1, &buffer0)
660                    }
661                }
662            }
663        }
664    }
665
666    impl<'r> BitAnd<TypedReprRef<'r>> for TypedRepr {
667        type Output = Repr;
668
669        #[inline]
670        fn bitand(self, rhs: TypedReprRef) -> Repr {
671            match (self, rhs) {
672                (Small(dword0), RefSmall(dword1)) => Repr::from_dword(dword0 & dword1),
673                (Small(dword0), RefLarge(buffer1)) => {
674                    Repr::from_dword(dword0 & lowest_dword(buffer1))
675                }
676                (Large(buffer0), RefSmall(dword1)) => {
677                    Repr::from_dword(buffer0.lowest_dword() & dword1)
678                }
679                (Large(buffer0), RefLarge(buffer1)) => bitand_large(buffer0, buffer1),
680            }
681        }
682    }
683
684    impl<'l> BitAnd<TypedRepr> for TypedReprRef<'l> {
685        type Output = Repr;
686
687        #[inline]
688        fn bitand(self, rhs: TypedRepr) -> Repr {
689            // bitand is commutative
690            rhs.bitand(self)
691        }
692    }
693
694    impl<'l, 'r> BitAnd<TypedReprRef<'r>> for TypedReprRef<'l> {
695        type Output = Repr;
696
697        #[inline]
698        fn bitand(self, rhs: TypedReprRef) -> Repr {
699            match (self, rhs) {
700                (RefSmall(dword0), RefSmall(dword1)) => Repr::from_dword(dword0 & dword1),
701                (RefSmall(dword0), RefLarge(buffer1)) => {
702                    Repr::from_dword(dword0 & lowest_dword(buffer1))
703                }
704                (RefLarge(buffer0), RefSmall(dword1)) => {
705                    Repr::from_dword(lowest_dword(buffer0) & dword1)
706                }
707                (RefLarge(buffer0), RefLarge(buffer1)) => {
708                    if buffer0.len() <= buffer1.len() {
709                        bitand_large(buffer0.into(), buffer1)
710                    } else {
711                        bitand_large(buffer1.into(), buffer0)
712                    }
713                }
714            }
715        }
716    }
717
718    fn bitand_large(mut buffer: Buffer, rhs: &[Word]) -> Repr {
719        if buffer.len() > rhs.len() {
720            buffer.truncate(rhs.len());
721        }
722        for (x, y) in buffer.iter_mut().zip(rhs.iter()) {
723            *x &= *y;
724        }
725        Repr::from_buffer(buffer)
726    }
727
728    impl BitOr<TypedRepr> for TypedRepr {
729        type Output = Repr;
730
731        #[inline]
732        fn bitor(self, rhs: TypedRepr) -> Repr {
733            match (self, rhs) {
734                (Small(dword0), Small(dword1)) => Repr::from_dword(dword0 | dword1),
735                (Small(dword0), Large(buffer1)) => bitor_large_dword(buffer1, dword0),
736                (Large(buffer0), Small(dword1)) => bitor_large_dword(buffer0, dword1),
737                (Large(buffer0), Large(buffer1)) => {
738                    if buffer0.len() >= buffer1.len() {
739                        bitor_large(buffer0, &buffer1)
740                    } else {
741                        bitor_large(buffer1, &buffer0)
742                    }
743                }
744            }
745        }
746    }
747
748    impl<'r> BitOr<TypedReprRef<'r>> for TypedRepr {
749        type Output = Repr;
750
751        #[inline]
752        fn bitor(self, rhs: TypedReprRef) -> Repr {
753            match (self, rhs) {
754                (Small(dword0), RefSmall(dword1)) => Repr::from_dword(dword0 | dword1),
755                (Small(dword0), RefLarge(buffer1)) => bitor_large_dword(buffer1.into(), dword0),
756                (Large(buffer0), RefSmall(dword1)) => bitor_large_dword(buffer0, dword1),
757                (Large(buffer0), RefLarge(buffer1)) => bitor_large(buffer0, buffer1),
758            }
759        }
760    }
761
762    impl<'l> BitOr<TypedRepr> for TypedReprRef<'l> {
763        type Output = Repr;
764
765        #[inline]
766        fn bitor(self, rhs: TypedRepr) -> Repr {
767            // bitor is commutative
768            rhs.bitor(self)
769        }
770    }
771
772    impl<'l, 'r> BitOr<TypedReprRef<'r>> for TypedReprRef<'l> {
773        type Output = Repr;
774
775        #[inline]
776        fn bitor(self, rhs: TypedReprRef) -> Repr {
777            match (self, rhs) {
778                (RefSmall(dword0), RefSmall(dword1)) => Repr::from_dword(dword0 | dword1),
779                (RefSmall(dword0), RefLarge(buffer1)) => bitor_large_dword(buffer1.into(), dword0),
780                (RefLarge(buffer0), RefSmall(dword1)) => bitor_large_dword(buffer0.into(), dword1),
781                (RefLarge(buffer0), RefLarge(buffer1)) => {
782                    if buffer0.len() >= buffer1.len() {
783                        bitor_large(buffer0.into(), buffer1)
784                    } else {
785                        bitor_large(buffer1.into(), buffer0)
786                    }
787                }
788            }
789        }
790    }
791
792    fn bitor_large_dword(mut buffer: Buffer, rhs: DoubleWord) -> Repr {
793        debug_assert!(buffer.len() >= 2);
794
795        let (lo, hi) = split_dword(rhs);
796        let (b_lo, b_hi) = buffer.lowest_dword_mut();
797        *b_lo |= lo;
798        *b_hi |= hi;
799        Repr::from_buffer(buffer)
800    }
801
802    fn bitor_large(mut buffer: Buffer, rhs: &[Word]) -> Repr {
803        for (x, y) in buffer.iter_mut().zip(rhs.iter()) {
804            *x |= *y;
805        }
806        if rhs.len() > buffer.len() {
807            buffer.ensure_capacity(rhs.len());
808            buffer.push_slice(&rhs[buffer.len()..]);
809        }
810        Repr::from_buffer(buffer)
811    }
812
813    impl BitXor<TypedRepr> for TypedRepr {
814        type Output = Repr;
815
816        #[inline]
817        fn bitxor(self, rhs: TypedRepr) -> Repr {
818            match (self, rhs) {
819                (Small(dword0), Small(dword1)) => Repr::from_dword(dword0 ^ dword1),
820                (Small(dword0), Large(buffer1)) => bitxor_large_dword(buffer1, dword0),
821                (Large(buffer0), Small(dword1)) => bitxor_large_dword(buffer0, dword1),
822                (Large(buffer0), Large(buffer1)) => {
823                    if buffer0.len() >= buffer1.len() {
824                        bitxor_large(buffer0, &buffer1)
825                    } else {
826                        bitxor_large(buffer1, &buffer0)
827                    }
828                }
829            }
830        }
831    }
832
833    impl<'r> BitXor<TypedReprRef<'r>> for TypedRepr {
834        type Output = Repr;
835
836        #[inline]
837        fn bitxor(self, rhs: TypedReprRef) -> Repr {
838            match (self, rhs) {
839                (Small(dword0), RefSmall(dword1)) => Repr::from_dword(dword0 ^ dword1),
840                (Small(dword0), RefLarge(buffer1)) => bitxor_large_dword(buffer1.into(), dword0),
841                (Large(buffer0), RefSmall(dword1)) => bitxor_large_dword(buffer0, dword1),
842                (Large(buffer0), RefLarge(buffer1)) => bitxor_large(buffer0, buffer1),
843            }
844        }
845    }
846
847    impl<'l> BitXor<TypedRepr> for TypedReprRef<'l> {
848        type Output = Repr;
849
850        #[inline]
851        fn bitxor(self, rhs: TypedRepr) -> Repr {
852            // bitxor is commutative
853            rhs.bitxor(self)
854        }
855    }
856
857    impl<'l, 'r> BitXor<TypedReprRef<'r>> for TypedReprRef<'l> {
858        type Output = Repr;
859
860        #[inline]
861        fn bitxor(self, rhs: TypedReprRef) -> Repr {
862            match (self, rhs) {
863                (RefSmall(dword0), RefSmall(dword1)) => Repr::from_dword(dword0 ^ dword1),
864                (RefSmall(dword0), RefLarge(buffer1)) => bitxor_large_dword(buffer1.into(), dword0),
865                (RefLarge(buffer0), RefSmall(dword1)) => bitxor_large_dword(buffer0.into(), dword1),
866                (RefLarge(buffer0), RefLarge(buffer1)) => {
867                    if buffer0.len() >= buffer1.len() {
868                        bitxor_large(buffer0.into(), buffer1)
869                    } else {
870                        bitxor_large(buffer1.into(), buffer0)
871                    }
872                }
873            }
874        }
875    }
876
877    fn bitxor_large_dword(mut buffer: Buffer, rhs: DoubleWord) -> Repr {
878        debug_assert!(buffer.len() >= 2);
879
880        let (lo, hi) = split_dword(rhs);
881        let (b_lo, b_hi) = buffer.lowest_dword_mut();
882        *b_lo ^= lo;
883        *b_hi ^= hi;
884        Repr::from_buffer(buffer)
885    }
886
887    fn bitxor_large(mut buffer: Buffer, rhs: &[Word]) -> Repr {
888        for (x, y) in buffer.iter_mut().zip(rhs.iter()) {
889            *x ^= *y;
890        }
891        if rhs.len() > buffer.len() {
892            buffer.ensure_capacity(rhs.len());
893            buffer.push_slice(&rhs[buffer.len()..]);
894        }
895        Repr::from_buffer(buffer)
896    }
897
898    impl AndNot<TypedRepr> for TypedRepr {
899        type Output = Repr;
900
901        #[inline]
902        fn and_not(self, rhs: TypedRepr) -> Repr {
903            match (self, rhs) {
904                (Small(dword0), Small(dword1)) => Repr::from_dword(dword0 & !dword1),
905                (Small(dword0), Large(buffer1)) => {
906                    Repr::from_dword(dword0 & !buffer1.lowest_dword())
907                }
908                (Large(buffer0), Small(dword1)) => and_not_large_dword(buffer0, dword1),
909                (Large(buffer0), Large(buffer1)) => and_not_large(buffer0, &buffer1),
910            }
911        }
912    }
913
914    impl<'r> AndNot<TypedReprRef<'r>> for TypedRepr {
915        type Output = Repr;
916
917        #[inline]
918        fn and_not(self, rhs: TypedReprRef) -> Repr {
919            match (self, rhs) {
920                (Small(dword0), RefSmall(dword1)) => Repr::from_dword(dword0 & !dword1),
921                (Small(dword0), RefLarge(buffer1)) => {
922                    Repr::from_dword(dword0 & !lowest_dword(buffer1))
923                }
924                (Large(buffer0), RefSmall(dword1)) => and_not_large_dword(buffer0, dword1),
925                (Large(buffer0), RefLarge(buffer1)) => and_not_large(buffer0, buffer1),
926            }
927        }
928    }
929
930    impl<'l> AndNot<TypedRepr> for TypedReprRef<'l> {
931        type Output = Repr;
932
933        #[inline]
934        fn and_not(self, rhs: TypedRepr) -> Repr {
935            match (self, rhs) {
936                (RefSmall(dword0), Small(dword1)) => Repr::from_dword(dword0 & !dword1),
937                (RefSmall(dword0), Large(buffer1)) => {
938                    Repr::from_dword(dword0 & !buffer1.lowest_dword())
939                }
940                (RefLarge(buffer0), Small(dword1)) => and_not_large_dword(buffer0.into(), dword1),
941                (RefLarge(buffer0), Large(buffer1)) => and_not_large(buffer0.into(), &buffer1),
942            }
943        }
944    }
945
946    impl<'l, 'r> AndNot<TypedReprRef<'r>> for TypedReprRef<'l> {
947        type Output = Repr;
948
949        #[inline]
950        fn and_not(self, rhs: TypedReprRef) -> Repr {
951            match (self, rhs) {
952                (RefSmall(dword0), RefSmall(dword1)) => Repr::from_dword(dword0 & !dword1),
953                (RefSmall(dword0), RefLarge(buffer1)) => {
954                    Repr::from_dword(dword0 & !lowest_dword(buffer1))
955                }
956                (RefLarge(buffer0), RefSmall(dword1)) => {
957                    and_not_large_dword(buffer0.into(), dword1)
958                }
959                (RefLarge(buffer0), RefLarge(buffer1)) => and_not_large(buffer0.into(), buffer1),
960            }
961        }
962    }
963
964    fn and_not_large_dword(mut buffer: Buffer, rhs: DoubleWord) -> Repr {
965        debug_assert!(buffer.len() >= 2);
966
967        let (lo, hi) = split_dword(rhs);
968        let (b_lo, b_hi) = buffer.lowest_dword_mut();
969        *b_lo &= !lo;
970        *b_hi &= !hi;
971        Repr::from_buffer(buffer)
972    }
973
974    fn and_not_large(mut buffer: Buffer, rhs: &[Word]) -> Repr {
975        for (x, y) in buffer.iter_mut().zip(rhs.iter()) {
976            *x &= !*y;
977        }
978        Repr::from_buffer(buffer)
979    }
980}
981
982impl Not for IBig {
983    type Output = IBig;
984
985    #[inline]
986    fn not(self) -> IBig {
987        let (sign, mag) = self.into_sign_repr();
988        match sign {
989            Positive => IBig(mag.add_one().with_sign(Negative)),
990            Negative => IBig(mag.sub_one().with_sign(Positive)),
991        }
992    }
993}
994
995impl Not for &IBig {
996    type Output = IBig;
997
998    #[inline]
999    fn not(self) -> IBig {
1000        let (sign, mag) = self.as_sign_repr();
1001        match sign {
1002            Positive => IBig(mag.add_one().with_sign(Negative)),
1003            Negative => IBig(mag.sub_one().with_sign(Positive)),
1004        }
1005    }
1006}
1007
1008macro_rules! impl_ibig_bitand {
1009    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {
1010        match ($sign0, $sign1) {
1011            (Positive, Positive) => IBig($mag0.bitand($mag1)),
1012            (Positive, Negative) => IBig($mag0.and_not($mag1.sub_one().into_typed())),
1013            (Negative, Positive) => IBig($mag1.and_not($mag0.sub_one().into_typed())),
1014            (Negative, Negative) => !IBig(
1015                $mag0
1016                    .sub_one()
1017                    .into_typed()
1018                    .bitor($mag1.sub_one().into_typed()),
1019            ),
1020        }
1021    };
1022}
1023macro_rules! impl_ibig_bitor {
1024    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {
1025        match ($sign0, $sign1) {
1026            (Positive, Positive) => IBig($mag0.bitor($mag1)),
1027            (Positive, Negative) => !IBig($mag1.sub_one().into_typed().and_not($mag0)),
1028            (Negative, Positive) => !IBig($mag0.sub_one().into_typed().and_not($mag1)),
1029            (Negative, Negative) => !IBig(
1030                $mag0
1031                    .sub_one()
1032                    .into_typed()
1033                    .bitand($mag1.sub_one().into_typed()),
1034            ),
1035        }
1036    };
1037}
1038macro_rules! impl_ibig_bitxor {
1039    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {
1040        match ($sign0, $sign1) {
1041            (Positive, Positive) => IBig($mag0.bitxor($mag1)),
1042            (Positive, Negative) => !IBig($mag0.bitxor($mag1.sub_one().into_typed())),
1043            (Negative, Positive) => !IBig($mag0.sub_one().into_typed().bitxor($mag1)),
1044            (Negative, Negative) => IBig(
1045                $mag0
1046                    .sub_one()
1047                    .into_typed()
1048                    .bitxor($mag1.sub_one().into_typed()),
1049            ),
1050        }
1051    };
1052}
1053helper_macros::forward_ibig_binop_to_repr!(impl BitAnd, bitand, Output = IBig, impl_ibig_bitand);
1054helper_macros::forward_ibig_binop_to_repr!(impl BitOr, bitor, Output = IBig, impl_ibig_bitor);
1055helper_macros::forward_ibig_binop_to_repr!(impl BitXor, bitxor, Output = IBig, impl_ibig_bitxor);
1056helper_macros::impl_binop_assign_by_taking!(impl BitAndAssign<IBig> for IBig, bitand_assign, bitand);
1057helper_macros::impl_binop_assign_by_taking!(impl BitOrAssign<IBig> for IBig, bitor_assign, bitor);
1058helper_macros::impl_binop_assign_by_taking!(impl BitXorAssign<IBig> for IBig, bitxor_assign, bitxor);
1059
1060// Ops between UBig & IBig
1061
1062macro_rules! impl_ubig_ibig_bitand {
1063    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {{
1064        debug_assert_eq!($sign0, Positive);
1065        match $sign1 {
1066            Positive => UBig($mag0.bitand($mag1)),
1067            Negative => UBig($mag0.and_not($mag1.sub_one().into_typed())),
1068        }
1069    }};
1070}
1071macro_rules! impl_ibig_ubig_bitand {
1072    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {{
1073        debug_assert_eq!($sign1, Positive);
1074        match $sign0 {
1075            Positive => UBig($mag1.bitand($mag0)),
1076            Negative => UBig($mag1.and_not($mag0.sub_one().into_typed())),
1077        }
1078    }};
1079}
1080helper_macros::forward_ubig_ibig_binop_to_repr!(
1081    impl BitAnd,
1082    bitand,
1083    Output = UBig,
1084    impl_ubig_ibig_bitand
1085);
1086helper_macros::forward_ubig_ibig_binop_to_repr!(impl BitOr, bitor, Output = IBig, impl_ibig_bitor);
1087helper_macros::forward_ubig_ibig_binop_to_repr!(
1088    impl BitXor,
1089    bitxor,
1090    Output = IBig,
1091    impl_ibig_bitxor
1092);
1093helper_macros::impl_binop_assign_by_taking!(impl BitAndAssign<IBig> for UBig, bitand_assign, bitand);
1094helper_macros::forward_ibig_ubig_binop_to_repr!(
1095    impl BitAnd,
1096    bitand,
1097    Output = UBig,
1098    impl_ibig_ubig_bitand
1099);
1100helper_macros::forward_ibig_ubig_binop_to_repr!(impl BitOr, bitor, Output = IBig, impl_ibig_bitor);
1101helper_macros::forward_ibig_ubig_binop_to_repr!(
1102    impl BitXor,
1103    bitxor,
1104    Output = IBig,
1105    impl_ibig_bitxor
1106);
1107helper_macros::impl_binop_assign_by_taking!(impl BitAndAssign<UBig> for IBig, bitand_assign, bitand);
1108helper_macros::impl_binop_assign_by_taking!(impl BitOrAssign<UBig> for IBig, bitor_assign, bitor);
1109helper_macros::impl_binop_assign_by_taking!(impl BitXorAssign<UBig> for IBig, bitxor_assign, bitxor);
1110
1111// Ops with primitives
1112
1113macro_rules! impl_bit_ops_primitive_with_ubig {
1114    ($($t:ty)*) => {$(
1115        helper_macros::impl_commutative_binop_with_primitive!(impl BitAnd<$t> for UBig, bitand -> $t);
1116        helper_macros::impl_commutative_binop_with_primitive!(impl BitOr<$t> for UBig, bitor);
1117        helper_macros::impl_commutative_binop_with_primitive!(impl BitXor<$t> for UBig, bitxor);
1118        helper_macros::impl_binop_assign_with_primitive!(impl BitAndAssign<$t> for UBig, bitand_assign);
1119        helper_macros::impl_binop_assign_with_primitive!(impl BitOrAssign<$t> for UBig, bitor_assign);
1120        helper_macros::impl_binop_assign_with_primitive!(impl BitXorAssign<$t> for UBig, bitxor_assign);
1121    )*};
1122}
1123impl_bit_ops_primitive_with_ubig!(u8 u16 u32 u64 u128 usize);
1124
1125macro_rules! impl_bit_ops_unsigned_with_ibig {
1126    ($($t:ty)*) => {$(
1127        helper_macros::impl_commutative_binop_with_primitive!(impl BitAnd<$t> for IBig, bitand -> $t);
1128        helper_macros::impl_commutative_binop_with_primitive!(impl BitOr<$t> for IBig, bitor);
1129        helper_macros::impl_commutative_binop_with_primitive!(impl BitXor<$t> for IBig, bitxor);
1130        helper_macros::impl_binop_assign_with_primitive!(impl BitAndAssign<$t> for IBig, bitand_assign);
1131        helper_macros::impl_binop_assign_with_primitive!(impl BitOrAssign<$t> for IBig, bitor_assign);
1132        helper_macros::impl_binop_assign_with_primitive!(impl BitXorAssign<$t> for IBig, bitxor_assign);
1133    )*};
1134}
1135impl_bit_ops_unsigned_with_ibig!(u8 u16 u32 u64 u128 usize);
1136
1137macro_rules! impl_bit_ops_signed_with_ibig {
1138    ($($t:ty)*) => {$(
1139        helper_macros::impl_commutative_binop_with_primitive!(impl BitAnd<$t> for IBig, bitand);
1140        helper_macros::impl_commutative_binop_with_primitive!(impl BitOr<$t> for IBig, bitor);
1141        helper_macros::impl_commutative_binop_with_primitive!(impl BitXor<$t> for IBig, bitxor);
1142        helper_macros::impl_binop_assign_with_primitive!(impl BitAndAssign<$t> for IBig, bitand_assign);
1143        helper_macros::impl_binop_assign_with_primitive!(impl BitOrAssign<$t> for IBig, bitor_assign);
1144        helper_macros::impl_binop_assign_with_primitive!(impl BitXorAssign<$t> for IBig, bitxor_assign);
1145    )*};
1146}
1147impl_bit_ops_signed_with_ibig!(i8 i16 i32 i64 i128 isize);
1148
1149#[cfg(test)]
1150mod tests {
1151    use super::*;
1152
1153    #[test]
1154    fn test_and_not() {
1155        let cases = [
1156            (UBig::from(0xf0f0u16), UBig::from(0xff00u16), UBig::from(0xf0u16)),
1157            (
1158                UBig::from(0xeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeu128),
1159                UBig::from(0xffu8),
1160                UBig::from(0xeeeeeeeeeeeeeeeeeeeeeeeeeeeeee00u128),
1161            ),
1162            (
1163                UBig::from(0xffu8),
1164                UBig::from(0xeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeu128),
1165                UBig::from(0x11u8),
1166            ),
1167            (
1168                UBig::from_str_radix("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee", 16).unwrap(),
1169                UBig::from_str_radix(
1170                    "dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd",
1171                    16,
1172                )
1173                .unwrap(),
1174                UBig::from_str_radix("22222222222222222222222222222222", 16).unwrap(),
1175            ),
1176            (
1177                UBig::from_str_radix(
1178                    "dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd",
1179                    16,
1180                )
1181                .unwrap(),
1182                UBig::from_str_radix("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee", 16).unwrap(),
1183                UBig::from_str_radix(
1184                    "dddddddddddddddddddddddddddddddd11111111111111111111111111111111",
1185                    16,
1186                )
1187                .unwrap(),
1188            ),
1189        ];
1190
1191        for (a, b, c) in cases.iter() {
1192            assert_eq!(UBig(a.repr().and_not(b.repr())), *c);
1193            assert_eq!(UBig(a.clone().into_repr().and_not(b.repr())), *c);
1194            assert_eq!(UBig(a.repr().and_not(b.clone().into_repr())), *c);
1195            let (a, b) = (a.clone(), b.clone());
1196            assert_eq!(UBig(a.into_repr().and_not(b.into_repr())), *c);
1197        }
1198    }
1199}
dashu_int/bits.rs

dashu_int/
bits.rs
