1. 首页
  2. 文章中心
  3. 编程

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

81 阅读 0 评论
我是靠谱客的博主 虚幻自行车，最近开发中收集的这篇文章主要介绍2 的幂次方 ——《C/C++ 位运算黑科技 02》2 的幂次方 ——《C/C++ 位运算黑科技 02》，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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/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

最后

以上就是虚幻自行车为你收集整理的2 的幂次方 ——《C/C++ 位运算黑科技 02》2 的幂次方 ——《C/C++ 位运算黑科技 02》的全部内容，希望文章能够帮你解决2 的幂次方 ——《C/C++ 位运算黑科技 02》2 的幂次方 ——《C/C++ 位运算黑科技 02》所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(54)

相关文章

判断一个数是否为2的幂次方(位运算)C++
判断一个数是否为2的幂次方(位运算)C++
编写一个函数实现n^k（n的k次方），使用递归实现
编写一个函数实现n^k（n的k次方），使用递归实现
次方比较（c++基础）
次方比较（c++基础）
C语言 · 2的次幂表示 · 幂方分解
C语言 · 2的次幂表示 · 幂方分解
2 的幂次方 ——《C/C++ 位运算黑科技 02》2 的幂次方 ——《C/C++ 位运算黑科技 02》
2 的幂次方 ——《C/C++ 位运算黑科技 02》2 的幂次方 ——《C/C++ 位运算黑科技 02》
【C++代码】之《2的整数幂》
【C++代码】之《2的整数幂》
C++ 幂的问题
C++ 幂的问题
leetcode之4的幂（C++）
leetcode之4的幂（C++）

评论列表共有 0 条评论

立即
投稿
返回
顶部