原理#
現在私たちが使用している二進数表現は非常にシンプルです：1、2、4、8、16・・・・・・
注意深く観察すると、一連の二進数の中で、もし 1 が一つだけ現れると、それは 2 の冪乗です。
コード#
template <typename T, class = std::enable_if_t<std::is_integral_v<T>>>
inline bool power2_1(T v)
{
return v && !(v & (v - 1));
}
または
template <typename T, class = std::enable_if_t<std::is_integral_v<T>>>
inline bool power2_2(T v)
{
return v && (v & -v) == v;
}
原理の分析#
方法一#
2 の冪乗は 1 が一つだけなので、最後の 1 を取り除いた後に 0 と等しいかどうかを判断すれば良いです。
v & (v - 1);
上記のコードは最下位の 1 を取り除くことができ、その原理も非常にシンプルです：1 を減らすことで最下位の 1 が 0 になり、さらに低い位に 1 が生成され、他の位は変わりません。そして自身と AND 演算を行うことで、これらの 1 と以前の最下位の 1 がクリアされます。
しかし、0 は特例なので、これを除外する必要があります：
v && !(v & (v - 1));
方法二#
方法二は方法一に似ています。まず v & -v が何に使われるかを知る必要があります。v & -v は実際には二進数の低位から高位への最初の 1 のビットインデックスを取得することです。例えば、111 の場合、111 の補数は 001 で、111 & 001 = 001 です；110 の場合、110 の補数は 010 で、110 & 010 = 010 です；
明らかに、ある数のビットインデックスがその数自身と等しい場合、それは 2 の冪乗です。
ベンチマーク#
#include "benchmark/benchmark.h"
template<typename T, class = std::enable_if_t<std::is_integral_v<T>>>
inline bool power2_1(T v) {
return v && !(v & (v - 1));
}
template<typename T, class = std::enable_if_t<std::is_integral_v<T>>>
inline bool power2_2(T v) {
return v && ((v & -v) == v);
}
static void BM_power2_1(benchmark::State &state) {
for (auto _: state) {
benchmark::DoNotOptimize(power2_1(state.range(0)));
}
}
static void BM_power2_2(benchmark::State &state) {
for (auto _: state) {
benchmark::DoNotOptimize(power2_2(state.range(0)));
}
}
BENCHMARK(BM_power2_1)->RangeMultiplier(32)->Range(INT64_MIN, INT64_MAX);
BENCHMARK(BM_power2_2)->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/power2
Unable to determine clock rate from sysctl: hw.cpufrequency: No such file or directory
2022-03-26T13:24:41+08:00
Running /Users/hominsu/CLionProjects/bit-hacks-bench/cmake-build-release-appleclang/bench/power2
Run on (8 X 24.0935 MHz CPU s)
CPU Caches:
L1 Data 64 KiB (x8)
L1 Instruction 128 KiB (x8)
L2 Unified 4096 KiB (x2)
Load Average: 1.38, 1.45, 1.71
---------------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------------
BM_power2_1/-9223372036854775808 0.443 ns 0.443 ns 1000000000
BM_power2_1/-1152921504606846976 0.443 ns 0.443 ns 1000000000
BM_power2_1/-36028797018963968 0.443 ns 0.443 ns 1000000000
BM_power2_1/-1125899906842624 0.443 ns 0.443 ns 1000000000
BM_power2_1/-35184372088832 0.443 ns 0.443 ns 1000000000
BM_power2_1/-1099511627776 0.444 ns 0.444 ns 1000000000
BM_power2_1/-34359738368 0.443 ns 0.443 ns 1000000000
BM_power2_1/-1073741824 0.444 ns 0.444 ns 1000000000
BM_power2_1/-33554432 0.444 ns 0.444 ns 1000000000
BM_power2_1/-1048576 0.444 ns 0.444 ns 1000000000
BM_power2_1/-32768 0.443 ns 0.443 ns 1000000000
BM_power2_1/-1024 0.443 ns 0.443 ns 1000000000
BM_power2_1/-32 0.444 ns 0.444 ns 1000000000
BM_power2_1/-1 0.444 ns 0.444 ns 1000000000
BM_power2_1/0 0.314 ns 0.314 ns 1000000000
BM_power2_1/1 0.444 ns 0.443 ns 1000000000
BM_power2_1/32 0.444 ns 0.444 ns 1000000000
BM_power2_1/1024 0.443 ns 0.443 ns 1000000000
BM_power2_1/32768 0.443 ns 0.443 ns 1000000000
BM_power2_1/1048576 0.443 ns 0.443 ns 1000000000
BM_power2_1/33554432 0.446 ns 0.446 ns 1000000000
BM_power2_1/1073741824 0.443 ns 0.443 ns 1000000000
BM_power2_1/34359738368 0.443 ns 0.443 ns 1000000000
BM_power2_1/1099511627776 0.444 ns 0.444 ns 1000000000
BM_power2_1/35184372088832 0.443 ns 0.443 ns 1000000000
BM_power2_1/1125899906842624 0.444 ns 0.444 ns 1000000000
BM_power2_1/36028797018963968 0.443 ns 0.443 ns 1000000000
BM_power2_1/1152921504606846976 0.443 ns 0.443 ns 1000000000
BM_power2_1/9223372036854775807 0.444 ns 0.444 ns 1000000000
BM_power2_2/-9223372036854775808 0.443 ns 0.443 ns 1000000000
BM_power2_2/-1152921504606846976 0.443 ns 0.443 ns 1000000000
BM_power2_2/-36028797018963968 0.444 ns 0.444 ns 1000000000
BM_power2_2/-1125899906842624 0.444 ns 0.444 ns 1000000000
BM_power2_2/-35184372088832 0.443 ns 0.443 ns 1000000000
BM_power2_2/-1099511627776 0.443 ns 0.443 ns 1000000000
BM_power2_2/-34359738368 0.444 ns 0.444 ns 1000000000
BM_power2_2/-1073741824 0.444 ns 0.444 ns 1000000000
BM_power2_2/-33554432 0.443 ns 0.443 ns 1000000000
BM_power2_2/-1048576 0.444 ns 0.444 ns 1000000000
BM_power2_2/-32768 0.444 ns 0.444 ns 1000000000
BM_power2_2/-1024 0.445 ns 0.445 ns 1000000000
BM_power2_2/-32 0.444 ns 0.444 ns 1000000000
BM_power2_2/-1 0.443 ns 0.443 ns 1000000000
BM_power2_2/0 0.313 ns 0.313 ns 1000000000
BM_power2_2/1 0.443 ns 0.443 ns 1000000000
BM_power2_2/32 0.444 ns 0.444 ns 1000000000
BM_power2_2/1024 0.444 ns 0.443 ns 1000000000
BM_power2_2/32768 0.443 ns 0.443 ns 1000000000
BM_power2_2/1048576 0.443 ns 0.443 ns 1000000000
BM_power2_2/33554432 0.444 ns 0.444 ns 1000000000
BM_power2_2/1073741824 0.443 ns 0.443 ns 1000000000
BM_power2_2/34359738368 0.443 ns 0.443 ns 1000000000
BM_power2_2/1099511627776 0.443 ns 0.443 ns 1000000000
BM_power2_2/35184372088832 0.443 ns 0.443 ns 1000000000
BM_power2_2/1125899906842624 0.444 ns 0.444 ns 1000000000
BM_power2_2/36028797018963968 0.445 ns 0.445 ns 1000000000
BM_power2_2/1152921504606846976 0.444 ns 0.444 ns 1000000000
BM_power2_2/9223372036854775807 0.450 ns 0.449 ns 1000000000
以下は i5-9500 と gcc 8.5.0 (Red Hat 8.5.0-10) を使用して CentOS-8-Stream で得られた結果です。
/tmp/tmp.CtmwmpTLjC/cmake-build-release-1104/bench/power2
2022-03-26T13:30:11+08:00
Running /tmp/tmp.CtmwmpTLjC/cmake-build-release-1104/bench/power2
Run on (6 X 4099.87 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: 3.17, 1.60, 1.17
---------------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------------
BM_power2_1/-9223372036854775808 0.487 ns 0.487 ns 1000000000
BM_power2_1/-1152921504606846976 0.496 ns 0.495 ns 1000000000
BM_power2_1/-36028797018963968 0.490 ns 0.489 ns 1000000000
BM_power2_1/-1125899906842624 0.489 ns 0.489 ns 1000000000
BM_power2_1/-35184372088832 0.485 ns 0.484 ns 1000000000
BM_power2_1/-1099511627776 0.493 ns 0.492 ns 1000000000
BM_power2_1/-34359738368 0.488 ns 0.488 ns 1000000000
BM_power2_1/-1073741824 0.491 ns 0.490 ns 1000000000
BM_power2_1/-33554432 0.489 ns 0.488 ns 1000000000
BM_power2_1/-1048576 0.496 ns 0.495 ns 1000000000
BM_power2_1/-32768 0.491 ns 0.490 ns 1000000000
BM_power2_1/-1024 0.491 ns 0.490 ns 1000000000
BM_power2_1/-32 0.484 ns 0.484 ns 1000000000
BM_power2_1/-1 0.495 ns 0.494 ns 1000000000
BM_power2_1/0 0.886 ns 0.885 ns 788464796
BM_power2_1/1 0.486 ns 0.486 ns 1000000000
BM_power2_1/32 0.491 ns 0.490 ns 1000000000
BM_power2_1/1024 0.489 ns 0.489 ns 1000000000
BM_power2_1/32768 0.491 ns 0.491 ns 1000000000
BM_power2_1/1048576 0.491 ns 0.490 ns 1000000000
BM_power2_1/33554432 0.494 ns 0.493 ns 1000000000
BM_power2_1/1073741824 0.484 ns 0.484 ns 1000000000
BM_power2_1/34359738368 0.492 ns 0.491 ns 1000000000
BM_power2_1/1099511627776 0.491 ns 0.490 ns 1000000000
BM_power2_1/35184372088832 0.495 ns 0.495 ns 1000000000
BM_power2_1/1125899906842624 0.484 ns 0.483 ns 1000000000
BM_power2_1/36028797018963968 0.493 ns 0.492 ns 1000000000
BM_power2_1/1152921504606846976 0.491 ns 0.490 ns 1000000000
BM_power2_1/9223372036854775807 0.496 ns 0.495 ns 1000000000
BM_power2_2/-9223372036854775808 0.552 ns 0.551 ns 1000000000
BM_power2_2/-1152921504606846976 0.552 ns 0.552 ns 1000000000
BM_power2_2/-36028797018963968 0.561 ns 0.560 ns 1000000000
BM_power2_2/-1125899906842624 0.546 ns 0.546 ns 1000000000
BM_power2_2/-35184372088832 0.551 ns 0.550 ns 1000000000
BM_power2_2/-1099511627776 0.553 ns 0.553 ns 1000000000
BM_power2_2/-34359738368 0.552 ns 0.551 ns 1000000000
BM_power2_2/-1073741824 0.552 ns 0.552 ns 1000000000
BM_power2_2/-33554432 0.553 ns 0.552 ns 1000000000
BM_power2_2/-1048576 0.553 ns 0.552 ns 1000000000
BM_power2_2/-32768 0.545 ns 0.545 ns 1000000000
BM_power2_2/-1024 0.554 ns 0.553 ns 1000000000
BM_power2_2/-32 0.548 ns 0.547 ns 1000000000
BM_power2_2/-1 0.546 ns 0.546 ns 1000000000
BM_power2_2/0 0.493 ns 0.493 ns 1000000000
BM_power2_2/1 0.553 ns 0.553 ns 1000000000
BM_power2_2/32 0.554 ns 0.553 ns 1000000000
BM_power2_2/1024 0.545 ns 0.544 ns 1000000000
BM_power2_2/32768 0.555 ns 0.555 ns 1000000000
BM_power2_2/1048576 0.550 ns 0.549 ns 1000000000
BM_power2_2/33554432 0.550 ns 0.549 ns 1000000000
BM_power2_2/1073741824 0.555 ns 0.554 ns 1000000000
BM_power2_2/34359738368 0.551 ns 0.550 ns 1000000000
BM_power2_2/1099511627776 0.553 ns 0.553 ns 1000000000
BM_power2_2/35184372088832 0.553 ns 0.552 ns 1000000000
BM_power2_2/1125899906842624 0.552 ns 0.552 ns 1000000000
BM_power2_2/36028797018963968 0.552 ns 0.552 ns 1000000000
BM_power2_2/1152921504606846976 0.551 ns 0.551 ns 1000000000
BM_power2_2/9223372036854775807 0.554 ns 0.553 ns 1000000000