21 count_bits_in_word(PN_uint16 x) {
22 return (
int)num_bits_on[x];
30 count_bits_in_word(PN_uint32 x) {
31 #if defined(__GNUC__) && defined(__POPCNT__) 32 return __builtin_popcount((
unsigned int) x);
34 return (
int)num_bits_on[x & 0xffff] + (int)num_bits_on[(x >> 16) & 0xffff];
43 count_bits_in_word(PN_uint64 x) {
44 #if defined(__GNUC__) && defined(__POPCNT__) 45 return __builtin_popcountll((
unsigned long long) x);
47 return count_bits_in_word((PN_uint32)x) + count_bits_in_word((PN_uint32)(x >> 32));
57 flood_bits_down(PN_uint16 x) {
71 flood_bits_down(PN_uint32 x) {
86 flood_bits_down(PN_uint64 x) {
102 flood_bits_up(PN_uint16 x) {
116 flood_bits_up(PN_uint32 x) {
131 flood_bits_up(PN_uint64 x) {
147 get_lowest_on_bit(PN_uint16 x) {
148 #if defined(_MSC_VER) 149 unsigned long result;
150 return (_BitScanForward(&result, (
unsigned long) x) == 0) ? -1 : result;
151 #elif defined(__GNUC__) 152 return __builtin_ffs((
unsigned int) x) - 1;
158 PN_uint16 w = (x & (~x + 1));
159 return (
int)num_bits_on[w - 1];
169 get_lowest_on_bit(PN_uint32 x) {
170 #if defined(_MSC_VER) 171 unsigned long result;
172 return (_BitScanForward(&result, (
unsigned long) x) == 0) ? -1 : result;
173 #elif defined(__GNUC__) 174 return __builtin_ffs((
unsigned int) x) - 1;
180 PN_uint32 w = (x & (~x + 1));
181 return count_bits_in_word(w - 1);
191 get_lowest_on_bit(PN_uint64 x) {
192 #if defined(_MSC_VER) && defined(_M_X64) 193 unsigned long result;
194 return (_BitScanForward64(&result, (
unsigned __int64) x) == 0) ? -1 : result;
195 #elif defined(__GNUC__) 196 return __builtin_ffsll((
unsigned long long) x) - 1;
202 PN_uint64 w = (x & (~x + 1));
203 return count_bits_in_word(w - 1);
213 get_highest_on_bit(PN_uint16 x) {
214 #if defined(_MSC_VER) 215 unsigned long result;
216 return (_BitScanReverse(&result, (
unsigned long) x) == 0) ? -1 : result;
217 #elif defined(__GNUC__) 218 return (x == 0) ? -1 : 31 - __builtin_clz((
unsigned int) x);
220 PN_uint16 w = flood_bits_down(x);
221 return count_bits_in_word(w) - 1;
231 get_highest_on_bit(PN_uint32 x) {
232 #if defined(_MSC_VER) 233 unsigned long result;
234 return (_BitScanReverse(&result, (
unsigned long) x) == 0) ? -1 : result;
235 #elif defined(__GNUC__) 236 return (x == 0) ? -1 : 31 - __builtin_clz((
unsigned int) x);
238 PN_uint32 w = flood_bits_down(x);
239 return count_bits_in_word(w) - 1;
249 get_highest_on_bit(PN_uint64 x) {
250 #if defined(_MSC_VER) && defined(_M_X64) 251 unsigned long result;
252 return (_BitScanReverse64(&result, (
unsigned __int64) x) == 0) ? -1 : result;
253 #elif defined(__GNUC__) 254 return (x == 0) ? -1 : 63 - __builtin_clzll((
unsigned long long) x);
256 PN_uint64 w = flood_bits_down(x);
257 return count_bits_in_word(w) - 1;
269 get_next_higher_bit(PN_uint16 x) {
270 return get_highest_on_bit(x) + 1;
281 get_next_higher_bit(PN_uint32 x) {
282 return get_highest_on_bit(x) + 1;
293 get_next_higher_bit(PN_uint64 x) {
294 return get_highest_on_bit(x) + 1;