Expand description
§Prime Bytes
A bit is a 1 or a 0. A byte is a list of 8 bits. Example: [01101001]
A “prime byte” is what we’ll name our abstraction over k-values. Reiterating, each bit in the prime byte will correspond to the k-value:
[ 01 07 11 13 17 19 23 29 ]
So, if we want to retrieve “the bit that corresponds to the k-value 13”, that’s the same as asking “please give me the 4th bit”. We can do this by performing a right shift, then taking the result modulo 2. For instance, if we want to retrieve the third bit, we remove the last 5 bits by shifting the byte to the right by 5. Then, we take the result modulo 2 to ignore the first 2 bits.
// the third bit >|< is 1
let byte: u8 = 0b01101010;
assert_eq!((byte >> 5) % 2, 1);What if we want to extract the k values of a prime byte that are set to 1? In the previous
example, we had 01101010. If we map each bit to a boolean array, where 0 maps to false and 1
maps to true, we can then zip it to the array of k values, yielding the following tuples:
[ (false, 1), (true, 7), (true, 11), ... (false, 19), (true, 23), (false, 29) ]
We can then filter all tuples with false, and extract the k value out of the remaining tuples. The resulting list, contains all k-values that are prime, according to the byte. Of course, we can only get their true value by determining the byte’s offset.
There are other methods implemented in this library, which are all tweaked versions of what I showed above. For example, maybe we want to restrict to prime bytes where the k-values belong to some range. That’s easily done by applying a second condition to the filter which is that the given range contains the k-value.
§Visibility
I decided to keep Prime Bytes public, in case anyone else feels like developing a data structure using prime bytes. But if not, they can just simply ignore it.