2021-05-19：給定一個非負陣列成的陣列，長度一定大於1，想知道陣列中哪兩個數&的結果最大。返回這個最大結果。時間複雜度O(N)，額外空間複雜度O(1)。

福大大 答案2021-05-19：

因為是正數，所以不用考慮符號位(31位)

首先來到30位，假設剩餘的數字有N個(整體)，看看這一位是1的數，有幾個

如果有0個、或者1個

說明不管怎麼在陣列中選擇，任何兩個數&的結果在第30位上都不可能有1了

答案在第30位上的狀態一定是0，

保留剩餘的N個數，繼續考察第29位，誰也不淘汰(因為誰也不行，乾脆接受30位上沒有1的事實)

如果有2個，

說明答案就是這兩個數(直接返回答案)，因為別的數在第30位都沒有1，就這兩個數有。

如果有>2個，比如K個

說明答案一定只用在這K個數中去選擇某兩個數，因為別的數在第30位都沒有1，就這K個數有。

答案在第30位上的狀態一定是1，

只把這K個數作為剩餘的數，繼續考察第29位，其他數都淘汰掉

.....

現在來到i位，假設剩餘的數字有M個，看看這一位是1的數，有幾個

如果有0個、或者1個

說明不管怎麼在M個數中選擇，任何兩個數&的結果在第i位上都不可能有1了

答案在第i位上的狀態一定是0，

保留剩餘的M個數，繼續考察第i-1位

如果有2個，

說明答案就是這兩個數(直接返回答案)，因為別的數在第i位都沒有1，就這兩個數有。

如果有>2個，比如K個

說明答案一定只用在這K個數中去選擇某兩個數，因為別的數在第i位都沒有1，就這K個數有。

答案在第i位上的狀態一定是1，

只把這K個數作為剩餘的數，繼續考察第i-1位，其他數都淘汰掉。

程式碼用golang編寫。程式碼如下：

package mainimport "fmt"func main() {    arr := []int{1, 2, 3, 4, 5}    ret := maxAndValue2(arr)    fmt.Println(ret)}func maxAndValue2(arr []int) int {    // arr[0...M-1]  arr[M....]    M := len(arr)    ans := 0    for bit := 62; bit >= 0; bit-- {        // arr[0...M-1] arr[M...]        i := 0        tmp := M        for i < M { // arr[0...M-1]            if (arr[i] & (1 << bit)) == 0 {                M--                arr[i], arr[M] = arr[M], arr[i]            } else {                i++            }        }        if M == 2 { // arr[0,1]            return arr[0] & arr[1]        }        if M < 2 {            M = tmp        } else { // > 2個數  bit位上有1            ans |= 1 << bit        }    }    return ans}

執行結果如下：

***

[左神java程式碼](https://gitee.com/moonfdd/coding-for-great-offer/blob/main/src/class07/Code01_MaxAndValue.java)