# 对于给定数组的任何排列，最大化第一个元素的按位与，并保留其余元素

2021年4月29日18:05:34 发表评论 554 次浏览

## 本文概述

A1 &(~A2) & (~A3) & ……& (~An)

• 表达方式一种1＆(〜A2)＆(〜A3)＆……＆(〜Añ)完全取决于A的值1.
• 因此, 要从表达式中获得最大值, 请选择A1这样它有设置位具有尽可能高的重要性, 而在所有其他数组元素中未设置。
• 由于剩余数组元素的顺序无关紧要, 请打印具有获得的A的任何排列1作为第一个元素。

(16)10 =(10000)2
(8)10 =(01000)2
(4)10 =(00100) )2
(2)10 =(00010)2
(1)10 =(00001)2

## C ++

``````//C++ Program to implement
//the above approach
#include <bits/stdc++.h>
using namespace std;

#define size_int 32

//Function to maximize the value for
//the given function and the array elements
int functionMax( int arr[], int n)
{
//Vector array to maintain which bit is set
//for which integer in the given array by
//saving index of that integer
vector<int> setBit[32];

for ( int i = 0; i <n; i++) {
for ( int j = 0; j <size_int; j++) {

//Check if j-th bit is set for
//i-th integer
if (arr[i] & (1 <<j))

//Push the index of that
//integer in setBit[j]
setBit[j].push_back(i);
}
}

//Find the element having
//highest significant set bit
//unset in other elements
for ( int i = size_int; i>= 0; i--) {
if (setBit[i].size() == 1) {

//Place that integer at 0-th index
swap(arr[0], arr[setBit[i][0]]);
break ;
}
}

//Store the maximum AND value
int maxAnd = arr[0];
for ( int i = 1; i <n; i++) {
maxAnd = maxAnd & (~arr[i]);
}

return maxAnd;
}

//Driver Code
int main()
{

int arr[] = { 1, 2, 4, 8, 16 };
int n = sizeof arr /sizeof arr[0];

//Function call
cout <<functionMax(arr, n);

return 0;
}``````

## Java

``````//Java Program to implement
//the above approach
import java.util.*;
class GFG{

static final int size_int = 32 ;

//Function to maximize the value for
//the given function and the array elements
static int functionMax( int arr[], int n)
{
//Vector array to maintain which bit is set
//for which integer in the given array by
//saving index of that integer
Vector<Integer> []setBit = new Vector[ 32 + 1 ];
for ( int i = 0 ; i <setBit.length; i++)
setBit[i] = new Vector<Integer>();
for ( int i = 0 ; i <n; i++)
{
for ( int j = 0 ; j <size_int; j++)
{

//Check if j-th bit is set for
//i-th integer
if ((arr[i] & ( 1 <<j))> 0 )

//Push the index of that
//integer in setBit[j]
}
}

//Find the element having
//highest significant set bit
//unset in other elements
for ( int i = size_int; i>= 0 ; i--)
{
if (setBit[i].size() == 1 )
{

//Place that integer at 0-th index
swap(arr, 0 , setBit[i].get( 0 ));
break ;
}
}

//Store the maximum AND value
int maxAnd = arr[ 0 ];
for ( int i = 1 ; i <n; i++)
{
maxAnd = maxAnd & (~arr[i]);
}

return maxAnd;
}

static int [] swap( int []arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}

//Driver Code
public static void main(String[] args)
{

int arr[] = { 1 , 2 , 4 , 8 , 16 };
int n = arr.length;

//Function call
System.out.print(functionMax(arr, n));
}
}

//This code is contributed by PrinciRaj1992``````

## Python3

``````# Python 3 Program to
# implement the above approach

# Function to maximize the
# value for the given function
# and the array elements
def functionMax(arr, n):

# Vector array to maintain
# which bit is set for which
# integer in the given array by
# saving index of that integer
setBit = [[] for i in range ( 32 )]

for i in range (n):
for j in range ( 32 ):

# Check if j-th bit is
# set for i-th integer
if (arr[i] & ( 1 <<j)):

# Push the index of that
# integer in setBit[j]
setBit[j].append(i)

# Find the element having
# highest significant set bit
# unset in other elements
i = 31

while (i> = 0 ):
if ( len (setBit[i]) = = 1 ):

# Place that integer
# at 0-th index
temp = arr[ 0 ]
arr[ 0 ] = arr[setBit[i][ 0 ]]
arr[setBit[i][ 0 ]] = temp
break
i - = 1

# Store the maximum
# AND value
maxAnd = arr[ 0 ]
for i in range ( 1 , n, 1 ):
maxAnd = (maxAnd & (~arr[i]))

return maxAnd

# Driver Code
if __name__ = = '__main__' :
arr = [ 1 , 2 , 4 , 8 , 16 ]
n = len (arr)

# Function call
print (functionMax(arr, n))

# This code is contributed by bgangwar59``````

## C#

``````//C# Program to implement
//the above approach
using System;
using System.Collections.Generic;

class GFG{

static readonly int size_int = 32;

//Function to maximize the value for
//the given function and the array elements
static int functionMax( int []arr, int n)
{
//List array to maintain which bit is set
//for which integer in the given array by
//saving index of that integer
List<int> []setBit = new List<int>[32 + 1];
for ( int i = 0; i <setBit.Length; i++)
setBit[i] = new List<int>();
for ( int i = 0; i <n; i++)
{
for ( int j = 0; j <size_int; j++)
{

//Check if j-th bit is set for
//i-th integer
if ((arr[i] & (1 <<j))> 0)

//Push the index of that
//integer in setBit[j]
}
}

//Find the element having
//highest significant set bit
//unset in other elements
for ( int i = size_int; i>= 0; i--)
{
if (setBit[i].Count == 1)
{

//Place that integer at 0-th index
swap(arr, 0, setBit[i][0]);
break ;
}
}

//Store the maximum AND value
int maxAnd = arr[0];
for ( int i = 1; i <n; i++)
{
maxAnd = maxAnd & (~arr[i]);
}

return maxAnd;
}

static int [] swap( int []arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}

//Driver Code
public static void Main(String[] args)
{

int []arr = { 1, 2, 4, 8, 16 };
int n = arr.Length;

//Function call
Console.Write(functionMax(arr, n));
}
}

//This code is contributed by Rajput-Ji``````

``16``

O(N * sizeof(int)), 其中sizeof(int)为32