Skip to content

Instantly share code, notes, and snippets.

@jweinst1
Last active September 15, 2025 22:10
Show Gist options
  • Save jweinst1/63c4eea5fb489e9508fea1c7e6644d10 to your computer and use it in GitHub Desktop.
Save jweinst1/63c4eea5fb489e9508fea1c7e6644d10 to your computer and use it in GitHub Desktop.
Bit set in rust that stores vectors for membership
fn sub_distance<const S: usize>(v1:&[u64;S], v2:&[u64;S]) -> u64 {
let mut total = 0;
for i in 0..S {
total += v1[i] - v2[i];
}
return total;
}
fn and_pop_distance<const S: usize>(v1:&[u64;S], v2:&[u64;S]) -> u64 {
let mut total = 0;
for i in 0..S {
total += (v1[i] & v2[i]).count_ones();
}
return total as u64;
}
fn and_pop_shift_right_distance<const S: usize, const D:usize>(v1:&[u64;S], v2:&[u64;S]) -> u64 {
const {
assert!(D < 6);
}
let mut total = 0;
for i in 0..S {
total += (v1[i] & (v2[i] >> D)).count_ones();
}
return total as u64;
}
fn check_memb<const S: usize, const B:usize>(key:&[u64;S], set:&[[u64;S];B]) -> bool {
let part = &set[(key[0] as usize) & (B - 1)];
for i in 0..S {
if key[i] & part[i] != key[i] {
return false
}
}
true
}
fn store_memb<const S: usize, const B:usize>(key:&[u64;S], set:&mut [[u64;S];B]) {
const {
assert!(B == 256);
}
let part = &mut set[(key[0] as usize) & (B - 1)];
for i in 0..S {
part[i] |= key[i];
}
}
fn test1() {
let mut k = [0b1101, 0b1001, 0b11111];
let mut s: [[u64; 3]; 256] = [[0; 3]; 256];
store_memb(&k, &mut s);
println!("{:?}", check_memb(&k, &s));
k[2] = k[2] << 1;
println!("{:?}", check_memb(&k, &s));
}
fn main() {
test1();
let mut s: [[u64; 3]; 256] = [[0; 3]; 256];
let mut k = [0, 0, 0];
let mut fakes = 0;
for i in 0..10000 {
if i % 2 == 0 {
k[0] = i;
k[2] = i + 95;
store_memb(&k, &mut s);
}
}
k[0] = 0;
k[1] = 0;
k[2] = 0;
for i in 0..10000 {
if i % 2 != 0 {
k[0] = i;
k[2] = i + 95;
if check_memb(&k, &s) {
fakes += 1;
}
}
}
println!("Fake count {:?}", fakes);
println!("sub dist {:?}", sub_distance(&s[0], &s[1]));
println!("shift and dist {:?}", and_pop_shift_right_distance::<3, 1>(&s[0], &s[1]));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment