Find the maximum XOR of two numbers in an array in Java

Problem statement

Construct a number using alternate bits from two integers. We create a number using the first bit of the second number, the second bit of the first number, the third bit of a second number, the fourth bit of a first number, and so on.

Example 1:

  • Input: x=8,y=10
  • Output: 8

Example 2:

  • Input: x=34,y=43
  • Output: 35

Algorithm

Looking at the pattern mentioned above:

  1. Get the set of even bits number of x.
  2. Get the set of odd bits number of y.
  3. Perform a bitwise OR of the result from steps 1 and 2.

The reference to obtain the odd/even positions of bits are as follows:

Code example

Let’s look at the code below:

class Main{
    static int setEvenPositionBits(int x) {
        int temp = x;
        int count = 0;
        int res = 0;
        for (temp = x; temp > 0; temp >>= 1) {
            if (count % 2 == 1)
                res |= (1 << count);
            count++;
        }
        return (x & res);
    }
    static int setOddPositionBits(int y) {
        int count = 0;
        int res = 0;
        for (int temp = y; temp > 0; temp >>= 1) {
            if (count % 2 == 0)
                res |= (1 << count);
            count++;
        }
        return (y & res);
    }
    static int getAlternateBits(int x, int y) {
        int tempX = setEvenPositionBits(x);
        int tempY = setOddPositionBits(y);
        return tempX | tempY;
    }
    public static void main(String[] args) {
        int x = 34;
        int y = 43;
        System.out.println(getAlternateBits(x, y));
    }
}

Code explanation

  • Lines 3–13: We obtain the set of all even position bits of a number.
  • Lines 15–24: We obtain the set of all even position bits of a number.
  • Lines 26–30: We define the getAlternateBits() method that invokes setOddPositionBits() and setEvenPositionBits() methods and performs a bitwise OR operation on the return values of the methods.
  • Line 33: The x is defined.
  • Line 34: The y is defined.
  • Line 35: We invoke the getAlternateBits() method.
Free AI Mock Interviews
Coding Interview
Coding PatternsFree Interview
Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
System Design
You TubeFree Interview
Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

License: Creative Commons-Attribution NonCommercial-ShareAlike 4.0 (CC-BY-NC-SA 4.0)