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

dashu_int/
bits.rs
