【】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()求二进制长度。最终也是一行实现。分页标题
代码如下：

文章图片
文章图片

文章图片
文章图片
Python语言实现：
Python 的实现和C语言的实现一致。
用bin(num)得出num的二进制字符串，然后用count方法求出里面字符1的数量，用len方法求二进制的长度，需要注意的是， bin方法打印的二进制字符串有两个前缀"0b" ，这个我们是要去掉的，所以要多减去2 。
代码如下：

文章图片
文章图片

文章图片
文章图片