目标
给你两个整数：num1 和 num2 。
在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2^i + num2 。
请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。
如果无法使 num1 等于 0 ，返回 -1 。
示例 1：
输入：num1 = 3, num2 = -2
输出：3
解释：可以执行下述步骤使 3 等于 0 ：
- 选择 i = 2 ，并从 3 减去 2^2 + (-2) ，num1 = 3 - (4 + (-2)) = 1 。
- 选择 i = 2 ，并从 1 减去 2^2 + (-2) ，num1 = 1 - (4 + (-2)) = -1 。
- 选择 i = 0 ，并从 -1 减去 2^0 + (-2) ，num1 = (-1) - (1 + (-2)) = 0 。
可以证明 3 是需要执行的最少操作数。示例 2：
输入：num1 = 5, num2 = 7
输出：-1
解释：可以证明，执行操作无法使 5 等于 0 。说明：
- 1 <= num1 <= 10^9
- -10^9 <= num2 <= 10^9
思路
已知整数 num1 和 num2，每次操作需要从 0 ~ 60 选一个整数 i，并将 num1 -= 2^i + num2，返回将 num1 变为 0 的最小操作次数，如果无法完成返回 -1。
假设最少需要操作 k 次，那么 num1 - k * num2 = 2^i1 + 2^i2 + …… + 2^ik，其中 ik 表示第 k 次选择的 i。
问题转换为 num1 - k * num2 能否用 k 个 2 的幂表示。
二进制中 1 的个数就是最少的 k 的个数，它自身的值就是最多可以拆分的个数 ，也就是说 num = num1 - k * num2 的二进制表示中 1 的个数应小于等于 k 并且 num >= k。
代码
/**
* @date 2025-09-05 8:46
*/
public class MakeTheIntegerZero2749 {
public int makeTheIntegerZero(int num1, int num2) {
for (int i = 0; i < 61; i++) {
long num = num1 - (long) i * num2;
if (num <= 0) {
return -1;
} else if (Long.bitCount(num) <= i && num >= i) {
return i;
}
}
return -1;
}
}
性能
