Leetcode每日一练--20
给你两个整数：num1 和 num2 。
在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2i + num2 。
请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。
如果无法使 num1 等于 0 ，返回 -1 。
示例 1：
输入：num1 = 3, num2 = -2 输出：3 解释：可以执行下述步骤使 3 等于 0 ： - 选择 i = 2 ，并从 3 减去 22 + (-2) ，num1 = 3 - (4 + (-2)) = 1 。 - 选择 i = 2 ，并从 1 减去 22 + (-2) ，num1 = 1 - (4 + (-2)) = -1 。 - 选择 i = 0 ，并从 -1 减去 20 + (-2) ，num1 = (-1) - (1 + (-2)) = 0 。 可以证明 3 是需要执行的最少操作数。
示例 2：
输入：num1 = 5, num2 = 7 输出：-1 解释：可以证明，执行操作无法使 5 等于 0 。
提示：
1 <= num1 <= 10^9-10^9 <= num2 <= 10^9
代码
#include <stdint.h>int popcountll(uint64_t x) {if (x == 0) return 0;int count = 0;while (x) {count++;x &= x - 1;}return count;
}int makeTheIntegerZero(int num1, int num2) {if (num1 == 0) return 0;// 扩展枚举范围至100（覆盖极端情况）for (int k = 1; k <= 100; k++) {// 使用64位防溢出计算int64_t S = (int64_t)num1 - (int64_t)k * num2;// 核心修复：严格检查S >= k（每个2^i至少贡献1）if (S < k) {if (num2 > 0) return -1; // num2>0时S递减continue; // num2<=0时S可能增大}// 计算二进制中1的个数int cnt = popcountll((uint64_t)S);// 充要条件：k >= cntif (k >= cnt) {return k;}}return -1;
}