数组元素大小计算公式（给定一个非负数组成的数组）

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 main import "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)