[−][src]Module succinct::broadword
Broadword operations treating u64
as a parallel vector.
From Sebastiano Vigna, “Broadword Implementation of Rank/Select Queries.” Changes from that work:
-
It 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
.
Structs
Broadword | Newtype for treating a |
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 |
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 |