原理#
数の絶対値を求めることは、負の数を正の数に変換することであり、その補数を求めるだけで済みます（反数に 1 を加える）
コード#
template <typename T, class = typename std::enable_if_t<!std::is_unsigned_v<T>>>
inline typename std::make_unsigned_t<T> mabs(T _val) {
const T mask = _val >> (sizeof(T) * 8 - 1);
return (_val ^ mask) - mask;
}
原理剖析#
-12 を例にとります：-12 の補数は 10100（ここではマシンのワード長を 5 ビットと仮定します）
手順は以下の通りです：
-
まずマスク
maskを取得します:const T mask = _val >> (sizeof(T) * 8 - 1);10100 を 4 ビット左にシフトすると 11111 になります。ここでの 11111 は非常に巧妙な設計です。
なぜマスクを右シフトで取得するのか、直接右シフトして 0x1 で & を取って符号ビットを得るのではなく、理由は次の通りです：11111 というマスクは実際にはすべて符号ビットから構成されています。符号ビットが 1 であれば、生成されたマスクは元のデータと直接排他的論理和（XOR）を取ることで反数を得て、1 を加えることで補数が得られます。
符号ビットが 0 であれば、得られるマスクは全て 0 となり、0 と任意の数の XOR はその数自身になります。
-
反数を求めます：
_val ^= mask;上の手順で示したように、10100 と 11111 の XOR は 01011 になり、反数を求めます。
もしここが正の数であれば、マスクは 00000 となり、XOR 後は変わりません。
-
1 を加えます：
_val - mask;01011 - 11111 = 01100 で - 12 の絶対値 12 が得られます。
なぜここで 1 を加えるのがマスクを引くことになったのか、実は簡単です。以前に求めたマスクは 11111 で、これは実際には - 1 の補数です。1 を加えるにはマスクを引くだけで済みます。
もしここが正の数であれば、マスクは 00000 となり、0 を引いても影響はありません。
こうして、絶対値を求めるアルゴリズムが実現されました。負の数が入ると正の数に変わり、正の数が入ると変わらないのはとても簡単ですね。
ベンチマーク#
#include "benchmark/benchmark.h"
template<typename T, class = typename std::enable_if_t<!std::is_unsigned_v<T>>>
inline typename std::make_unsigned_t<T> mabs(T _val) {
const T mask = _val >> (sizeof(T) * 8 - 1);
return (_val + mask) ^ mask;
}
static void BM_mabs(benchmark::State &state) {
for (auto _: state) {
benchmark::DoNotOptimize(mabs(state.range(0)));
}
}
static void BM_std_abs(benchmark::State &state) {
for (auto _: state) {
benchmark::DoNotOptimize(std::abs(state.range(0)));
}
}
BENCHMARK(BM_mabs)->RangeMultiplier(32)->Range(INT64_MIN, INT64_MAX);
BENCHMARK(BM_std_abs)->RangeMultiplier(32)->Range(INT64_MIN, INT64_MAX);
BENCHMARK_MAIN();
以下は MacBook Air (M1, 2020) と Apple clang 13.1.6 で得られた結果です。
/Users/hominsu/CLionProjects/bit-hacks-bench/cmake-build-release-appleclang/bench/abs
Unable to determine clock rate from sysctl: hw.cpufrequency: No such file or directory
2022-03-26T13:00:40+08:00
Running /Users/hominsu/CLionProjects/bit-hacks-bench/cmake-build-release-appleclang/bench/abs
Run on (8 X 24.1207 MHz CPU s)
CPU Caches:
L1 Data 64 KiB (x8)
L1 Instruction 128 KiB (x8)
L2 Unified 4096 KiB (x2)
Load Average: 2.42, 2.09, 2.29
--------------------------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------------------------
BM_mabs/-9223372036854775808 0.340 ns 0.340 ns 1000000000
BM_mabs/-1152921504606846976 0.344 ns 0.344 ns 1000000000
BM_mabs/-36028797018963968 0.342 ns 0.342 ns 1000000000
BM_mabs/-1125899906842624 0.336 ns 0.336 ns 1000000000
BM_mabs/-35184372088832 0.343 ns 0.343 ns 1000000000
BM_mabs/-1099511627776 0.342 ns 0.342 ns 1000000000
BM_mabs/-34359738368 0.343 ns 0.343 ns 1000000000
BM_mabs/-1073741824 0.343 ns 0.343 ns 1000000000
BM_mabs/-33554432 0.344 ns 0.344 ns 1000000000
BM_mabs/-1048576 0.345 ns 0.345 ns 1000000000
BM_mabs/-32768 0.344 ns 0.344 ns 1000000000
BM_mabs/-1024 0.343 ns 0.343 ns 1000000000
BM_mabs/-32 0.347 ns 0.347 ns 1000000000
BM_mabs/-1 0.343 ns 0.343 ns 1000000000
BM_mabs/0 0.344 ns 0.344 ns 1000000000
BM_mabs/1 0.346 ns 0.346 ns 1000000000
BM_mabs/32 0.341 ns 0.341 ns 1000000000
BM_mabs/1024 0.346 ns 0.346 ns 1000000000
BM_mabs/32768 0.347 ns 0.347 ns 1000000000
BM_mabs/1048576 0.348 ns 0.348 ns 1000000000
BM_mabs/33554432 0.344 ns 0.344 ns 1000000000
BM_mabs/1073741824 0.340 ns 0.340 ns 1000000000
BM_mabs/34359738368 0.350 ns 0.350 ns 1000000000
BM_mabs/1099511627776 0.343 ns 0.343 ns 1000000000
BM_mabs/35184372088832 0.339 ns 0.339 ns 1000000000
BM_mabs/1125899906842624 0.341 ns 0.341 ns 1000000000
BM_mabs/36028797018963968 0.341 ns 0.341 ns 1000000000
BM_mabs/1152921504606846976 0.348 ns 0.348 ns 1000000000
BM_mabs/9223372036854775807 0.346 ns 0.346 ns 1000000000
BM_std_abs/-9223372036854775808 0.340 ns 0.340 ns 1000000000
BM_std_abs/-1152921504606846976 0.345 ns 0.345 ns 1000000000
BM_std_abs/-36028797018963968 0.347 ns 0.347 ns 1000000000
BM_std_abs/-1125899906842624 0.340 ns 0.340 ns 1000000000
BM_std_abs/-35184372088832 0.348 ns 0.348 ns 1000000000
BM_std_abs/-1099511627776 0.345 ns 0.345 ns 1000000000
BM_std_abs/-34359738368 0.347 ns 0.347 ns 1000000000
BM_std_abs/-1073741824 0.344 ns 0.344 ns 1000000000
BM_std_abs/-33554432 0.342 ns 0.342 ns 1000000000
BM_std_abs/-1048576 0.347 ns 0.347 ns 1000000000
BM_std_abs/-32768 0.345 ns 0.345 ns 1000000000
BM_std_abs/-1024 0.347 ns 0.347 ns 1000000000
BM_std_abs/-32 0.348 ns 0.348 ns 1000000000
BM_std_abs/-1 0.341 ns 0.341 ns 1000000000
BM_std_abs/0 0.352 ns 0.352 ns 1000000000
BM_std_abs/1 0.346 ns 0.346 ns 1000000000
BM_std_abs/32 0.348 ns 0.348 ns 1000000000
BM_std_abs/1024 0.344 ns 0.344 ns 1000000000
BM_std_abs/32768 0.342 ns 0.342 ns 1000000000
BM_std_abs/1048576 0.348 ns 0.348 ns 1000000000
BM_std_abs/33554432 0.346 ns 0.346 ns 1000000000
BM_std_abs/1073741824 0.346 ns 0.346 ns 1000000000
BM_std_abs/34359738368 0.347 ns 0.347 ns 1000000000
BM_std_abs/1099511627776 0.343 ns 0.343 ns 1000000000
BM_std_abs/35184372088832 0.347 ns 0.347 ns 1000000000
BM_std_abs/1125899906842624 0.351 ns 0.351 ns 1000000000
BM_std_abs/36028797018963968 0.340 ns 0.340 ns 1000000000
BM_std_abs/1152921504606846976 0.346 ns 0.346 ns 1000000000
BM_std_abs/9223372036854775807 0.343 ns 0.343 ns 1000000000
以下は i5-9500 と gcc 8.5.0 (Red Hat 8.5.0-10) で得られた結果です。
/tmp/tmp.CtmwmpTLjC/cmake-build-release-1104/bench/abs
2022-03-26T13:10:38+08:00
Running /tmp/tmp.CtmwmpTLjC/cmake-build-release-1104/bench/abs
Run on (6 X 4138.24 MHz CPU s)
CPU Caches:
L1 Data 32 KiB (x6)
L1 Instruction 32 KiB (x6)
L2 Unified 256 KiB (x6)
L3 Unified 9216 KiB (x1)
Load Average: 0.94, 0.61, 0.49
--------------------------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------------------------
BM_mabs/-9223372036854775808 0.366 ns 0.366 ns 1000000000
BM_mabs/-1152921504606846976 0.367 ns 0.367 ns 1000000000
BM_mabs/-36028797018963968 0.366 ns 0.365 ns 1000000000
BM_mabs/-1125899906842624 0.368 ns 0.367 ns 1000000000
BM_mabs/-35184372088832 0.370 ns 0.370 ns 1000000000
BM_mabs/-1099511627776 0.364 ns 0.364 ns 1000000000
BM_mabs/-34359738368 0.370 ns 0.370 ns 1000000000
BM_mabs/-1073741824 0.364 ns 0.364 ns 1000000000
BM_mabs/-33554432 0.367 ns 0.367 ns 1000000000
BM_mabs/-1048576 0.368 ns 0.368 ns 1000000000
BM_mabs/-32768 0.371 ns 0.370 ns 1000000000
BM_mabs/-1024 0.365 ns 0.365 ns 1000000000
BM_mabs/-32 0.365 ns 0.365 ns 1000000000
BM_mabs/-1 0.364 ns 0.363 ns 1000000000
BM_mabs/0 0.368 ns 0.368 ns 1000000000
BM_mabs/1 0.366 ns 0.365 ns 1000000000
BM_mabs/32 0.364 ns 0.363 ns 1000000000
BM_mabs/1024 0.368 ns 0.368 ns 1000000000
BM_mabs/32768 0.370 ns 0.369 ns 1000000000
BM_mabs/1048576 0.368 ns 0.367 ns 1000000000
BM_mabs/33554432 0.366 ns 0.366 ns 1000000000
BM_mabs/1073741824 0.367 ns 0.366 ns 1000000000
BM_mabs/34359738368 0.371 ns 0.371 ns 1000000000
BM_mabs/1099511627776 0.368 ns 0.367 ns 1000000000
BM_mabs/35184372088832 0.370 ns 0.369 ns 1000000000
BM_mabs/1125899906842624 0.363 ns 0.362 ns 1000000000
BM_mabs/36028797018963968 0.368 ns 0.367 ns 1000000000
BM_mabs/1152921504606846976 0.372 ns 0.372 ns 1000000000
BM_mabs/9223372036854775807 0.367 ns 0.366 ns 1000000000
BM_std_abs/-9223372036854775808 0.491 ns 0.490 ns 1000000000
BM_std_abs/-1152921504606846976 0.484 ns 0.484 ns 1000000000
BM_std_abs/-36028797018963968 0.490 ns 0.490 ns 1000000000
BM_std_abs/-1125899906842624 0.487 ns 0.486 ns 1000000000
BM_std_abs/-35184372088832 0.493 ns 0.493 ns 1000000000
BM_std_abs/-1099511627776 0.486 ns 0.485 ns 1000000000
BM_std_abs/-34359738368 0.491 ns 0.491 ns 1000000000
BM_std_abs/-1073741824 0.487 ns 0.486 ns 1000000000
BM_std_abs/-33554432 0.490 ns 0.490 ns 1000000000
BM_std_abs/-1048576 0.489 ns 0.488 ns 1000000000
BM_std_abs/-32768 0.494 ns 0.493 ns 1000000000
BM_std_abs/-1024 0.490 ns 0.489 ns 1000000000
BM_std_abs/-32 0.491 ns 0.490 ns 1000000000
BM_std_abs/-1 0.486 ns 0.486 ns 1000000000
BM_std_abs/0 0.492 ns 0.492 ns 1000000000
BM_std_abs/1 0.487 ns 0.486 ns 1000000000
BM_std_abs/32 0.487 ns 0.486 ns 1000000000
BM_std_abs/1024 0.493 ns 0.492 ns 1000000000
BM_std_abs/32768 0.489 ns 0.489 ns 1000000000
BM_std_abs/1048576 0.492 ns 0.491 ns 1000000000
BM_std_abs/33554432 0.487 ns 0.486 ns 1000000000
BM_std_abs/1073741824 0.493 ns 0.492 ns 1000000000
BM_std_abs/34359738368 0.486 ns 0.486 ns 1000000000
BM_std_abs/1099511627776 0.493 ns 0.492 ns 1000000000
BM_std_abs/35184372088832 0.489 ns 0.488 ns 1000000000
BM_std_abs/1125899906842624 0.491 ns 0.491 ns 1000000000
BM_std_abs/36028797018963968 0.490 ns 0.490 ns 1000000000
BM_std_abs/1152921504606846976 0.494 ns 0.493 ns 1000000000
BM_std_abs/9223372036854775807 0.491 ns 0.490 ns 1000000000