这道题是 LeetCode 1521，要求找到一个子数组 arr[l...r]，使得这个子数组内所有元素进行按位与（&）运算后的结果，与目标值 target 的绝对差最小。

🤔 核心思路

解决这个问题的关键在于利用按位与运算的一个重要性质：

对于一个固定的右端点 r，当左端点 l 从 r 向左移动（即子数组变长）时，func(arr, l, r) 的值是单调不增的。

这是因为 a & b 的结果只会小于或等于 a 和 b 中的任何一个。随着更多数字参与按位与运算，结果的二进制表示中，1 只会变成 0，而 0 不可能变回 1。

基于这个性质，我们可以得出另一个重要结论：

对于任何一个固定的右端点 r，所有可能的 func(arr, l, r) 的不同结果数量非常少（最多不超过 log₂(max(arr)) 个）。

因为数组中的元素最大为 10⁶，其二进制表示不超过 20 位。所以，对于固定的 r，不同的运算结果最多只有 20 种左右。

💡 算法步骤

我们可以遍历数组，将每个位置 i 作为子数组的右端点，并维护一个集合来存储所有以 i 结尾的子数组可能产生的按位与结果。

1.  初始化: 创建一个集合（例如 HashSet）prevResults 来存储上一轮（以 i-1 结尾）的所有按位与结果。同时，用一个变量 minDiff 记录找到的最小绝对差。
2.  遍历数组: 对于数组中的每一个元素 arr[i]：
    *   创建一个新的集合 currResults 来存储以 arr[i] 结尾的所有可能结果。
    *   将 arr[i] 本身加入 currResults（这对应于子数组 [i, i]）。
    *   遍历 prevResults 中的每一个值 val，计算 val & arr[i]，并将结果加入 currResults。这相当于将以 i-1 结尾的子数组向右扩展一位。
    *   在计算过程中，用每一个新产生的结果去更新 minDiff。
    *   将 currResults 赋值给 prevResults，为下一次迭代做准备。
3.  返回结果: 遍历结束后，minDiff 就是最终答案。

这种方法的时间复杂度为 O(n * log M)，其中 n 是数组长度，M 是数组中的最大值，效率非常高。

💻 Java 代码实现

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int closestToTarget(int[] arr, int target) {
        // 初始化最小差值为第一个元素与target的差
        int minDiff = Math.abs(arr[0] - target);
        
        // prevResults 存储以上一个元素结尾的所有可能的按位与结果
        Set prevResults = new HashSet();
        prevResults.add(arr[0]);

        // 从第二个元素开始遍历，将当前元素作为子数组的右端点
        for (int i = 1; i  currResults = new HashSet();
            
            // 1. 子数组只包含当前元素本身 [i, i]
            currResults.add(currentNum);
            minDiff = Math.min(minDiff, Math.abs(currentNum - target));

            // 2. 将之前所有可能的结果与当前元素进行按位与运算
            // 这相当于将以 i-1 结尾的子数组扩展到 i
            for (int val : prevResults) {
                int newVal = val & currentNum;
                currResults.add(newVal);
                minDiff = Math.min(minDiff, Math.abs(newVal - target));
            }

            // 更新 prevResults，为下一次迭代做准备
            prevResults = currResults;
        }

        return minDiff;
    }
}

这个问题问得非常到位。更准确地说，这个性质是：对于一个固定的右端点，所有可能的按位与结果，其不同值的数量最多不超过 log₂M 个，其中 M 是数组中的最大值。

这个结论的核心在于按位与（&）运算的一个关键特性：结果的单调不增性。

📉 核心原理：单调不增性

当我们固定子数组的右端点，并不断向左扩展左端点时，参与按位与运算的数字会越来越多。在这个过程中，运算结果的二进制表示有一个不可逆的趋势：

*   1 只能变成 0
*   0 永远不能变回 1

这意味着，随着更多数字加入运算，结果的值只会保持不变或变小，绝不会变大。

🔍 为什么不同结果的数量是 log₂M 级别？

我们可以从二进制位的角度来理解。假设数组中的最大值为 M，那么任何一个数字的二进制表示最多有 k = floor(log₂M) + 1 位。

