NTZとNLZ
NTZは最下位ビットから連続する立っていないビットの数、NLZは最上位ビットから連続する立っていないビットの数のことを言います。
具体的に言うと、8bitの
00101000
というビット列があった場合、最下位ビットからは0が3つ連続しているのでNTZは3、最上位ビットからは0が2つ連続しているのでNLZは2になります。
アルゴリズムの高速化などを考えると割と必要になることがあるのですが、いまいちライブラリが整理されていない感があります。
CPUの命令セットにも含まれていたりするようですが、全てのビットが0だった時の結果がバラバラだったりもするので、あまり使い物になりません。
という訳で、NTZとNLZを実装してみたいと思います。
とは言え、どういう方法で実装すればいいのかについては、既にネット上で情報を探れば色々出てくるので、今更私が解説しても仕方ありません。
この記事ではなるべく汎用的に使えるようにテンプレート関数を定義しようと思います。
方法
まずは何も言わずにここを読みましょう。
当面C#と.NETな記録: [C#] 一番右端の立っているビット位置を求める「ものすごい」コード
上記で紹介されている黒魔術を使います。これはC#のものですが、C++で実装します。
上記の記事では64bitに関して扱っていますが、全ての整数型に対応しようと思ったら、32bit、16bit、8bitのそれぞれについて実装する必要があります。
謎の数値と配列
上記で紹介した記事に出ていたマジックナンバーとテーブルを拡張して、以下の数値と配列を使用します。
//8bit版
static constexpr auto magic8 = 0x1DU;
static constexpr int ntz_table8[15] = {8, 0, -1, 1, 6, -1, -1, 2, 7, -1, 5, -1, -1, 4, 3};
static constexpr int nlz_table8[15] = {8, 7, -1, 6, 1, -1, -1, 5, 0, -1, 2, -1, -1, 3, 4};
//16bit版
static constexpr auto magic16 = 0x0F2DU;
static constexpr int ntz_table16[31] = {
16, 0, -1, 1, -1, 8, -1, 2, 14, -1, -1, 9, -1, 11, -1, 3,
15, -1, 7, -1, 13, -1, 10, -1, -1, 6, 12, -1, 5, -1, 4,
};
static constexpr int nlz_table16[31] = {
16, 15, -1, 14, -1, 7, -1, 13, 1, -1, -1, 6, -1, 4, -1, 12,
0, -1, 8, -1, 2, -1, 5, -1, -1, 9, 3, -1, 10, -1, 11,
};
// 32bit版
static constexpr auto magic32 = 0x07C56E99U;
static constexpr int ntz_table32[63] = {
32, 0, -1, 1, -1, 10, -1, 2, 29, -1, 11, -1, 25, -1, -1, 3,
30, -1, -1, 23, -1, 12, 14, -1, -1, 26, -1, 16, -1, 19, -1, 4,
31, -1, 9, -1, 28, -1, 24, -1, -1, 22, -1, 13, -1, 15, 18, -1,
-1, 8, 27, -1, 21, -1, -1, 17, 7, -1, 20, -1, 6, -1, 5
};
static constexpr int nlz_table32[63] = {
32, 31, -1, 30, -1, 21, -1, 29, 2, -1, 20, -1, 6, -1, -1, 28,
1, -1, -1, 8, -1, 19, 17, -1, -1, 5, -1, 15, -1, 12, -1, 27,
0, -1, 22, -1, 3, -1, 7, -1, -1, 9, -1, 18, -1, 16, 13, -1,
-1, 23, 4, -1, 10, -1, -1, 14, 24, -1, 11, -1, 25, -1, 26
};
// 64bit版
static constexpr auto magic64 = 0x03F0A933ADCBD8D1ULL;
static constexpr int ntz_table64[127] = {
64, 0, -1, 1, -1, 12, -1, 2, 60, -1, 13, -1, -1, 53, -1, 3,
61, -1, -1, 21, -1, 14, -1, 42, -1, 24, 54, -1, -1, 28, -1, 4,
62, -1, 58, -1, 19, -1, 22, -1, -1, 17, 15, -1, -1, 33, -1, 43,
-1, 50, -1, 25, 55, -1, -1, 35, -1, 38, 29, -1, -1, 45, -1, 5,
63, -1, 11, -1, 59, -1, 52, -1, -1, 20, -1, 41, 23, -1, 27, -1,
-1, 57, 18, -1, 16, -1, 32, -1, 49, -1, -1, 34, 37, -1, 44, -1,
-1, 10, -1, 51, -1, 40, -1, 26, 56, -1, -1, 31, 48, -1, 36, -1,
9, -1, 39, -1, -1, 30, 47, -1, 8, -1, -1, 46, 7, -1, 6,
};
static constexpr int nlz_table64[127] = {
64, 63, -1, 62, -1, 51, -1, 61, 3, -1, 50, -1, -1, 10, -1, 60,
2, -1, -1, 42, -1, 49, -1, 21, -1, 39, 9, -1, -1, 35, -1, 59,
1, -1, 5, -1, 44, -1, 41, -1, -1, 46, 48, -1, -1, 30, -1, 20,
-1, 13, -1, 38, 8, -1, -1, 28, -1, 25, 34, -1, -1, 18, -1, 58,
0, -1, 52, -1, 4, -1, 11, -1, -1, 43, -1, 22, 40, -1, 36, -1,
-1, 6, 45, -1, 47, -1, 31, -1, 14, -1, -1, 29, 26, -1, 19, -1,
-1, 53, -1, 12, -1, 23, -1, 37, 7, -1, -1, 32, 15, -1, 27, -1,
54, -1, 24, -1, -1, 33, 16, -1, 55, -1, -1, 17, 56, -1, 57,
};
1bit分拡張することで、0をチェックする必要性をなくしています。その分テーブルのサイズは増えてしまうのですが、せいぜい1KB程度なので、大抵の場合は気にすることはないでしょう。
ちなみに、-1で埋められている部分は使用されません。
NTZ, NLZ用の型特性クラス
テンプレートで扱う必要があるので、以下のように特性クラスを実装します
template<std::size_t size>
struct ntz_traits;
template<>
struct ntz_traits<1>
{
using type = std::uint8_t;
static constexpr int shift = 4;
static constexpr auto magic = magic8;
static constexpr auto ntz_table = ntz_table8;
static constexpr auto nlz_table = nlz_table8;
};
template<>
struct ntz_traits<2>
{
using type = std::uint16_t;
static constexpr int shift = 11;
static constexpr auto magic = magic16;
static constexpr auto ntz_table = ntz_table16;
static constexpr auto nlz_table = nlz_table16;
};
template<>
struct ntz_traits<4>
{
using type = std::uint32_t;
static constexpr int shift = 26;
static constexpr auto magic = magic32;
static constexpr auto ntz_table = ntz_table32;
static constexpr auto nlz_table = nlz_table32;
};
template<>
struct ntz_traits<8>
{
using type = std::uint64_t;
static constexpr int shift = 57;
static constexpr auto magic = magic64;
static constexpr auto ntz_table = ntz_table64;
static constexpr auto nlz_table = nlz_table64;
};
このように定義を行うことで、整数型Tに対して、ntz_traits<sizeof(T)>を使用してマジックナンバーやテーブルを取得できます。
整数型のビット深度が8, 16, 32, 64でない環境に関しては、とりあえず考えません。面倒なので。
NTZの実装
さて、これだけ定義してしまえば、NTZの実装は簡単です。
// SFINAEに必要なもろもろ
extern void* enabler;
template<bool condition, typename T = void>
using enable_if_type = typename std::enable_if<condition, T>::type;
template<typename T>
using make_unsigned_type = typename std::make_unsigned<T>::type;
// unsigned型のNTZ。例の黒魔術
template<typename T, enable_if_type<std::is_unsigned<T>{}>*& = enabler>
inline constexpr int ntz(T val) noexcept {
using tr= ntz_traits<sizeof(T)>;
using type = typename tr::type;
return tr::ntz_table[static_cast<type>(tr::magic*static_cast<type>(val&-val))>>tr::shift];
}
// signdな型はunsignedな型にキャストする
template<typename T, enable_if_type<std::is_signed<T>{}>*& = enabler>
inline constexpr int ntz(T val) noexcept {
return ntz(static_cast<make_unsigned_type<T>>(val));
}
// enum型は同じサイズの整数型にキャストする
template<typename T, enable_if_type<std::is_enum<T>{}>*& = enabler>
inline constexpr int ntz(T val) noexcept {
return ntz(static_cast<typename ntz_traits<sizeof(T)>::type>(val));
}
// ポインタ型はuintptr_tにキャストして整数型として扱う
template<typename T>
inline int ntz(T* val) noexcept { return ntz(reinterpret_cast<std::uintptr_t>(val)); }
// bool型は1bitとみなす
inline constexpr int ntz(bool val) noexcept { return val?0:1; }
// nullptrは0bitとみなす。多分使わないけど
inline constexpr int ntz(std::nullptr_t) noexcept { return 0; }
符号なしの整数型を基本に、符号付きの型、列挙型、ポインタ型に関しては、同じサイズの符号付き整数型にキャストして呼び出すオーバーロード関数を用意しています。
また、bool型とnullptr_t型に関しては特殊なので別のオーバーロードを用意しました。
NLZの実装
さて、ntzではval&-valという式を使って一番下位の立っているビットを残すという計算を行ったわけですが、一番上位の立っているビットを残すのは少し手間のかかる操作です。
考え方は単純で、例えばvalが64bitの型なら、
val = val | (val>>32);
val = val | (val>>16);
val = val | (val>>8);
val = val | (val>>4);
val = val | (val>>2);
val = val | (val>>1);
val = val ^ (val>>1);
と、一番上位の立っているビットから下を全部1にしてから、一番上位以外のビットを全て反転します。
テンプレートで、かつC++11のconstexprでも利用可能な再帰関数にするために、以下の様にします。
template<int n>
struct highest_bit
{
template<typename T>
static inline constexpr T get(T val) noexcept {
return highest_bit<n/2>::get(static_cast<T>(val | (val >> n)));
}
};
template<>
struct highest_bit<1>
{
template<typename T>
static inline constexpr T get_2(T val) noexcept { return static_cast<T>(val ^ (val >> 1)); }
template<typename T>
static inline constexpr T get(T val) noexcept { return get_2(static_cast<T>(val | (val >> 1))); }
};
template<typename T>
inline constexpr T get_highest_bit(T val) noexcept { return highest_bit<sizeof(T)*4>::get(val); }
これさえ定義されれば、後はntzとほぼ同じです。
// unsigned型のNLZ
template<typename T, enable_if_type<std::is_unsigned<T>{}>*& = enabler>
inline constexpr int nlz(T val) noexcept {
using tr= ntz_traits<sizeof(T)>;
using type = typename tr::type;
return tr::nlz_table[static_cast<type>(tr::magic*get_highest_bit(val))>>tr::shift];
}
template<typename T, enable_if_type<std::is_signed<T>{}>*& = enabler>
inline constexpr int nlz(T val) noexcept {
return nlz(static_cast<make_unsigned_type<T>>(val));
}
template<typename T, enable_if_type<std::is_enum<T>{}>*& = enabler>
inline constexpr int nlz(T val) noexcept {
return nlz(static_cast<typename ntz_traits<sizeof(T)>::type>(val));
}
template<typename T>
inline int nlz(T* val) noexcept { return nlz(reinterpret_cast<std::uintptr_t>(val)); }
inline constexpr int nlz(bool val) noexcept { return val?0:1; }
inline constexpr int nlz(std::nullptr_t) noexcept { return 0; }
終わりに
冒頭で紹介した記事を読んで、「こりゃスゲエ！」と思って実装してみたものの、全てのスカラー型に対応しようなんて思ったら意外と面倒でした。
あ、でもこれ全てじゃないですね。floatとdoubleとlong doubleに対応していないので。
浮動小数点型も、reinterpret_castを使用して無理やりIEEE754の内部表現をビット列と見做してNTZとNLZをとることは可能ですが、特にlong double辺りは64bitより大きい環境もあったりして面倒ですし、面倒な割には使いどころがなさそうなので今回は省きました。
NTZは整数型を素因数分解した時の2の次数です。これが分かると、ユークリッドの互除法より早い（除算を使わない）最小公倍数アルゴリズムが使えるようになったりします。
NLZを使えば、2つの整数型に対して、「上位ビットから見て初めて異なるビットが現れる位置」を求めることができます。
それが分かって何になるんだと思われるかもしれませんが、それに関しては後日別の記事で書こうと思います。
それでは本日はこの辺で。