AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

二进制中 1 的个数 ——《C/C++ 位运算黑科技 03》

2022-03-30 355
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 二进制中 1 的个数 ——《C/C++ 位运算黑科技 03》

欢迎大家来我的博客逛逛👏：homing.so

原理

计算一个二进制数中 1 的出现次数其实很简单，只需要不断用 v & (v - 1) 移除掉最后一个 1 即可，原理可以参考这篇文章：2 的幂次方 ——《C/C++ 位运算黑科技 02》

上述方法是一个普通的思考方向，下面我会介绍另外一种思路：并行计数器，来计算二进制数中出现的 1

实际上，我们可以将这个数看作是全部由单位的计数器组成，1、0 就代表单个计数器的状态，我们只要合并相邻的计数器即可，这其实也是归并的思想。

代码

inline unsigned count_bits(uint64_t v)
{
   
    v = (v & 0x5555555555555555) + ((v >> 1) & 0x5555555555555555);
    v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333);
    v = (v & 0x0f0f0f0f0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f0f0f0f0f);
    v = (v & 0x00ff00ff00ff00ff) + ((v >> 8) & 0x00ff00ff00ff00ff);
    v = (v & 0x0000ffff0000ffff) + ((v >> 16) & 0x0000ffff0000ffff);
    v = (v & 0x00000000ffffffff) + ((v >> 32) & 0x00000000ffffffff);
    return v;
}

inline unsigned count_bits(uint32_t v)
{
   
    v = (v & 0x55555555) + ((v >> 1) & 0x55555555);
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
    v = (v & 0x0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f);
    v = (v & 0x00ff00ff) + ((v >> 8) & 0x00ff00ff);
    v = (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff);
    return v;
}

inline unsigned count_bits(uint16_t v)
{
   
    v = (v & 0x5555) + ((v >> 1) & 0x5555);
    v = (v & 0x3333) + ((v >> 2) & 0x3333);
    v = (v & 0x0f0f) + ((v >> 4) & 0x0f0f);
    v = (v & 0x00ff) + ((v >> 8) & 0x00ff);
    return v;
}

inline unsigned count_bits(uint8_t v)
{
   
    v = (v & 0x55) + ((v >> 1) & 0x55);
    v = (v & 0x33) + ((v >> 2) & 0x33);
    v = (v & 0x0f) + ((v >> 4) & 0x0f);
    return v;
}

原理剖析

下面以 1110001010011110 作为例子，来解释并行计数器合并的方法：

val 1 1 1 0 0 0 1 0 1 0 0 1 1 1 1 0
& 0x5555 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
= 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0
val >> 1 0 1 1 1 0 0 0 1 0 1 0 0 1 1 1 1
& 0x5555 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
= 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1

然后两者相加就得到了相邻 2 个计数器的合并计数：1001000101011001，然后我们在以 2 个比特为单位来继续合并计数器

Val 10 01 00 01 01 01 10 01
& 0x3333 00 11 00 11 00 11 00 11
= 00 01 00 01 00 01 00 01
Val >> 2 00 10 01 00 01 01 01 10
& 0x3333 00 11 00 11 00 11 00 11
= 00 10 00 00 00 01 00 10

然后两者相加就得到了相邻 4 个计数器的合并计数：0011000100100011，然后我们在以 4 个比特为单位来继续合并计数器

Val 0011 0001 0010 0011
& 0x0f0f 0000 1111 0000 1111
= 0000 0001 0000 0011
Val >> 4 0000 0011 0001 0010
& 0x0f0f 0000 1111 0000 1111
= 0000 0011 0000 0010

然后两者相加就得到了相邻 8 个计数器的合并计数：0000010000000101，然后我们在以 8 个比特为单位来继续合并计数器

Val 00000100 00000101
&00ff 00000000 11111111
= 00000000 00000101
Val >> 8 00000000 00000100
&00ff 00000000 11111111
= 00000000 00000100

然后两者相加就得到了相邻 8 个计数器的合并计数：0000000000001001，转换成十进制就是 9，与原数字中的 1 的个数是相同的。

Benchmark

#include "benchmark/benchmark.h"

