Skip to main content

Perform XNOR of two numbers

The problem at hand involves performing an XNOR operation on two given numbers. An XNOR operation (also known as equivalence operation) takes two binary inputs and produces a single binary output. It returns 1 if both inputs are the same (either both 0 or both 1), and 0 if the inputs are different. In this article, we'll explore the problem statement, understand the concept behind the XNOR operation, provide a step-by-step approach to solving the problem, and analyze the time complexity of the solution.

Problem Statement and Description

The task is to perform the XNOR operation on two given integers, x and y. The goal is to compute the result of x ⊙ y, where represents the XNOR operation.

For example, if x is 12 (binary 1100) and y is 6 (binary 0110), then:

  • The XNOR of the least significant bits is 0 (0 ⊙ 0 = 1).
  • The XNOR of the next bits is 1 (1 ⊙ 1 = 1).
  • The XNOR of the next bits is 1 (0 ⊙ 0 = 1).
  • The XNOR of the most significant bits is 1 (0 ⊙ 0 = 1). So, the result is 0101, which is 5 in decimal.

Another example

7 in binary is 00111 18 in binary is 10010. Now we can perform the XNOR operation on each corresponding bit:

Truth table of XNOR with example

7   00111
18  10010 
------------
1 XNOR 0 = 0
1 XNOR 1 = 1
1 XNOR 0 = 0
0 XNOR 0 = 1
0 XNOR 1 = 0

Therefore, the XNOR of 7 and 18 is 01010 in binary, which is 10 in decimal.

Idea to Solve the Problem

To perform the XNOR operation on two numbers x and y, we can break down the problem into XNOR operations on individual bits of the two numbers. We'll compare the corresponding bits of x and y and compute the XNOR for each pair of bits, resulting in the corresponding bits of the final output.

Pseudocode

Here's a high-level pseudocode for solving the problem:

function setAllBit(num):
    n = num
    n = n | n >> 1
    n = n | n >> 2
    n = n | n >> 4
    n = n | n >> 8
    n = n | n >> 16
    return n

function xnor(x, y):
    result = 0
    if x > y:
        result = (setAllBit(x) ^ x) ^ y
    else:
        result = (setAllBit(y) ^ y) ^ x
    return result

function main():
    task = create ExclusiveNOR object
    task.xnor(12, 6)
    task.xnor(7, 18)
    task.xnor(45, 32)

Algorithm Explanation

  1. The setAllBit function takes an integer num and activates all the bits after the most significant bit, effectively creating a number with all bits set to 1 up to the position of the most significant bit.

  2. The xnor function takes two integers, x and y, and performs the XNOR operation using the setAllBit function.

  3. If x is greater than y, the function computes (setAllBit(x) ^ x) ^ y.

    • setAllBit(x) ensures that all bits up to the most significant bit are set to 1.
    • The first XNOR (^ x) compares setAllBit(x) with x.
    • The second XNOR (^ y) compares the result of the first XNOR with y.
  4. If y is greater than x, the function computes (setAllBit(y) ^ y) ^ x following a similar logic.

  5. The main function creates an ExclusiveNOR object and calls the xnor function for three sets of inputs.

Code Solution

Time Complexity

The setAllBit function runs in O(1) time because it operates on a fixed number of bits, regardless of the input value. The xnor function has a constant number of operations for each input pair, and its time complexity is also O(1). The main function runs the xnor function three times, so its time complexity is still O(1).





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment