2 的幂次方 ——《C/C++ 位运算黑科技 02》

欢迎大家来我的博客逛逛👏：hauhau.cn

原理

现在我们使用的二进制码表示都很简单：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，其他位不变。而与上自身之后，这些 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 的幂次方。

Benchmark

#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/power2Unable to determine clock rate from sysctl: hw.cpufrequency: No such file or directory2022-03-26T13:24:41+08:00Running /Users/hominsu/CLionProjects/bit-hacks-bench/cmake-build-release-appleclang/bench/power2Run 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   1000000000BM_power2_1/-1152921504606846976      0.443 ns 0.443 ns   1000000000BM_power2_1/-36028797018963968 0.443 ns 0.443 ns   1000000000BM_power2_1/-1125899906842624  0.443 ns 0.443 ns   1000000000BM_power2_1/-35184372088832    0.443 ns 0.443 ns   1000000000BM_power2_1/-1099511627776     0.444 ns 0.444 ns   1000000000BM_power2_1/-343597383680.443 ns 0.443 ns   1000000000BM_power2_1/-1073741824 0.444 ns 0.444 ns   1000000000BM_power2_1/-33554432   0.444 ns 0.444 ns   1000000000BM_power2_1/-1048576    0.444 ns 0.444 ns   1000000000BM_power2_1/-32768      0.443 ns 0.443 ns   1000000000BM_power2_1/-10240.443 ns 0.443 ns   1000000000BM_power2_1/-32  0.444 ns 0.444 ns   1000000000BM_power2_1/-1   0.444 ns 0.444 ns   1000000000BM_power2_1/0    0.314 ns 0.314 ns   1000000000BM_power2_1/1    0.444 ns 0.443 ns   1000000000BM_power2_1/32   0.444 ns 0.444 ns   1000000000BM_power2_1/1024 0.443 ns 0.443 ns   1000000000BM_power2_1/327680.443 ns 0.443 ns   1000000000BM_power2_1/1048576     0.443 ns 0.443 ns   1000000000BM_power2_1/33554432    0.446 ns 0.446 ns   1000000000BM_power2_1/1073741824  0.443 ns 0.443 ns   1000000000BM_power2_1/34359738368 0.443 ns 0.443 ns   1000000000BM_power2_1/1099511627776      0.444 ns 0.444 ns   1000000000BM_power2_1/35184372088832     0.443 ns 0.443 ns   1000000000BM_power2_1/1125899906842624   0.444 ns 0.444 ns   1000000000BM_power2_1/36028797018963968  0.443 ns 0.443 ns   1000000000BM_power2_1/11529215046068469760.443 ns 0.443 ns   1000000000BM_power2_1/92233720368547758070.444 ns 0.444 ns   1000000000BM_power2_2/-9223372036854775808      0.443 ns 0.443 ns   1000000000BM_power2_2/-1152921504606846976      0.443 ns 0.443 ns   1000000000BM_power2_2/-36028797018963968 0.444 ns 0.444 ns   1000000000BM_power2_2/-1125899906842624  0.444 ns 0.444 ns   1000000000BM_power2_2/-35184372088832    0.443 ns 0.443 ns   1000000000BM_power2_2/-1099511627776     0.443 ns 0.443 ns   1000000000BM_power2_2/-343597383680.444 ns 0.444 ns   1000000000BM_power2_2/-1073741824 0.444 ns 0.444 ns   1000000000BM_power2_2/-33554432   0.443 ns 0.443 ns   1000000000BM_power2_2/-1048576    0.444 ns 0.444 ns   1000000000BM_power2_2/-32768      0.444 ns 0.444 ns   1000000000BM_power2_2/-10240.445 ns 0.445 ns   1000000000BM_power2_2/-32  0.444 ns 0.444 ns   1000000000BM_power2_2/-1   0.443 ns 0.443 ns   1000000000BM_power2_2/0    0.313 ns 0.313 ns   1000000000BM_power2_2/1    0.443 ns 0.443 ns   1000000000BM_power2_2/32   0.444 ns 0.444 ns   1000000000BM_power2_2/1024 0.444 ns 0.443 ns   1000000000BM_power2_2/327680.443 ns 0.443 ns   1000000000BM_power2_2/1048576     0.443 ns 0.443 ns   1000000000BM_power2_2/33554432    0.444 ns 0.444 ns   1000000000BM_power2_2/1073741824  0.443 ns 0.443 ns   1000000000BM_power2_2/34359738368 0.443 ns 0.443 ns   1000000000BM_power2_2/1099511627776      0.443 ns 0.443 ns   1000000000BM_power2_2/35184372088832     0.443 ns 0.443 ns   1000000000BM_power2_2/1125899906842624   0.444 ns 0.444 ns   1000000000BM_power2_2/36028797018963968  0.445 ns 0.445 ns   1000000000BM_power2_2/11529215046068469760.444 ns 0.444 ns   1000000000BM_power2_2/92233720368547758070.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/power22022-03-26T13:30:11+08:00Running /tmp/tmp.CtmwmpTLjC/cmake-build-release-1104/bench/power2Run 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   1000000000BM_power2_1/-1152921504606846976      0.496 ns 0.495 ns   1000000000BM_power2_1/-36028797018963968 0.490 ns 0.489 ns   1000000000BM_power2_1/-1125899906842624  0.489 ns 0.489 ns   1000000000BM_power2_1/-35184372088832    0.485 ns 0.484 ns   1000000000BM_power2_1/-1099511627776     0.493 ns 0.492 ns   1000000000BM_power2_1/-343597383680.488 ns 0.488 ns   1000000000BM_power2_1/-1073741824 0.491 ns 0.490 ns   1000000000BM_power2_1/-33554432   0.489 ns 0.488 ns   1000000000BM_power2_1/-1048576    0.496 ns 0.495 ns   1000000000BM_power2_1/-32768      0.491 ns 0.490 ns   1000000000BM_power2_1/-10240.491 ns 0.490 ns   1000000000BM_power2_1/-32  0.484 ns 0.484 ns   1000000000BM_power2_1/-1   0.495 ns 0.494 ns   1000000000BM_power2_1/0    0.886 ns 0.885 ns    788464796BM_power2_1/1    0.486 ns 0.486 ns   1000000000BM_power2_1/32   0.491 ns 0.490 ns   1000000000BM_power2_1/1024 0.489 ns 0.489 ns   1000000000BM_power2_1/327680.491 ns 0.491 ns   1000000000BM_power2_1/1048576     0.491 ns 0.490 ns   1000000000BM_power2_1/33554432    0.494 ns 0.493 ns   1000000000BM_power2_1/1073741824  0.484 ns 0.484 ns   1000000000BM_power2_1/34359738368 0.492 ns 0.491 ns   1000000000BM_power2_1/1099511627776      0.491 ns 0.490 ns   1000000000BM_power2_1/35184372088832     0.495 ns 0.495 ns   1000000000BM_power2_1/1125899906842624   0.484 ns 0.483 ns   1000000000BM_power2_1/36028797018963968  0.493 ns 0.492 ns   1000000000BM_power2_1/11529215046068469760.491 ns 0.490 ns   1000000000BM_power2_1/92233720368547758070.496 ns 0.495 ns   1000000000BM_power2_2/-9223372036854775808      0.552 ns 0.551 ns   1000000000BM_power2_2/-1152921504606846976      0.552 ns 0.552 ns   1000000000BM_power2_2/-36028797018963968 0.561 ns 0.560 ns   1000000000BM_power2_2/-1125899906842624  0.546 ns 0.546 ns   1000000000BM_power2_2/-35184372088832    0.551 ns 0.550 ns   1000000000BM_power2_2/-1099511627776     0.553 ns 0.553 ns   1000000000BM_power2_2/-343597383680.552 ns 0.551 ns   1000000000BM_power2_2/-1073741824 0.552 ns 0.552 ns   1000000000BM_power2_2/-33554432   0.553 ns 0.552 ns   1000000000BM_power2_2/-1048576    0.553 ns 0.552 ns   1000000000BM_power2_2/-32768      0.545 ns 0.545 ns   1000000000BM_power2_2/-10240.554 ns 0.553 ns   1000000000BM_power2_2/-32  0.548 ns 0.547 ns   1000000000BM_power2_2/-1   0.546 ns 0.546 ns   1000000000BM_power2_2/0    0.493 ns 0.493 ns   1000000000BM_power2_2/1    0.553 ns 0.553 ns   1000000000BM_power2_2/32   0.554 ns 0.553 ns   1000000000BM_power2_2/1024 0.545 ns 0.544 ns   1000000000BM_power2_2/327680.555 ns 0.555 ns   1000000000BM_power2_2/1048576     0.550 ns 0.549 ns   1000000000BM_power2_2/33554432    0.550 ns 0.549 ns   1000000000BM_power2_2/1073741824  0.555 ns 0.554 ns   1000000000BM_power2_2/34359738368 0.551 ns 0.550 ns   1000000000BM_power2_2/1099511627776      0.553 ns 0.553 ns   1000000000BM_power2_2/35184372088832     0.553 ns 0.552 ns   1000000000BM_power2_2/1125899906842624   0.552 ns 0.552 ns   1000000000BM_power2_2/36028797018963968  0.552 ns 0.552 ns   1000000000BM_power2_2/11529215046068469760.551 ns 0.551 ns   1000000000BM_power2_2/92233720368547758070.554 ns 0.553 ns   1000000000