#include "scann/oss_wrappers/scann_bits.h"
#include <cstdint>
namespace research_scann {
namespace bits {
#if (defined(__i386__) || defined(__x86_64__)) && defined(__GNUC__)
#else
int FindLSBSetNonZero(uint32_t n) {
int rc = 31;
for (int i = 4, shift = 1 << 4; i >= 0; --i) {
const uint32_t x = n << shift;
if (x != 0) {
n = x;
rc -= shift;
}
shift >>= 1;
}
return rc;
}
#endif
const char num_bits[] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4,
2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4,
2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5,
3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
int Count(const void *m, int num_bytes) {
int nbits = 0;
const uint8_t *s = static_cast<const uint8_t *>(m);
for (int i = 0; i < num_bytes; i++) nbits += num_bits[*s++];
return nbits;
}
int Log2Ceiling(uint32_t n) {
int floor = Log2Floor(n);
if ((n & (n - 1)) == 0)
return floor;
else
return floor + 1;
}
int Log2Ceiling64(uint64_t n) {
int floor = Log2Floor64(n);
if ((n & (n - 1)) == 0)
return floor;
else
return floor + 1;
}
} }