Readme

3806.Maximum-Bitwise-AND-After-Increment-Operations

因为bitwise AND的性质是数越多结果反而越小。要想最终结果最大，显然需要在尽量高的bit位置上，令所有数组元素在该处的bit值都是1.

于是我们就有显然的贪心策略：优先探索能否把所有元素的最高（即第30号）bit位都变成1（注意：整型的第31号bit位是符号位），也就是将“100...0”定为目标值target。我们可以计算将所有元素都变成target的超集（即使得target & num == target）所需要的最少操作数，如果成功，那么实现该效果的所有操作是必须保留的。因为不做这些操作，bitwise AND的第30号位就不是1，结果不可能更优。

接下来在此基础上，我们自然就会考察下一个位置：能否把所有元素的第29号bit位都变成1。如果前一步的尝试是成功的，此时就将“110...0”定为目标值；如果前一步不能实现，此时就将“010...0”定为目标值。同样，我们可以计算出所有元素变成该target的超集所需要的最少操作数，以及是否能实现。

以此类推，我们可以找到最优且可行的target，使得所有数组元素可以在指定的操作范围内，都变成target的超集。自然最终的bitwise AND的结果也就是target。

想到这里，我们需要处理的一个子问题就是，对于一个数num，需要最少增加多少，才能使得target & num == target？我们只需要从最高位往低逐位找到第一个位置p，使得target的第p位是1，但是num的第p位是0。此时说明“num的后p位后缀”比“target的后p位后缀”小，二者之间的差值就是我们需要最少的对num的增1操作数量，使得num的bit 1位置与target能够恰好对齐。