資料結構
網路
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 次瀏覽
廣告