现在，我们固定右端点，从右向左扩展子数组，观察按位与结果的变化：

1.  初始状态：子数组只包含右端点那个数，比如 A[r]。这是第一个结果。
2.  向左扩展：我们将 A[r-1] 加入运算，得到新结果 A[r-1] & A[r]。根据单调不增性，这个新结果要么等于 A[r]，要么比它小。
3.  变化的本质：如果结果变小了，那一定是因为在 A[r] 的二进制表示中，至少有一个为 1 的位，在与 A[r-1] 进行运算后变成了 0。
4.  变化的上限：一个数字最多只有 k 个二进制位。因此，从初始值 A[r] 开始，它的二进制位中的 1 最多只能从 1 变成 0 共 k 次。每一次变化，都会产生一个新的、更小的结果。

所以，从初始值开始，我们最多只能经历 k 次“值的变化”，最终结果会变成 0。这意味着，所有可能产生的不同结果的数量，最多就是 k + 1 个（包括初始值和 0）。

因为 k ≈ log₂M，所以不同结果的数量是 O(log M) 级别的。

💡 举个例子

假设我们有一个数组 [15, 13, 7]，我们固定右端点为最后一个元素 7。15 的二进制是 1111，最多有 4 位，所以不同结果不会超过 4 个。

我们从右向左扩展，观察按位与结果的变化：

1.  子数组 [7]: 结果是 7 (二进制 0111)。
2.  子数组 [13, 7]: 结果是 13 & 7 = 5 (二进制 1101 & 0111 = 0101)。
    *   注意，结果的最后一位从 1 变成了 0。
3.  子数组 [15, 13, 7]: 结果是 15 & 13 & 7 = 5 (二进制 1111 & 1101 & 0111 = 0101)。
    *   结果没有变化。

在这个例子中，以 7 结尾的子数组，其按位与的不同结果只有 {7, 5} 两个。这个过程清晰地展示了结果是如何随着左端点扩展而单调不增，并且由于二进制位的限制，不同结果的数量非常有限。

正是这个 O(log M) 的性质，保证了我们使用 HashSet 来存储中间结果的算法是极其高效的。

你的理解基本正确，但我们可以更精确地表述一下。

log₂M 并不是指“取以2为底的对数”这个运算本身的最大值，而是指运算结果的上限。

更准确地说，log₂M 代表了数组中最大值 M 在二进制表示下所需要的位数（或者说是位数减一，取决于是否包含最高位）。

💡 为什么是 log₂M？

这和计算机底层的二进制存储方式有关：

1.  二进制位数：任何一个整数在计算机中都是以二进制（0和1）存储的。如果一个数是 M，那么它转换成二进制后，大约需要 log₂M 个位（bit）来表示。
    *   例如：M = 8，log₂8 = 3。8 的二进制是 1000（严格说是4位，但在算法复杂度分析中，我们通常关注数量级，所以常简略说成与 log₂M 相关）。
    *   例如：M = 1000，log₂1000 ≈ 9.96。这意味着 1000 用二进制表示大约需要 10 位。

2.  按位与的“消耗”：正如我们之前讨论的，按位与运算只会让二进制位中的 1 变成 0，而不会反过来。
    *   既然 M 最多只有约 log₂M 个二进制位。
    *   那么在这个过程中，1 变成 0 的次数最多也就只有 log₂M 次。
    *   每一次变化都会产生一个新的数值。

总结一下：
log₂M 在这里代表的是“变化的潜力”。因为数值 M 的二进制长度限制在了 log₂M 级别，所以它能产生的不同按位与结果（即数值变化的次数）也就被限制在了这个范围内。

📌 补充小知识：为什么算法里常省略底数？

在算法复杂度分析（比如 O 表示法）中，我们通常直接写 O(log N) 而不写 O(log₂N)。这是因为根据数学上的换底公式，不同底数的对数之间只差一个常数倍数（例如 log₂N 和 log₁₀N 只相差约 3.32 倍）。在分析算法随数据规模增长的趋势时，常数倍数通常被忽略，所以底数是多少就不重要了。但在具体解释“二进制位数”这种物理含义时，底数必须是 2。