monster/solver/
bitvec.rs

1use std::{
2    fmt,
3    ops::{Add, BitAnd, BitOr, BitXor, Div, Mul, Neg, Not, Rem, Shl, Shr, Sub},
4};
5
6#[derive(Clone, Copy, Eq, Hash, PartialEq, PartialOrd)]
7pub struct BitVector(pub u64);
8
9impl BitVector {
10    pub fn ones() -> BitVector {
11        BitVector(u64::max_value())
12    }
13
14    pub fn ctz(&self) -> u32 {
15        self.0.trailing_zeros()
16    }
17
18    pub fn odd(&self) -> bool {
19        self.0 % 2 == 1
20    }
21
22    pub fn lsb(&self) -> u64 {
23        self.0 & 1
24    }
25
26    pub fn modinverse(&self) -> Option<BitVector> {
27        modinverse::modinverse((self.0 as u128) as i128, 2_i128.pow(64))
28            .map(|res| BitVector(res as u64))
29    }
30
31    pub fn addo(&self, t: BitVector) -> bool {
32        self.0.overflowing_add(t.0).1
33    }
34
35    pub fn mulo(&self, t: BitVector) -> bool {
36        self.0.overflowing_mul(t.0).1
37    }
38}
39
40impl Neg for BitVector {
41    type Output = BitVector;
42
43    fn neg(self) -> Self::Output {
44        Self(-(self.0 as i64) as u64)
45    }
46}
47
48impl Add<BitVector> for BitVector {
49    type Output = BitVector;
50
51    fn add(self, other: BitVector) -> Self::Output {
52        Self(self.0.wrapping_add(other.0))
53    }
54}
55
56impl Sub<BitVector> for BitVector {
57    type Output = BitVector;
58
59    fn sub(self, other: BitVector) -> Self::Output {
60        Self(self.0.wrapping_sub(other.0))
61    }
62}
63
64impl Mul<BitVector> for BitVector {
65    type Output = BitVector;
66
67    fn mul(self, other: BitVector) -> Self::Output {
68        Self(self.0.wrapping_mul(other.0))
69    }
70}
71
72impl Div<BitVector> for BitVector {
73    type Output = BitVector;
74
75    fn div(self, other: BitVector) -> Self::Output {
76        if other == BitVector(0) {
77            Self::ones()
78        } else {
79            Self(self.0.wrapping_div(other.0))
80        }
81    }
82}
83
84impl Rem<BitVector> for BitVector {
85    type Output = BitVector;
86
87    fn rem(self, other: BitVector) -> Self::Output {
88        if other == BitVector(0) {
89            self
90        } else {
91            Self(self.0.wrapping_rem(other.0))
92        }
93    }
94}
95
96impl BitOr<BitVector> for BitVector {
97    type Output = BitVector;
98
99    fn bitor(self, other: BitVector) -> Self::Output {
100        Self(self.0 | other.0)
101    }
102}
103
104impl BitAnd<BitVector> for BitVector {
105    type Output = BitVector;
106
107    fn bitand(self, other: BitVector) -> Self::Output {
108        Self(self.0 & other.0)
109    }
110}
111
112impl BitXor<BitVector> for BitVector {
113    type Output = BitVector;
114
115    fn bitxor(self, other: BitVector) -> Self::Output {
116        Self(self.0 ^ other.0)
117    }
118}
119
120impl Shl<u32> for BitVector {
121    type Output = BitVector;
122
123    fn shl(self, other: u32) -> Self::Output {
124        Self(self.0.wrapping_shl(other))
125    }
126}
127
128impl Shr<u32> for BitVector {
129    type Output = BitVector;
130
131    fn shr(self, other: u32) -> Self::Output {
132        Self(self.0.wrapping_shr(other))
133    }
134}
135
136impl Not for BitVector {
137    type Output = BitVector;
138
139    fn not(self) -> Self::Output {
140        BitVector(!self.0)
141    }
142}
143
144impl fmt::Debug for BitVector {
145    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
146        fn bit_to_char(x: &BitVector, b: u32) -> char {
147            if *x & (BitVector(1) << b) > BitVector(0) {
148                '1'
149            } else {
150                '0'
151            }
152        }
153
154        let bit_vector = (0..64)
155            .rev()
156            .map(|b| bit_to_char(self, b))
157            .skip_while(|c| *c == '0')
158            .collect::<String>();
159
160        write!(f, "<{}>", bit_vector)
161    }
162}
monster/solver/bitvec.rs

monster/solver/
bitvec.rs
