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 17digit (68bit) 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 