rust_dense_bitset/u64impl.rs
1use crate::bitset::BitSet;
2
3use std::fmt;
4use std::hash::{Hash, Hasher};
5
6/// Overload of &, &=, |, |=, ^, ^=, !, <<, <<=, >>, >>=
7use std::ops::{
8 BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not, Shl, ShlAssign, Shr,
9 ShrAssign,
10};
11
12/// Provides an efficient and compact `BitSet` implementation for up to 64 bits.
13///
14/// This structure implements `BitSet, Clone, Copy, Default, Debug, Hash, PartialEq, Eq` and bit operations.
15#[derive(Copy, Clone, Default)]
16pub struct DenseBitSet {
17 state: u64,
18}
19
20impl DenseBitSet {
21 /// Returns a new empty `DenseBitSet`.
22 ///
23 /// # Example
24 /// ```
25 /// use rust_dense_bitset::DenseBitSet;
26 ///
27 /// let mut bs = DenseBitSet::new();
28 /// ```
29 pub fn new() -> Self {
30 Self { state: 0 }
31 }
32
33 /// Generates a bitset from an integer (little endian convention).
34 ///
35 /// # Example
36 /// ```
37 /// use rust_dense_bitset::DenseBitSet;
38 ///
39 /// let bs = DenseBitSet::from_integer(1234567890);
40 /// ```
41 pub fn from_integer(i: u64) -> Self {
42 Self { state: i }
43 }
44
45 /// Generates a bitset from a string and a base (little endian convention).
46 ///
47 /// The `base` must be an integer between 2 and 32.
48 ///
49 /// # Example
50 /// ```
51 /// use rust_dense_bitset::DenseBitSet;
52 ///
53 /// let mut bs1 = DenseBitSet::from_string("101010", 2);
54 /// let mut bs2 = DenseBitSet::from_string("2a", 16);
55 ///
56 /// assert_eq!(bs1,bs2);
57 /// ```
58 ///
59 /// # Panics
60 ///
61 /// This function will panic if an incorrect `base` is provided or if invalid
62 /// characters are found when parsing.
63 pub fn from_string(s: &str, base: u32) -> Self {
64 assert!(2 <= base && base <= 32, "Only supports base from 2 to 32");
65 let val = u64::from_str_radix(s, base);
66 let res: u64 = val.expect("Failed to parse string");
67 Self { state: res }
68 }
69
70 /// Returns an integer representing the bitset (little endian convention).
71 ///
72 /// # Example
73 /// ```
74 /// use rust_dense_bitset::DenseBitSet;
75 ///
76 /// let bs = DenseBitSet::from_integer(1234);
77 ///
78 /// assert_eq!(bs.to_integer(), 1234);
79 /// ```
80 pub fn to_integer(self) -> u64 {
81 self.state
82 }
83
84 /// Returns an integer representation of the bitset starting at the given `position` with given `length` (little endian convention).
85 ///
86 /// # Example
87 /// ```
88 /// use rust_dense_bitset::DenseBitSet;
89 ///
90 /// let bs = DenseBitSet::from_integer(0b11110101010010);
91 /// let value = bs.extract(5,6);
92 ///
93 /// assert_eq!(value, 42);
94 /// ```
95 ///
96 /// # Panics
97 /// This function will panic if `length` is zero or if one tries to
98 /// access a bit beyond the 64 bit limit (i.e., `position + length > 64`).
99 pub fn extract(self, position: usize, length: usize) -> u64 {
100 assert!(
101 position + length <= 64,
102 "This implementation is currently limited to 64 bit bitsets."
103 );
104 assert!(length > 0, "Cannot extract a zero-width slice.");
105 if length < 64 {
106 (self.state >> position) & ((1 << length) - 1)
107 } else {
108 // This special branch is to avoid overflowing when masking
109 (self.state >> position)
110 }
111 }
112
113 /// Returns nothing, mutates the `DenseBitSet` to insert `value` at the given `position`.
114 ///
115 /// Note that `value` is treated as a `length`-bit integer (little endian convention);
116 /// if necessary, `value` is padded with zeros (or truncated) to be of the correct length.
117 ///
118 /// # Example
119 /// ```
120 /// use rust_dense_bitset::DenseBitSet;
121 ///
122 /// let mut bs = DenseBitSet::new();
123 /// bs.insert(10, 8, 0b10101011);
124 /// bs.insert(3,1,1);
125 ///
126 /// assert_eq!(bs.to_integer(), 0b101010110000001000)
127 /// ```
128 ///
129 /// # Panics
130 /// This function will panic if `length` is zero, or if one tries to
131 /// insert a bit beyond the 64 bit limit (i.e. `position + length > 64`)
132 pub fn insert(&mut self, position: usize, length: usize, value: u64) {
133 assert!(
134 position + length <= 64,
135 "This implementation is currently limited to 64 bit bitsets."
136 );
137 assert!(length > 0, "Cannot insert zero-width slice");
138 if length < 64 {
139 let mut u = u64::max_value();
140 u ^= ((1 << length) - 1) << position;
141 self.state &= u;
142 self.state |= value << position;
143 } else {
144 self.state = value;
145 }
146 }
147
148 /// Returns `true` if and only if all bits are set to `true`.
149 ///
150 /// # Example
151 /// ```
152 /// use rust_dense_bitset::DenseBitSet;
153 /// use rust_dense_bitset::BitSet;
154 ///
155 /// let mut bs = DenseBitSet::from_integer(u64::max_value());
156 ///
157 /// assert!(bs.all());
158 ///
159 /// bs.set_bit(28,false);
160 /// bs.all(); // -> false
161 /// ```
162 pub fn all(self) -> bool {
163 self.state == u64::max_value()
164 }
165
166 /// Returns `true` if at least one of the bits is set to `true`.
167 ///
168 /// # Example
169 /// ```
170 /// use rust_dense_bitset::DenseBitSet;
171 /// use rust_dense_bitset::BitSet;
172 ///
173 /// let mut bs = DenseBitSet::from_integer(2048);
174 ///
175 /// assert!(bs.any());
176 ///
177 /// bs.set_bit(11,false);
178 /// bs.any(); // -> false
179 /// ```
180 pub fn any(self) -> bool {
181 self.state > 0
182 }
183
184 /// Returns `true` if all the bits are set to `false`.
185 ///
186 /// # Example
187 /// ```
188 /// use rust_dense_bitset::DenseBitSet;
189 /// use rust_dense_bitset::BitSet;
190 ///
191 /// let mut bs = DenseBitSet::from_integer(2048);
192 /// bs.set_bit(11,false);
193 ///
194 /// assert!(bs.none());
195 /// ```
196 pub fn none(self) -> bool {
197 !self.any()
198 }
199
200 /// Returns a bit-reversed `DenseBitSet`.
201 ///
202 /// This method is using a constant time bit reversal algorithm for 64 bits integers.
203 ///
204 /// # Example
205 /// ```
206 /// use rust_dense_bitset::DenseBitSet;
207 ///
208 /// let bs = DenseBitSet::from_integer(0b11110001);
209 /// let bs2 = bs.reverse();
210 ///
211 /// assert_eq!(bs2.to_integer(), 0b1000111100000000000000000000000000000000000000000000000000000000);
212 /// ```
213 pub fn reverse(self) -> Self {
214 let mut v = self.state;
215 v = ((v >> 1) & (0x5555555555555555 as u64)) | ((v & (0x5555555555555555 as u64)) << 1);
216 v = ((v >> 2) & (0x3333333333333333 as u64)) | ((v & (0x3333333333333333 as u64)) << 2);
217 v = ((v >> 4) & (0x0F0F0F0F0F0F0F0F as u64)) | ((v & (0x0F0F0F0F0F0F0F0F as u64)) << 4);
218
219 Self {
220 state: v.swap_bytes(),
221 }
222 }
223
224 /// Right rotation of `shift` bits.
225 ///
226 /// Shifts the bits to the right, wrapping the truncated bits to the end of the bitset.
227 ///
228 /// The rotation is done in-place, so the bitset needs to be mutable.
229 /// # Example
230 /// ```
231 /// use rust_dense_bitset::DenseBitSet;
232 ///
233 /// let mut bs = DenseBitSet::from_integer(0b111000111000111000111);
234 /// bs.rotr(10);
235 ///
236 /// assert_eq!(bs.to_integer(), 0b111000111000000000000000000000000000000000000000000011100011100 );
237 /// ```
238 pub fn rotr(&mut self, shift: u32) {
239 self.state = self.state.rotate_right(shift);
240 }
241
242 /// Left rotation of `shift` bits.
243 ///
244 /// Shifts the bits to the left, wrapping the truncated bits to the beginning of the bitset.
245 ///
246 /// The rotation is done in place, so the bitset needs to be mutable.
247 /// # Example
248 /// ```
249 /// use rust_dense_bitset::DenseBitSet;
250 ///
251 /// let mut bs = DenseBitSet::from_integer(0b111000111000111000111);
252 /// bs.rotl(10);
253 ///
254 /// assert_eq!(bs.to_integer(), 0b1110001110001110001110000000000 );
255 /// ```
256 pub fn rotl(&mut self, shift: u32) {
257 self.state = self.state.rotate_left(shift);
258 }
259
260 /// Returns the position of the first set bit (little endian convention)
261 ///
262 /// # Example
263 /// ```
264 /// # use rust_dense_bitset::DenseBitSet;
265 /// let dbs = DenseBitSet::from_integer(256);
266 /// println!("{}", dbs.first_set());
267 /// ```
268 pub fn first_set(self) -> u32 {
269 self.state.trailing_zeros()
270 }
271}
272
273/// This is a compact implementation of the `BitSet` trait over a 64-bit word (which is the native
274/// word size for many architectures), allowing for efficient operations and compact memory usage.
275///
276/// Modifiers and accessors are boundary checked to ensure that operations remain within that 64 bit range.
277///
278/// Note: The `BitSet` trait must be in scope in order to use methods from this trait.
279impl BitSet for DenseBitSet {
280 /// Sets the bit at index `position` to `value`.
281 /// The bitset needs to be mutable for this operation to succeed.
282 ///
283 /// # Example
284 /// ```
285 /// use rust_dense_bitset::DenseBitSet;
286 /// use rust_dense_bitset::BitSet;
287 ///
288 /// let mut bs = DenseBitSet::new();
289 /// bs.set_bit(25, true); // This sets the bit at index 25 , hence the 26th bit -> 2^25
290 ///
291 /// assert_eq!(bs.to_integer(), 33554432);
292 /// ```
293 fn set_bit(&mut self, position: usize, value: bool) {
294 assert!(
295 position < 64,
296 "This implementation is currently limited to 64 bit bitsets."
297 );
298 if value {
299 self.state |= 1 << position
300 } else {
301 self.state &= !(1 << position)
302 }
303 }
304
305 /// Get the bit at index `position`.
306 ///
307 /// # Example
308 /// ```
309 /// use rust_dense_bitset::DenseBitSet;
310 /// use rust_dense_bitset::BitSet;
311 ///
312 /// let bs = DenseBitSet::from_integer(65536);
313 ///
314 /// assert!(bs.get_bit(16));
315 /// ```
316 fn get_bit(&self, position: usize) -> bool {
317 assert!(
318 position < 64,
319 "This implementation is currently limited to 64 bit bitsets."
320 );
321
322 (self.state >> position) & 1 == 1
323 }
324
325 /// Returns the bitset's Hamming weight (in other words, the number of bits set to true).
326 ///
327 /// # Example
328 /// ```
329 /// use rust_dense_bitset::DenseBitSet;
330 /// use rust_dense_bitset::BitSet;
331 ///
332 /// let bs = DenseBitSet::from_integer(0b01100100111010);
333 ///
334 /// println!("{}", bs.get_weight()); // -> 7
335 /// ```
336 fn get_weight(&self) -> u32 {
337 self.state.count_ones()
338 }
339
340 /// This resets the bitset to its empty state.
341 /// (The bitset must be mutable for this operation).
342 ///
343 /// # Example
344 /// ```
345 /// use rust_dense_bitset::DenseBitSet;
346 /// use rust_dense_bitset::BitSet;
347 ///
348 /// let mut bs = DenseBitSet::from_integer(1234567890);
349 /// bs.reset();
350 ///
351 /// assert!(bs.none());
352 /// ```
353 fn reset(&mut self) {
354 self.state = 0
355 }
356
357 /// Returns a representation of the bitset as a `String`.
358 ///
359 /// # Example
360 /// ```
361 /// use rust_dense_bitset::DenseBitSet;
362 /// use rust_dense_bitset::BitSet;
363 ///
364 /// let bs = DenseBitSet::from_integer(68719481088);
365 ///
366 /// println!("{}", bs.to_string()) // -> "0000000000000000000000000001000000000000000000000001000100000000"
367 /// ```
368 fn to_string(self) -> String {
369 format!("{:064b}", self.state)
370 }
371}
372
373impl fmt::Debug for DenseBitSet {
374 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
375 write!(f, "{:064b}", self.to_integer())
376 }
377}
378
379impl PartialEq for DenseBitSet {
380 fn eq(&self, other: &Self) -> bool {
381 self.state == other.to_integer()
382 }
383}
384
385impl Eq for DenseBitSet {}
386
387impl Hash for DenseBitSet {
388 fn hash<H: Hasher>(&self, state: &mut H) {
389 self.state.hash(state);
390 }
391}
392
393impl BitAnd for DenseBitSet {
394 type Output = Self;
395 fn bitand(self, rhs: Self) -> Self {
396 Self {
397 state: self.state & rhs.state,
398 }
399 }
400}
401
402impl BitAndAssign for DenseBitSet {
403 fn bitand_assign(&mut self, rhs: Self) {
404 self.state &= rhs.state;
405 }
406}
407
408impl BitOr for DenseBitSet {
409 type Output = Self;
410 fn bitor(self, rhs: Self) -> Self {
411 Self {
412 state: self.state | rhs.state,
413 }
414 }
415}
416
417impl BitOrAssign for DenseBitSet {
418 fn bitor_assign(&mut self, rhs: Self) {
419 self.state |= rhs.state;
420 }
421}
422
423impl BitXor for DenseBitSet {
424 type Output = Self;
425 fn bitxor(self, rhs: Self) -> Self {
426 Self {
427 state: self.state ^ rhs.state,
428 }
429 }
430}
431
432impl BitXorAssign for DenseBitSet {
433 fn bitxor_assign(&mut self, rhs: Self) {
434 self.state ^= rhs.state;
435 }
436}
437
438impl Not for DenseBitSet {
439 type Output = Self;
440 fn not(self) -> Self {
441 Self { state: !self.state }
442 }
443}
444
445impl Shl<usize> for DenseBitSet {
446 type Output = Self;
447 fn shl(self, rhs: usize) -> Self {
448 if rhs >= 64 {
449 Self { state: 0 }
450 } else {
451 Self {
452 state: self.state << rhs,
453 }
454 }
455 }
456}
457
458impl ShlAssign<usize> for DenseBitSet {
459 fn shl_assign(&mut self, rhs: usize) {
460 if rhs >= 64 {
461 self.reset();
462 } else {
463 self.state <<= rhs;
464 }
465 }
466}
467
468impl Shr<usize> for DenseBitSet {
469 type Output = Self;
470 fn shr(self, rhs: usize) -> Self {
471 if rhs >= 64 {
472 Self { state: 0 }
473 } else {
474 Self {
475 state: self.state >> rhs,
476 }
477 }
478 }
479}
480
481impl ShrAssign<usize> for DenseBitSet {
482 fn shr_assign(&mut self, rhs: usize) {
483 if rhs >= 64 {
484 self.reset();
485 } else {
486 self.state >>= rhs;
487 }
488 }
489}