Crate broadword [−] [src]
Broadword operations treat a u64
as a parallel vector of eight u8
s or i8
s.
This module also provides a population count function count_ones
and a
select function select1
.
The algorithms here are from Sebastiano Vigna, “Broadword Implementation of Rank/Select Queries,” but with several changes from that work:
-
Vigna uses a 17-digit (68-bit) constant “0x0F0F0F0F0F0F0F0F0.” I believe the correct constant is these 64 bits: 0x0F0F_0F0F_0F0F_0F0F.
-
Arithmetic operations are assumed to wrap on overflow. If this were not the case, Algorithm 1 (count_ones) would overflow its last line, when multiplying by L₈.
-
Line 2 of Algorithm 2 should read
s = (s & 0x3333_3333_3333_3333) + ((s >> 2) & 0x3333_3333_3333_3333);
In the paper, the shifted
s
appears asx
.
Constants
H8 |
Has the highest bit of every byte set: |
L8 |
Has the lowest bit of every byte set: |
Functions
count_ones |
Counts the number of ones in a |
i_le8 |
Parallel ≤, treating a |
select1 |
Finds the index of the |
select1_raw |
Finds the index of the |
u_le8 |
Parallel ≤, treating a |
u_nz8 |
Parallel >0, treating a |