博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
后面有多少个零
阅读量:6256 次
发布时间:2019-06-22

本文共 622 字,大约阅读时间需要 2 分钟。

1. 阶乘($n!$)后面有多少个零

如果用1连续乘到$n$,再判断有多少个0,可以明显看到的是乘积很快溢出了。优化一点的方法,每乘多一个数都判断有多少个0,再将乘积后面的0删除,即便是这样,乘积也很就溢出。所以这两种方法在n比较大时,无法使用,我们必须要有一种算法避免溢出。

由于$n!$中含有质因子2的个数肯定比含有质因子5的个数要多,由因式分解可以得到:

$$n!=c2^a5^b=c2^{a-b}10^b$$则$n!$后面有b个零,与$n!$含有质因子5的个数相等,那么我们求出$n!$含有多少个质因子5就可以了,代码如下:

uint32_t CountZone(uint32_t n){    uint32_t count = 0;    while (n)    {        n /= 5;        count += n;    }    return count;}

2.判断一个数是否是2的n次幂:

0 == n&(n-1)

3. 判断一个数有多少个1

由第2点可以看到运算一次n&(n-1)就会少一个1,那么一个数有多少个1就会运算多少次n&(n-1),代码如下:

uint32_t CountOne(uint32_t n){    uint32_t count = 0;    while (n) {        count++;        n &= n-1;    }    return count;}

转载地址:http://rqnsa.baihongyu.com/

你可能感兴趣的文章
[转]Oracle 清除incident和trace -- ADRCI用法
查看>>
农产品期货普遍回调 短期压力仍较大
查看>>
数据之路 Day8 Matplotlib包
查看>>
Ye.云狐J2刷机笔记 | 完美切换内部存储卡和SD卡的改法.vold.fstab
查看>>
【转】WIFI基本知识整理
查看>>
普通GRE 隧道配置
查看>>
Vim编程常用命令
查看>>
【树莓派】RASPBIAN镜像初始化配置
查看>>
在按钮上添加倒计时激活功能(转自手册网)
查看>>
java过滤敏感词汇
查看>>
类似LIS+贪心(ZOJ1025)
查看>>
[C++再学习系列] 虚函数的4条规则
查看>>
Thread.sleep
查看>>
浅析 ThreadLocal
查看>>
Pycharm批量操作代码快捷键
查看>>
oracle备份与恢复
查看>>
LLDB调试器
查看>>
cordova Ionic 和cordova的区别是什么
查看>>
【ZZ】C 语言中的指针和内存泄漏 & 编写高效的C程序与C代码优化
查看>>
linux暂停一个在运行中的进程【转】
查看>>