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

dashu_int/
bits.rs
