LC 1521. 找到最接近目标值的函数值

https://leetcode-cn.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/

这题有点类似"使用双指针寻找子数组之和等于某个值"的问题

`func(arr, l, r)` 的值是单调递减的，因为 `&` 操作会将更多的为设置成为0
所以一旦 `func(arr, l, r) < target` 的话，那么我们应该立刻从左边开始排除元素
然后就涉及一个问题是，如何根据 `func(arr, l, r)` 的值，计算出 `func(arr, l+1, r)` 的值

这个问题我们只需要记录 `arr[l..r]` 上所有的bits数值就可以还原

t = func(arr, l, r)
t[i] = 1 if bits[i] == (r-l+1)
t[i] = 0 if bits[i] != (r-l+1)

class Solution:
    def closestToTarget(self, arr: List[int], target: int) -> int:

        n = len(arr)

        def getBits(x):
            bits = [0] * 32
            for i in range(32):
                if (x >> i) & 0x1:
                    bits[i] += 1
            return bits

        def addBits(x, y):
            for i in range(32):
                x[i] += y[i]

        def subBits(x, y):
            for i in range(32):
                x[i] -= y[i]

        def cons(bits, size):
            t = 0
            for i in range(32):
                if bits[i] == size:
                    t |= (1 << i)
            return t

        BITS = [0] * 32
        t = arr[0]
        j = 0
        ans = 1 << 30
        for i in range(n):
            x = arr[i]

            t = t & x
            bits = getBits(x)
            addBits(BITS, bits)

            # print(t)
            ans = min(ans, abs(t - target))

            if t < target:
                while j < i and t < target:
                    y = arr[j]
                    bits = getBits(y)
                    subBits(BITS, bits)
                    t = cons(BITS, i - j)
                    # print(t)
                    ans = min(ans, abs(t - target))
                    j += 1

        return ans