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 as `x`.

Constants

 H8 Has the highest bit of every byte set: `0x8080_8080_8080_8080`. L8 Has the lowest bit of every byte set: `0x0101_0101_0101_0101`.

Functions

 count_ones Counts the number of ones in a `u64`. i_le8 Parallel ≤, treating a `u64` as a vector of 8 `i8`s. select1 Finds the index of the `r`th one bit in `x`. select1_raw Finds the index of the `r`th one bit in `x`, returning 72 when not found. u_le8 Parallel ≤, treating a `u64` as a vector of 8 `u8`s. u_nz8 Parallel >0, treating a `u64` as a vector of 8 `u8`s.