【】LeetCode基础算法题第181篇：将数字减少为零的步骤数
技术提高是一个循序渐进的过程 ， 所以我讲的leetcode算法题从最简单的level开始写的 ， 然后到中级难度 ， 最后到hard难度全部完 。目前我选择C语言 ， Python和Java作为实现语言 ， 因为这三种语言还是比较典型的 。由于篇幅和精力有限 ， 其他语言的实现有兴趣的朋友请自己尝试 。
LeetCode 1342. 将数字减少为零的步骤数（Number of Steps to Reduce a Number to Zero）
问题描述：
给定一个非负整数num ， 返回将其减少为零的步骤数 。如果当前数为偶数 ， 则必须将其除以2 ， 否则 ， 必须从中减去1 。
注:
0 示例：
【【】LeetCode基础算法题第181篇：将数字减少为零的步骤数】
文章图片
文章图片
C语言实现：
这个题目大家第一个想到的一定是按部就班的弄一个for循环 ， 判断num是奇数还是偶数 ， 奇数减1 ， 偶数除而 ， 返回循环的次数 。
这是传统的思路 。我们今天来换一个角度思考一下 。
首先数字不断的除2 ， 我想到的是二进制的右移操作 。对于二进制形式来说 ， 如果一个数是偶数 ， 那么它二进制形式的最右边一定是0 ， 反之一定是1 ， 注意这里 ， 很重要 ， 请先记住 。
按照题目所说 ， 如果偶数就除以2 ， 那就相当于右移动一位 ， 如果是奇数就减一 ， 那么是不是表明数二进制形式有多少1就要减多少次呢？
而要变成0 ， 就要不断的右移 ， 移动多少次？是不是二进制的长度决定的 。
那么最终的结果要处理多少次 ， 就应该是：二进制中1的数量+二进制的长度-1 。
为什么要减1 ， 因为右移到二进制形式的最左边的1 ， 被重复计算了一次：计算1数量的时候计算了一次 ， 最后右移动到1的时候又计算了一次 。
这个算法并不复杂 ， 不理解的跟着例子慢慢琢磨就明白了 。举一个例子：
假设num = 1234 ， 那么它的二进制形式就是"10011010010"
右移 ， 即除以2 ， 得到617 ，二进制："1001101001"
617是奇数 ， 要减1 ， 得616 ， 二进制："1001101000"
右移 ， 得到308 ，二进制："100110100"
右移 ， 得到154 ，二进制："10011010"
右移 ， 得到77 ，二进制："1001101"
77是奇数 ， 减1 ， 得76 ，二进制："1001100"
右移 ， 得到38 ，二进制："100110"
右移 ， 得到19 ，二进制："10011"
19是奇数 ， 减1 ， 得18 ，二进制："10010"
右移 ， 得到9 ，二进制："1001"
9是奇数 ， 减1 ， 得8 ，二进制："1000"
右移 ， 得到4 ，二进制："100"
右移 ， 得到2 ，二进制："10"
右移 ， 得到1 ，二进制："1"
1是奇数 ， 减1 ， 得0 ，二进制："0"
对于C语言来说 ， 我们用gun内置函数__builtin_popcount可以很方便的计算出1的数量 ， 而二进制的长度可以用32-__builtin_clz(num)来实现 ， __builtin_clz是求num前导0的数量 ， 这么一减 ， 就是二进制的长度 。
所以最终我们一行代码就可以搞定 。
代码如下：
文章图片
文章图片 
文章图片
文章图片
Java语言实现：
Java 的实现和C语言的实现一致 。
我们用Integer.bitCount方法求1的数量 ， 用Integer.toBinaryString(num).length()求二进制长度 。最终也是一行实现 。
推荐阅读
- CSDN|基础软件，未来只有开源一条路？
- 大哥大短讯|华为智慧屏解密之基础电视能力
- 太平洋电脑网|麻省理工学院开发海洋搜救算法有寻找失踪物体和人员
- 小小摄影生|摄影初学必须搞懂的基础知识，打好基础是成功的关键
- 店铺|乐到家科技：拼多多店铺有哪些产品不具备基础销量推广？1、低客单价产品2、具备自身优势3、新店产品
- 我不是琪琪|iPad 可以用来做什么？
- BitCherryBCHC价值载体|BitCherry基于IPV8技术可扩容区块链基础设施
- 「」继中兴华为之后，中国第三大电信基础设施崛起，首次冲进全球前十
- 「数字」全国政协委员丁磊：推动编程教育纳入我国基础教学体系
- 「」共建数据基础设施，开启智能世界之眼