inline unsigned count_bits(uint64_t v)
{
   
  v = (v & 0x5555555555555555) + ((v >> 1) & 0x5555555555555555);
  v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333);
  v = (v & 0x0f0f0f0f0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f0f0f0f0f);
  v = (v & 0x00ff00ff00ff00ff) + ((v >> 8) & 0x00ff00ff00ff00ff);
  v = (v & 0x0000ffff0000ffff) + ((v >> 16) & 0x0000ffff0000ffff);
  v = (v & 0x00000000ffffffff) + ((v >> 32) & 0x00000000ffffffff);
  return v;
}

inline unsigned count_bits(uint32_t v)
{
   
  v = (v & 0x55555555) + ((v >> 1) & 0x55555555);
  v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
  v = (v & 0x0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f);
  v = (v & 0x00ff00ff) + ((v >> 8) & 0x00ff00ff);
  v = (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff);
  return v;
}

inline unsigned count_bits(uint16_t v)
{
   
  v = (v & 0x5555) + ((v >> 1) & 0x5555);
  v = (v & 0x3333) + ((v >> 2) & 0x3333);
  v = (v & 0x0f0f) + ((v >> 4) & 0x0f0f);
  v = (v & 0x00ff) + ((v >> 8) & 0x00ff);
  return v;
}

inline unsigned count_bits(uint8_t v)
{
   
  v = (v & 0x55) + ((v >> 1) & 0x55);
  v = (v & 0x33) + ((v >> 2) & 0x33);
  v = (v & 0x0f) + ((v >> 4) & 0x0f);
  return v;
}

static void BM_count_64(benchmark::State &state) {
   
  for (auto _: state) {
   
    uint64_t n = UINT64_MAX;
    benchmark::DoNotOptimize(count_bits(n));
  }
}

static void BM_count_32(benchmark::State &state) {
   
  for (auto _: state) {
   
    uint32_t n = UINT32_MAX;
    benchmark::DoNotOptimize(count_bits(n));
  }
}

static void BM_count_16(benchmark::State &state) {
   
  for (auto _: state) {
   
    uint16_t n = UINT16_MAX;
    benchmark::DoNotOptimize(count_bits(n));
  }
}

static void BM_count_8(benchmark::State &state) {
   
  for (auto _: state) {
   
    uint8_t n = UINT8_MAX;
    benchmark::DoNotOptimize(count_bits(n));
  }
}

BENCHMARK(BM_count_8);
BENCHMARK(BM_count_16);
BENCHMARK(BM_count_32);
BENCHMARK(BM_count_64);

BENCHMARK_MAIN();

下面是使用 MacBook Air (M1, 2020) 和 Apple clang 13.1.6 得到的结果

/Users/hominsu/CLionProjects/bit-hacks-bench/cmake-build-release-appleclang/bench/count_bits
Unable to determine clock rate from sysctl: hw.cpufrequency: No such file or directory
2022-03-27T14:09:30+08:00
Running /Users/hominsu/CLionProjects/bit-hacks-bench/cmake-build-release-appleclang/bench/count_bits
Run on (8 X 24.1205 MHz CPU s)
CPU Caches:
  L1 Data 64 KiB (x8)
  L1 Instruction 128 KiB (x8)
  L2 Unified 4096 KiB (x2)
