数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中数组中一对的最大按位 AND 值
问题表述
给定一个包含 n 个正元素的数组。我们需要找到该数组中任意两个元素生成的最大的按位 AND 值。
示例
如果输入数组为 {10, 12, 15, 18}，则最大的按位 AND 值为 12。
算法
当两个位都是 1 时，对单个位的按位 AND 操作的结果最大。考虑该属性 -
- 从最高有效位开始，检查数组中是否有至少两个元素的值为 1
- 如果存在，则该最高有效位将成为我们解决方案的一部分并被添加到结果中，否则我们将丢弃该位
- 类似地，从最高有效位到最低有效位（32 至 1）对位值进行迭代，我们可以轻松检查哪些位将成为我们解决方案的一部分，并且将继续将所有这些位添加到我们的解决方案中
示例
让我们现在看一个示例 -
#include <bits/stdc++.h>
using namespace std;
int checkBits(int *arr, int n, int pattern) {
int cnt = 0;
for (int i = 0; i < n; ++i) {
if ((pattern & arr[i]) == pattern) {
++cnt;
}
}
return cnt;
}
int getMaxBitwiseAnd(int *arr, int n) {
int result = 0;
int count;
for (int i = 31; i >= 0; --i) {
count = checkBits(arr, n, result | (1 << i));
if (count >= 2) {
result |= (1 << i);
}
}
return result;
}
int main() {
int arr[] = {10, 12, 15, 18};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum bitwise AND = " << getMaxBitwiseAnd(arr, n) << endl;
return 0;
}输出
Maximum bitwise AND = 12
更新于： 31-12-2019
556 次浏览
广告