Maximum AND of Two Elements in an Array
Bit manipulation and bitwise operators are some of the hardest problems in programming interviews. This post discusses an interesting bit manipulation problem. The problem was asked by Salesforce.
Problem:
Given an array, find the maximum AND value generated by any pair of element from the array.
Examples:
Input : arr[] = {4, 8, 12, 16}
Output : Maximum AND value = 8 Input : arr[] = {4, 8, 16, 2}
Output : Maximum AND value = 0
(Recall that & is a bitwise AND operator in C++).
Solution 1: Naive approach
Recall the truth table of the logical AND operator
The AND of two bits is one if and only if both bits are one
The logical AND operator on integers (& operator in C++) works bitwise - it performs AND on every pair of corresponding bits on the two numbers.
Let’s work on an example. Consider two 8-bit integers: 8 = 00001000, and 12 = 00001100. The most significant digits (MSB) of the two integers are both zero. As a result, the MSB of the AND of the two is also zero. Extending to other bits, we get 8 & 12 = 8.
