25 #if !defined(__BMI2__) // BMI2 has everything in the header 26 #if SIZE_MAX == UINT32_MAX 62 static const uint8_t nth_bit_bit_count[256] = {
63 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4,
64 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
65 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4,
66 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
67 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
68 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
69 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5,
70 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
71 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
72 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
73 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
79 static const uint8_t nth_bit_bit_pos[8][256] = {
81 255, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0,
82 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
83 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0,
84 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0,
85 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0,
86 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0,
87 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0,
88 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
89 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0,
90 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
91 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0,
92 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
95 255, 255, 255, 1, 255, 2, 2, 1, 255, 3, 3, 1, 3, 2, 2, 1, 255, 4,
96 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 255, 5, 5, 1,
97 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 5, 4, 4, 1, 4, 2,
98 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 255, 6, 6, 1, 6, 2, 2, 1,
99 6, 3, 3, 1, 3, 2, 2, 1, 6, 4, 4, 1, 4, 2, 2, 1, 4, 3,
100 3, 1, 3, 2, 2, 1, 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1,
101 3, 2, 2, 1, 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2,
102 2, 1, 255, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1,
103 7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 7, 5,
104 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 5, 4, 4, 1,
105 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 7, 6, 6, 1, 6, 2,
106 2, 1, 6, 3, 3, 1, 3, 2, 2, 1, 6, 4, 4, 1, 4, 2, 2, 1,
107 4, 3, 3, 1, 3, 2, 2, 1, 6, 5, 5, 1, 5, 2, 2, 1, 5, 3,
108 3, 1, 3, 2, 2, 1, 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1,
112 255, 255, 255, 255, 255, 255, 255, 2, 255, 255, 255, 3, 255, 3, 3, 2,
113 255, 255, 255, 4, 255, 4, 4, 2, 255, 4, 4, 3, 4, 3, 3, 2,
114 255, 255, 255, 5, 255, 5, 5, 2, 255, 5, 5, 3, 5, 3, 3, 2,
115 255, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
116 255, 255, 255, 6, 255, 6, 6, 2, 255, 6, 6, 3, 6, 3, 3, 2,
117 255, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3, 3, 2,
118 255, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3, 2,
119 6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
120 255, 255, 255, 7, 255, 7, 7, 2, 255, 7, 7, 3, 7, 3, 3, 2,
121 255, 7, 7, 4, 7, 4, 4, 2, 7, 4, 4, 3, 4, 3, 3, 2,
122 255, 7, 7, 5, 7, 5, 5, 2, 7, 5, 5, 3, 5, 3, 3, 2,
123 7, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
124 255, 7, 7, 6, 7, 6, 6, 2, 7, 6, 6, 3, 6, 3, 3, 2,
125 7, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3, 3, 2,
126 7, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3, 2,
127 6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
130 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
131 255, 3, 255, 255, 255, 255, 255, 255, 255, 4, 255, 255, 255, 4,
132 255, 4, 4, 3, 255, 255, 255, 255, 255, 255, 255, 5, 255, 255,
133 255, 5, 255, 5, 5, 3, 255, 255, 255, 5, 255, 5, 5, 4,
134 255, 5, 5, 4, 5, 4, 4, 3, 255, 255, 255, 255, 255, 255,
135 255, 6, 255, 255, 255, 6, 255, 6, 6, 3, 255, 255, 255, 6,
136 255, 6, 6, 4, 255, 6, 6, 4, 6, 4, 4, 3, 255, 255,
137 255, 6, 255, 6, 6, 5, 255, 6, 6, 5, 6, 5, 5, 3,
138 255, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4,
139 4, 3, 255, 255, 255, 255, 255, 255, 255, 7, 255, 255, 255, 7,
140 255, 7, 7, 3, 255, 255, 255, 7, 255, 7, 7, 4, 255, 7,
141 7, 4, 7, 4, 4, 3, 255, 255, 255, 7, 255, 7, 7, 5,
142 255, 7, 7, 5, 7, 5, 5, 3, 255, 7, 7, 5, 7, 5,
143 5, 4, 7, 5, 5, 4, 5, 4, 4, 3, 255, 255, 255, 7,
144 255, 7, 7, 6, 255, 7, 7, 6, 7, 6, 6, 3, 255, 7,
145 7, 6, 7, 6, 6, 4, 7, 6, 6, 4, 6, 4, 4, 3,
146 255, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5,
147 5, 3, 7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4,
151 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
152 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
153 255, 255, 255, 4, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
154 255, 255, 255, 255, 255, 5, 255, 255, 255, 255, 255, 255, 255, 5,
155 255, 255, 255, 5, 255, 5, 5, 4, 255, 255, 255, 255, 255, 255,
156 255, 255, 255, 255, 255, 255, 255, 255, 255, 6, 255, 255, 255, 255,
157 255, 255, 255, 6, 255, 255, 255, 6, 255, 6, 6, 4, 255, 255,
158 255, 255, 255, 255, 255, 6, 255, 255, 255, 6, 255, 6, 6, 5,
159 255, 255, 255, 6, 255, 6, 6, 5, 255, 6, 6, 5, 6, 5,
160 5, 4, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
161 255, 255, 255, 7, 255, 255, 255, 255, 255, 255, 255, 7, 255, 255,
162 255, 7, 255, 7, 7, 4, 255, 255, 255, 255, 255, 255, 255, 7,
163 255, 255, 255, 7, 255, 7, 7, 5, 255, 255, 255, 7, 255, 7,
164 7, 5, 255, 7, 7, 5, 7, 5, 5, 4, 255, 255, 255, 255,
165 255, 255, 255, 7, 255, 255, 255, 7, 255, 7, 7, 6, 255, 255,
166 255, 7, 255, 7, 7, 6, 255, 7, 7, 6, 7, 6, 6, 4,
167 255, 255, 255, 7, 255, 7, 7, 6, 255, 7, 7, 6, 7, 6,
168 6, 5, 255, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5,
172 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
173 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
174 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
175 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
176 255, 255, 255, 255, 255, 255, 255, 5, 255, 255, 255, 255, 255, 255,
177 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
178 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 6, 255, 255,
179 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 6,
180 255, 255, 255, 255, 255, 255, 255, 6, 255, 255, 255, 6, 255, 6,
181 6, 5, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
182 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
183 255, 255, 255, 255, 255, 7, 255, 255, 255, 255, 255, 255, 255, 255,
184 255, 255, 255, 255, 255, 255, 255, 7, 255, 255, 255, 255, 255, 255,
185 255, 7, 255, 255, 255, 7, 255, 7, 7, 5, 255, 255, 255, 255,
186 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 7, 255, 255,
187 255, 255, 255, 255, 255, 7, 255, 255, 255, 7, 255, 7, 7, 6,
188 255, 255, 255, 255, 255, 255, 255, 7, 255, 255, 255, 7, 255, 7,
189 7, 6, 255, 255, 255, 7, 255, 7, 7, 6, 255, 7, 7, 6,
193 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
194 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
195 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
196 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
197 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
198 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
199 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
200 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
201 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
202 255, 6, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
203 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
204 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
205 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
206 255, 255, 255, 255, 255, 255, 255, 255, 255, 7, 255, 255, 255, 255,
207 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
208 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 7,
209 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
210 255, 7, 255, 255, 255, 255, 255, 255, 255, 7, 255, 255, 255, 7,
214 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
215 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
216 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
217 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
218 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
219 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
220 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
221 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
222 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
223 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
224 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
225 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
226 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
227 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
228 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
229 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
230 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
231 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
240 uint32_t next_byte = v & 255;
241 uint32_t byte_popcount = nth_bit_bit_count[next_byte];
242 if (r < byte_popcount)
return nth_bit_bit_pos[r][next_byte];
244 next_byte = (v >> 8) & 255;
245 byte_popcount = nth_bit_bit_count[next_byte];
246 if (r < byte_popcount)
return 8 + nth_bit_bit_pos[r][next_byte];
248 next_byte = (v >> 16) & 255;
249 byte_popcount = nth_bit_bit_count[next_byte];
250 if (r < byte_popcount)
return 16 + nth_bit_bit_pos[r][next_byte];
252 next_byte = (v >> 24) & 255;
253 byte_popcount = nth_bit_bit_count[next_byte];
254 if (r < byte_popcount)
return 24 + nth_bit_bit_pos[r][next_byte];
256 next_byte = (v >> 32) & 255;
257 byte_popcount = nth_bit_bit_count[next_byte];
258 if (r < byte_popcount)
return 32 + nth_bit_bit_pos[r][next_byte];
260 next_byte = (v >> 40) & 255;
261 byte_popcount = nth_bit_bit_count[next_byte];
262 if (r < byte_popcount)
return 40 + nth_bit_bit_pos[r][next_byte];
264 next_byte = (v >> 48) & 255;
265 byte_popcount = nth_bit_bit_count[next_byte];
266 if (r < byte_popcount)
return 48 + nth_bit_bit_pos[r][next_byte];
268 next_byte = (v >> 56) & 255;
269 byte_popcount = nth_bit_bit_count[next_byte];
270 if (r < byte_popcount)
return 56 + nth_bit_bit_pos[r][next_byte];
274 #elif SIZE_MAX == UINT64_MAX // 64-bit, non-BMI2 291 const uint8_t kSelectInByte[8 * 256] = {
292 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
293 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
294 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
295 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
296 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
297 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
298 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
299 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
300 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
301 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
302 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
303 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
304 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
305 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
306 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
307 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
309 0, 0, 0, 1, 0, 2, 2, 1, 0, 3, 3, 1, 3, 2, 2, 1,
310 0, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
311 0, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
312 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
313 0, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
314 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
315 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
316 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
317 0, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1,
318 7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
319 7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
320 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
321 7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
322 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
323 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
324 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
326 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 3, 0, 3, 3, 2,
327 0, 0, 0, 4, 0, 4, 4, 2, 0, 4, 4, 3, 4, 3, 3, 2,
328 0, 0, 0, 5, 0, 5, 5, 2, 0, 5, 5, 3, 5, 3, 3, 2,
329 0, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
330 0, 0, 0, 6, 0, 6, 6, 2, 0, 6, 6, 3, 6, 3, 3, 2,
331 0, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3, 3, 2,
332 0, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3, 2,
333 6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
334 0, 0, 0, 7, 0, 7, 7, 2, 0, 7, 7, 3, 7, 3, 3, 2,
335 0, 7, 7, 4, 7, 4, 4, 2, 7, 4, 4, 3, 4, 3, 3, 2,
336 0, 7, 7, 5, 7, 5, 5, 2, 7, 5, 5, 3, 5, 3, 3, 2,
337 7, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
338 0, 7, 7, 6, 7, 6, 6, 2, 7, 6, 6, 3, 6, 3, 3, 2,
339 7, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3, 3, 2,
340 7, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3, 2,
341 6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
343 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
344 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 4, 0, 4, 4, 3,
345 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 5, 0, 5, 5, 3,
346 0, 0, 0, 5, 0, 5, 5, 4, 0, 5, 5, 4, 5, 4, 4, 3,
347 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 6, 6, 3,
348 0, 0, 0, 6, 0, 6, 6, 4, 0, 6, 6, 4, 6, 4, 4, 3,
349 0, 0, 0, 6, 0, 6, 6, 5, 0, 6, 6, 5, 6, 5, 5, 3,
350 0, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
351 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 3,
352 0, 0, 0, 7, 0, 7, 7, 4, 0, 7, 7, 4, 7, 4, 4, 3,
353 0, 0, 0, 7, 0, 7, 7, 5, 0, 7, 7, 5, 7, 5, 5, 3,
354 0, 7, 7, 5, 7, 5, 5, 4, 7, 5, 5, 4, 5, 4, 4, 3,
355 0, 0, 0, 7, 0, 7, 7, 6, 0, 7, 7, 6, 7, 6, 6, 3,
356 0, 7, 7, 6, 7, 6, 6, 4, 7, 6, 6, 4, 6, 4, 4, 3,
357 0, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 3,
358 7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
360 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
361 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4,
362 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
363 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 5, 0, 5, 5, 4,
364 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
365 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 6, 6, 4,
366 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 6, 6, 5,
367 0, 0, 0, 6, 0, 6, 6, 5, 0, 6, 6, 5, 6, 5, 5, 4,
368 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7,
369 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 4,
370 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 5,
371 0, 0, 0, 7, 0, 7, 7, 5, 0, 7, 7, 5, 7, 5, 5, 4,
372 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 6,
373 0, 0, 0, 7, 0, 7, 7, 6, 0, 7, 7, 6, 7, 6, 6, 4,
374 0, 0, 0, 7, 0, 7, 7, 6, 0, 7, 7, 6, 7, 6, 6, 5,
375 0, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 4,
377 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
378 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
379 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
380 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
381 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
382 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
383 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
384 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 6, 6, 5,
385 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
386 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7,
387 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7,
388 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 5,
389 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7,
390 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 6,
391 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 6,
392 0, 0, 0, 7, 0, 7, 7, 6, 0, 7, 7, 6, 7, 6, 6, 5,
394 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
395 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
396 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
397 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
398 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
399 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
400 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
401 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
402 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
403 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
404 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
405 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7,
406 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
407 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7,
408 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7,
409 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 6,
411 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
412 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
413 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
414 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
415 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
416 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
417 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
418 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
419 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
420 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
421 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
422 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
423 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
424 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
425 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
426 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7
431 #endif // 64-bit, non-BMI2 432 #endif // !defined(__BMI2__)
int nth_bit(const uint64_t v, uint32_t r)