other/bit_width.cpp

• View this file on GitHub
• Last update: 2020-03-11 22:42:07+09:00

Depends on

• other/countl_zero.cpp
• other/countr_zero.cpp
• other/int_alias.cpp

Required by

• Axiotis-Tzamos Unbounded Knapsack (algorithm/axiotis_tzamos_unbounded_knapsack.cpp)
• Dual Segment Tree (data_structure/dual_segment_tree.cpp)
• Lazy Segment Tree (data_structure/lazy_segment_tree.cpp)
• Radix Heap (data_structure/radix_heap.cpp)

Verified with

• test/axiotis_tzamos_unbounded_knapsack.test.cpp
• test/dual_segment_tree.test.cpp
• test/lazy_segment_tree.test.cpp
• test/radix_heap.test.cpp

Code

#pragma once

#include "other/countl_zero.cpp"
#include "other/int_alias.cpp"

usize bit_width(const u64 x) { return 64 - countl_zero(x); }

#line 2 "other/bit_width.cpp"

#line 2 "other/countl_zero.cpp"

#line 2 "other/countr_zero.cpp"

#line 2 "other/int_alias.cpp"

#include <cstddef>
#include <cstdint>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
#line 4 "other/countr_zero.cpp"

#include <array>

usize countr_zero(u64 x) {
  if (x == 0)
    return 64;
#ifdef __GNUC__
  return __builtin_ctzll(x);
#else
  constexpr std::array<usize, 64> table = {
      0,  1,  2,  7,  3,  13, 8,  27, 4,  33, 14, 36, 9,  49, 28, 19,
      5,  25, 34, 17, 15, 53, 37, 55, 10, 46, 50, 39, 29, 42, 20, 57,
      63, 6,  12, 26, 32, 35, 48, 18, 24, 16, 52, 54, 45, 38, 41, 56,
      62, 11, 31, 47, 23, 51, 44, 40, 61, 30, 22, 43, 60, 21, 59, 58};
  return table[(x & ~x + 1) * 0x218A7A392DD9ABF >> 58 & 0x3F];
#endif
}
#line 5 "other/countl_zero.cpp"

usize countl_zero(u64 x) {
#ifdef __GNUC__
  return x == 0 ? 64 : __builtin_clzll(x);
#else
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  x |= x >> 32;
  return 64 - countr_zero(~x);
#endif
}
#line 5 "other/bit_width.cpp"

usize bit_width(const u64 x) { return 64 - countl_zero(x); }

Back to top page