Load Average: 2.64, 2.22, 1.79
------------------------------------------------------
Benchmark            Time             CPU   Iterations
------------------------------------------------------
BM_count_8       0.319 ns        0.319 ns   1000000000
BM_count_16      0.321 ns        0.321 ns   1000000000
BM_count_32      0.313 ns        0.313 ns   1000000000
BM_count_64      0.316 ns        0.316 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/count_bits
2022-03-27T14:10:07+08:00
Running /tmp/tmp.CtmwmpTLjC/cmake-build-release-1104/bench/count_bits
Run on (6 X 4100.35 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.57, 0.54, 0.51
------------------------------------------------------
Benchmark            Time             CPU   Iterations
------------------------------------------------------
BM_count_8       0.244 ns        0.244 ns   1000000000
BM_count_16      0.246 ns        0.246 ns   1000000000
BM_count_32      0.245 ns        0.244 ns   1000000000
BM_count_64      0.249 ns        0.248 ns   1000000000
文章标签：
C++
C语言
Linux
关键词：
C++位运算
二进制C++
C++二进制
C++位运算黑科技
C++黑科技
HauHau
目录
相关文章
泡沫o0
|
4月前
|
算法 网络协议 编译器
【C++ 14 新特性】C++14二进制字面量：深度探索与实践
【C++ 14 新特性】C++14二进制字面量：深度探索与实践
泡沫o0
85 1
极客李华
|
4月前
|
C++
二进制求和(C++)
二进制求和(C++)
极客李华
48 1
n7lskg6uuowc2
|
3月前
|
编译器 Linux C++
详细解读C++中的位运算总结
详细解读C++中的位运算总结
n7lskg6uuowc2
20 0
什么时候能躺平
|
4月前
|
算法 C++
c++算法学习笔记 (10) 位运算
c++算法学习笔记 (10) 位运算
什么时候能躺平
29 0
yma16
|
4月前
|
C++
十进制二进制相互转化C++
十进制二进制相互转化C++
yma16
16 0
闻缺陷则喜何志丹
|
4月前
|
算法 测试技术 C++
【位运算】【二分查找】【C++算法】100160价值和小于等于 K 的最大数字
【位运算】【二分查找】【C++算法】100160价值和小于等于 K 的最大数字
闻缺陷则喜何志丹
35 2
泡沫o0
|
4月前
|
存储 算法 数据安全/隐私保护
C++ 位运算 std::bitset类的使用介绍
C++ 位运算 std::bitset类的使用介绍
泡沫o0
98 0
HannYang
|
4月前
|
Java Go Python
Golang每日一练(leetDay0103) 区域和检索1~3
Golang每日一练(leetDay0103) 区域和检索1~3
HannYang
50 0
Golang每日一练(leetDay0103) 区域和检索1~3
HannYang
|
4月前
|
算法 Java C++
Java每日一练(20230424) 二叉树中序遍历、交换链表节点、不同子序列
Java每日一练(20230424) 二叉树中序遍历、交换链表节点、不同子序列
HannYang
54 0
Java每日一练(20230424) 二叉树中序遍历、交换链表节点、不同子序列
闻缺陷则喜何志丹
|
4月前
|
算法 测试技术 C#
【位运算】【二分查找】【C++算法】100160价值和小于等于 K 的最大数字
【位运算】【二分查找】【C++算法】100160价值和小于等于 K 的最大数字
闻缺陷则喜何志丹
36 0

热门文章

最新文章

  • 1
    C++模板初阶
  • 2
    C++数组参数应用方式探讨（转）
  • 3
    《C++语言入门经典》一2.10　小结
  • 4
    C++语言基础 例程 案例：一个接口，多种方法
  • 5
    C++第11周项目3（3）——回文数
  • 6
    嵌入式数据库sqlite3【基础篇】基本命令操作，小白一看就懂（C/C++）
  • 7
    C/C++程序员上手C#应该知道的100件事（21~30）
  • 8
    C++ Internals: STL之Map
  • 9
    C++语言基础 例程 类模板
  • 10
    《C++语言基础》实践参考——图书馆的书
  • 1
    C++ new和delete的用法
    68
  • 2
    为什么c++要引入class关键字
    54
  • 3
    【C++】使用g++指令控制【翻译】各个过程
    43
  • 4
    【C++】一文深入浅出带你参透库中的几种 [ 智能指针 ]及其背后实现原理（代码＆图示）
    52
  • 5
    【C++】C++中的【文件IO流】使用指南 [手把手代码演示] ＆ [小白秒懂]
    62
  • 6
    【C++】istream类型对象转换为逻辑条件判断值
    41
  • 7
    【C++】一文全解四种经典 [ 特殊类 ]的设计
    45
  • 8
    【C++】【C++的常变量取地址问题（对比C的不同）】const修饰的常变量＆volatile修饰用法详解（代码演示）
    38
  • 9
    【C++】C++中规范[ 类型转换标准 ] 的四种形式
    45
  • 10
    【C++小小知识点】重载、覆盖(重写)、隐藏(重定义)的对比【详解】（23）
    62

    • 相关课程

    更多
  • C++ 入门教程开发文档

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    通义千问API入门教程