『位运算』将数字变成 0 的操作次数1342

题目相关

• 原题链接：1342. 将数字变成 0 的操作次数 - 力扣（LeetCode）
• 涉及知识：位运算
• 题目难度：★

题目解读

如果是基本思路的话，则是模拟运算计数即可；如果是通过位运算的话，就比较巧妙了。下面是一些基本的位运算，设当前数为x（x为非负整数）：

• x和1与运算：由于1的二进制码如00001，所以x和1进行与运算的结果就是：1（若x为奇数，即x的二进制码最后一位为1），0（若x为偶数，即x的二进制码最后一位为0）
• x和1异或运算：由于1的二进制码如00001，所以x和1进行抑或运算的结果就是：x-1（若x为奇数，即x的二进制码最后一位为1），x+1（若x为偶数，即x的二进制码最后一位为0）
• x左移一位：x/2 -1（若x为奇数，即x的二进制码最后一位为1），x/2（若x为偶数，即x的二进制码最后一位为0）
  若x不为0，则x的二进制表示为1abcd...，其中abcd等是1或者0，在将x变成0的过程中，对于每一位而言：如果该位是1，那么需要进行一次抑或运算，将该位变成0，然后进行左移运算；如果该位是0，则直接进行左移运算即可。
  所以我们可以发现对于某个确定的x的二进制表示，我们需要进行的抑或运算m和左移运算的次数n也是确定的。不难发现，其中m就等于该二进制表示中1的个数，而n则等于该二进制表示长度-1（因为若x非0，那么x的二进制表示的第一位总是1，而在对后面的各位进行处理了之后，临时结果只剩下一个1，只需要再进行一次异或运算即可将之变为0）。

Python相关

在Python中，我们有如下几种常见位运算：

1. x和1与运算，对应于x & 1，等价于x % 2
2. x和1异或运算，对应于x ^ 1，等价于x - 1（x为奇数）、x + 1（x为偶数）
3. x左移一位，对应于x >> 1，等价于x // 2

具体实现

基本思路：

class Solution:
    def numberOfSteps (self, num: int) -> int:
        count = 0
        while num:
            if num % 2 == 0:
                num = num // 2
            else:
                num -= 1
            count += 1
        return co

位运算：

class Solution:
    def numberOfSteps(self, num: int) -> int:
        tmp = str(bin(num))[2:]
        return len(tmp) - 1 + tmp.count('1')

参考

1. 用位运算处理的思路与代码 - 将数字变成 0 的操作次数 - 力扣（LeetCode）