#ifndef SCANN_OSS_WRAPPERS_SCANN_BITS_H_
#define SCANN_OSS_WRAPPERS_SCANN_BITS_H_
#include <cstddef>
#include <cstdint>
#include "absl/numeric/bits.h"
namespace research_scann {
namespace bits {
#if (defined(__i386__) || defined(__x86_64__)) && defined(__GNUC__)
inline int FindLSBSetNonZero(uint32_t n) { return __builtin_ctz(n); }
inline int FindLSBSetNonZero64(uint64_t n) { return __builtin_ctzll(n); }
#else
int FindLSBSetNonZero(uint32_t n);
inline int FindLSBSetNonZero64(uint64_t n) {
const uint32_t bottombits = static_cast<uint32_t>(n);
if (bottombits == 0) {
return 32 + FindLSBSetNonZero(static_cast<uint32_t>(n >> 32));
} else {
return FindLSBSetNonZero(bottombits);
}
}
#endif
extern const char num_bits[];
int Count(const void *m, int num_bytes);
inline int Log2Floor(uint32_t n) { return absl::bit_width(n) - 1; }
inline int Log2FloorNonZero(uint32_t n) { return Log2Floor(n); }
inline int Log2Floor64(uint64_t n) { return absl::bit_width(n) - 1; }
inline int Log2FloorNonZero64(uint64_t n) { return Log2Floor64(n); }
inline int FindMSBSetNonZero(uint32_t n) { return Log2FloorNonZero(n); }
inline int FindMSBSetNonZero64(uint64_t n) { return Log2FloorNonZero64(n); }
int Log2Ceiling(uint32_t n);
int Log2Ceiling64(uint64_t n);
} }
#endif