位运算，LeetCode 2749. 得到整数零需要执行的最少操作数

一、题目

1、题目描述

给你两个整数：num1 和 num2 。

在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2i + num2 。

请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。

如果无法使 num1 等于 0 ，返回 -1 。

2、接口描述

​

class Solution {
public:
    int makeTheIntegerZero(int num1, int num2) {
        
    }
};

3、原题链接

2749. 得到整数零需要执行的最少操作数

二、解题报告

1、思路分析

假设操作了k次，那么原问题可以转化为num1 - num2 * k能否表示为k个2的幂

我们设m = num1 - num2 * k，那么当k满足如下条件时候可以满足

popcount(m) <= k <= m

下限即m二进制位1的个数， 上限即m个2^0

我们考虑从小到大枚举i

如果num2为正数，那么当i增大，那么m越小，所以我们从1开始枚举，当i > x - i * y时候就退出循环，否则当i >= popcount(m)就返回

如果num2为负数，那么i增大，m增大，显然比i增大的快，退出循环条件仍为i > x - i * y，然后就是如果i初始时小于下界，是否一定能在较小的循环次数内追上下界

popcount(m)为log级增长，i为线性增长，所以一定能追上，考虑函数交点，对于本题数据而言，最坏情况下三十多次就得到答案了

2、复杂度

时间复杂度： O(f(num1 + |num2|))，其中f为2^x/x的反函数空间复杂度：O(1)

3、代码详解

​

class Solution {
public:
    int makeTheIntegerZero(long long x, long long y) {
        for(int i = 1; i <= x -  i * y; i++)
            if(__builtin_popcountll(x - i * y) <= i) 
                return i;
        return -1;
    }
};