環境

コンパイラ: GCC or clang
規格: C++14 or C++17 or C++20

標準のみで、boost等は使えません。

質問内容

サイズが 64bit を超えるstd::bitset の 1 になっているビットのうち最上位のビットの位置を取得したいです。
0b0101 は 3 、0b0000 は 0 となるような値です。
Ruby, Python で言うところの bit_length を計算したいです。

ループを回したり二分探索をするだけであれば難しくは無いですが簡潔では無いように思います。
何かベストプラクティスのようなものはありますでしょうか。

y_waiwai

2021/02/23 23:28

まずはそのループを回す方法でコードを組んて提示しましょう。まるっきりの丸投げでは回答はつかないかと思います

退会済みユーザー

2021/02/24 07:17 編集

64bitを超えるを見逃していたので、コメントを取り消します。

行動規範の内容に同意します

回答2件

ベストアンサー

C++20標準ライブラリで追加されたビット操作関数を利用すれば、unsinged long longビット幅以下に限ってMSB位置計算を簡潔かつ高速に行えます。

c++
1#include <bit>  // C++20
2#include <bitset>
3#include <limits>
4
5template <size_t N>
6size_t msb_pos(const std::bitset<N>& bs)
7{
8  constexpr size_t ULL_BITS = std::numeric_limits<unsigned long long>::digits;
9  static_assert(N <= ULL_BITS);
10  return std::bit_width(bs.to_ullong());
11}

サイズが 64bit を超えるstd::bitset の 1 になっているビットのうち最上位のビットの位置を取得したいです。
ループを回したり二分探索をするだけであれば難しくは無いですが簡潔では無いように思います。

このstd::bit_width関数を活用する前提で、unsinged long longビット幅づつ検査するアルゴリズムを書いてみました。
...素直に先頭bitからループを回した方がマシかもしれませんね。

c++
1template <size_t N>
2size_t msb_pos(const std::bitset<N>& bs)
3{
4  constexpr size_t ULL_BITS = std::numeric_limits<unsigned long long>::digits;
5  if constexpr (N <= ULL_BITS) {
6    return std::bit_width(bs.to_ullong());
7  }
8  else {
9    std::bitset<N> mask = std::bitset<N>{~(0ULL)} << (N - ULL_BITS);
10    int shift = N - ULL_BITS;
11    while (0 < shift) {
12      if ((bs & mask).any())
13        break;
14      mask >>= ULL_BITS;
15      shift -= ULL_BITS;
16    }
17    if (shift <= 0) {
18      return std::bit_width(bs.to_ullong());
19    } else {
20      auto tmp = bs >> shift;
21      return std::bit_width(tmp.to_ullong())) + shift;
22    }
23  }
24}