値を表現するために必要な最小のbit幅 (bit_width)
(src/utility/bit/bit-width.hpp)

View this file on GitHub
Last update: 2023-07-30 00:54:52+09:00
Include: #include "src/utility/bit/bit-width.hpp"

bit_width

usize bit_width(u64 n)

n を表現するために必要な最小のビット幅を求める。

$n = 0$ のときは $0$ が返る。

計算量

$O(\log \log n)$

制約

C++17 以前であること。

C++20 以降では std::bit_width(T n) を使用すること。

appendix

立っている bit のうち最も大きい桁よりも小さい bit をすべて 1 で埋め、popcount でその数を取得している。

Depends on

Required by

Verified with

Code

#pragma once

#include "src/cpp-template/header/int-alias.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include "src/utility/bit/popcount.hpp"

#include <cassert>

namespace luz {

  usize bit_width(u64 x) {
    assert(__cplusplus <= 201703L);

    if (x == 0) {
      return 0;
    }

#ifdef __GNUC__
    return 64 - __builtin_clzll(x);
#endif

    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return popcount(x);
  }

} // namespace luz

#line 2 "src/utility/bit/bit-width.hpp"

#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

  using i32  = std::int32_t;
  using i64  = std::int64_t;
  using i128 = __int128_t;

  using u32  = std::uint32_t;
  using u64  = std::uint64_t;
  using u128 = __uint128_t;

} // namespace luz
#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 2 "src/utility/bit/popcount.hpp"

#line 5 "src/utility/bit/popcount.hpp"

#include <cassert>

namespace luz {

  usize popcount(u64 x) {
    assert(__cplusplus <= 201703L);

#ifdef __GNUC__
    return __builtin_popcountll(x);
#endif

    x -= (x >> 1) & 0x5555555555555555;
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    x += (x >> 4) & 0x0f0f0f0f0f0f0f0f;
    return x * 0x0101010101010101 >> 56 & 0x7f;
  }

} // namespace luz
#line 6 "src/utility/bit/bit-width.hpp"

#line 8 "src/utility/bit/bit-width.hpp"

namespace luz {

  usize bit_width(u64 x) {
    assert(__cplusplus <= 201703L);

    if (x == 0) {
      return 0;
    }

#ifdef __GNUC__
    return 64 - __builtin_clzll(x);
#endif

    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return popcount(x);
  }

} // namespace luz

値を表現するために必要な最小のbit幅 (bit_width) (src/utility/bit/bit-width.hpp)

bit_width

計算量

制約

appendix

Depends on

Required by

Verified with

Code

値を表現するために必要な最小のbit幅 (bit_width)
(src/utility/bit/bit-width.hpp)