JiXiaw

  • 主页
  • 归档
所有文章 友链

  • 主页
  • 归档

c++计算十进制数的位数

阅读数:8575次 2020-11-20
字数统计: 578字   |   阅读时长≈ 2分

总结了计算十进制数的位数的几种方法

一

最常见一种方法就是不断地除以 10 直到为 0.

1
2
3
4
5
6
7
8
9
int GetDigitOfUInt1(uint32_t x) 
{
int res = 0;
while (x) {
res += 1;
x /= 10;
}
return res;
}

每次只除以 10 速度有点慢,可以优化一下每次除以100:

1
2
3
4
5
6
7
8
9
10
11
12
13
int GetDigitOfUInt2(uint32_t x) 
{
int res = 0;
while (x) {
if (x < 10) {
res += 1;
} else {
res += 2;
}
x /= 100;
}
return res;
}

二

第二种方法就是取对数

1
2
3
4
5
int GetDigitOfUInt3(uint32_t x) 
{
if (x == 0) return 0;
return 1 + (int)log10(x);
}

三

由于计算机取10的对数速度很慢,第二种方法速度比第一种慢很多,但是计算机取2的对数很快,只要进行移位操作就可以了,我们就可以通过 2 的对数来计算10的对数,第三种方法就是基于这个思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int GetDigitOfUInt4(uint32_t x)
{
static const int powers_of_10_u32[] = {
0,
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000,
1000000000
};
uint32_t t = (32 - __builtin_clz(x | 1)) * 1233 >> 12;
return t - (x < powers_of_10_u32[t]) + 1;
}

其中__builtin_clz是由gcc提供的计算一个数字前导 0 的个数的函数,(32 - __builtin_clz(x | 1)) 表示 log2x的值. log10x=log2x/log210,
1/log210≈0.301, 12334096≈0.301.

最后比较一下运行时间:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define TEST_FUCTION(func)                      \
do { \
time_t t1, t2; \
uint32_t maxNum = 200000000; \
t1 = GetCurrentMs(); \
for (uint32_t i = 0; i <= maxNum; ++i){ \
func(i); \
} \
t2 = GetCurrentMs(); \
std::cout << t2 - t1<<std::endl; \
} \
while (0);

int main()
{
TEST_FUCTION(GetDigitOfUInt1)
TEST_FUCTION(GetDigitOfUInt2)
TEST_FUCTION(GetDigitOfUInt3)
TEST_FUCTION(GetDigitOfUInt4)
}

输出:

1
2
3
4
3108    // 第一种,每次除以10
1920 // 第一种,每次除以100
6980 // 第二种
714 // 第三种

可以看出用log10计算的是最慢的,第三种方法最快,因为没有除法运算,除法运算是四种运算里最耗时的。

附录: gcc的一些__builtin_函数

__builtin_ffs(x)

返回x中最后一个为1的位是从后向前的第几位

__builtin_popcount(x)

x中1的个数

__builtin_ctz(x)

x末尾0的个数。x=0时结果未定义。

__builtin_clz(x)

x前导0的个数。x=0时结果未定义。

__builtin_parity(x)

x中1的奇偶性。

另外在这些函数名后面加 ll 就可以计算 long long类型对应的结果。

参考:

https://github.com/fmtlib/format-benchmark/blob/cbbe9a485c4a552548c5e2380caa00bad582410a/src/digits10/digits10.h (第三种方法)
https://blog.csdn.net/jasonchen_gbd/article/details/44948523

  • 本文作者: JiXiaw
  • 本文链接: http://jixiaw.github.io/2020/11/20/digitofnum/
  • 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!
  • c++

扫一扫,分享到微信

rapidjosn基本操作
vimdiff以及vim的一个bug
Like Issue Page
Error: Not Found
Login with GitHub
Styling with Markdown is supported
Powered by Gitment
© 2018-2022 JiXiaw
GitHub:hexo-theme-yilia-plus by Litten
本站总访问量9003次 | 本站访客数7377人
  • 所有文章
  • 友链

tag:

  • c++
  • Linux, 多线程
  • git
  • hexo
  • Linux
  • 算法
  • 经验
  • summary
  • c++ rapidjson
  • linux
  • 操作系统

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录(注意不是yilia-plus根目录)执行以下命令:
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置:

      jsonContent:
        meta: false
        pages: false
        posts:
          title: true
          date: true
          path: true
          text: false
          raw: false
          content: false
          slug: false
          updated: false
          comments: false
          link: false
          permalink: false
          excerpt: false
          categories: false
          tags: true
    

  • Raft学习笔记

    2022-03-01

    #操作系统

  • 秋招的一些总结和感想

    2021-09-27

    #经验

  • MIT6.S081学习总结-lab10:mmap

    2021-07-08

    #操作系统

  • MIT6.S081学习总结-lab9:file system

    2021-07-05

    #操作系统

  • MIT6.S081学习总结-lab8:Lock

    2021-07-04

    #操作系统

  • MIT6.S081学习总结-lab7:Multithreading

    2021-06-30

    #操作系统

  • MIT6.S081学习总结-lab6:copy-on-write fork

    2021-06-29

    #操作系统

  • MIT6.S081学习总结-lab5:lazy allocation

    2021-06-27

    #操作系统

  • MIT6.S081学习总结-lab4:traps

    2021-06-24

    #操作系统

  • MIT6.S081学习总结-lab3:page tables

    2021-06-14

    #操作系统

  • MIT6.S081学习总结-lab2:system calls

    2021-06-03

    #操作系统

  • MIT6.S081学习总结-lab1:Xv6 and Unix utilities

    2021-06-02

    #操作系统

  • Linux网络编程之TCP相关

    2021-05-27

    #c++

  • 3月总结

    2021-03-30

    #summary

  • cppquiz系列题目2

    2021-02-26

    #c++

  • 多线程中伪共享问题

    2021-02-19

    #Linux, 多线程

  • c++基础知识

    2021-02-04

    #c++

  • cppquiz系列题目1

    2021-02-04

    #c++

  • rapidjosn基本操作

    2021-02-04

    #c++ rapidjson

  • c++计算十进制数的位数

    2020-11-19

    #c++

  • vimdiff以及vim的一个bug

    2020-10-16

    #linux

  • git 基本操作及开发流程

    2020-10-02

    #git

  • 面试总结

    2020-09-08

    #经验

  • 分数取模

    2020-08-28

    #算法

  • Linux 命令整理

    2020-08-20

    #Linux

  • Hexo搭建博客

    2020-08-18

    #hexo

  • 安装 Ubuntu 、win10 双系统

    2020-08-18

    #Linux

  • CSDN 博客
  • ZQ`s blog