In this article, we have explored the idea of making comparisons (equal, larger, smaller) through bitwise operations along with the basic idea of bitwise operations and their examples.

Table of content:

1. What are Bitwise Operations?
2. Using bitwise operations to compare two operands
   (a) Check if both operands are equal
   (b) Check which operand is smaller/ larger in value
3. Time and Space Complexity

We will get started now.

What are Bitwise Operations?

In a computer setting, a bitwise operation is an operation that operates on the lowest possible level on a bit array, bit string or a bit integer at the level of its individual bits (0 or 1).

It is a considerably simple, efficient and fast operation that is directly supported by the processor since it is an on-chip operation.

Bitwise operations are usually two-operand instructions, meaning that they require at least two operands/variables/values as input in order to produce the correct output.

Some of the commonly used Bitwise Operators are as follows:

Bitwise NOT (~)

NOT is a unary operator (single operand) that complements/negates/inverses the value of each individual bit of the operand.

X	~X
0	1
1	0

Bitwise AND (&)

AND is a binary operator that compares the individual bits of two operands and outputs 1 if and only if both of the bits are 1, else the output will be 0.

X	Y	X & Y
0	0	0
0	1	0
1	0	0
1	1	1

Bitwise OR (|)

OR is a binary operator that compares the individual bits of two operands and outputs 1 if either of the bits being compared is 1, else the output will be 0.

X	Y	X │ Y
0	0	0
0	1	1
1	0	1
1	1	1

Bitwise XOR (^)

XOR is a binary operator that compares the individual bits of two operands and outputs 1 if the bits being compared are different, else the output will be 0.

X	Y	X ^ Y
0	0	0
0	1	1
1	0	1
1	1	0

Using bitwise operations to compare two operands

What if you have two compare two operands without using the comparison operator directly?

Well, worry not, as most of these comparisons can be performed even without the use of the comparison operator.

We will be comparing two operands to check for the following cases:
(a) Check if both operands are equal
(b) Check which operand is smaller/larger in value

(a) Check if both operands are equal

We can check if two given values are equal or not by making use of the XOR operator. If two numbers are equal, then their bitwise XOR will always result in 0.

For example:
In decimal form, a = 9 & b = 9
In binary form, a = 1001 & b = 1001
a ^ b = 1001 ^ 1001
a ^ b = 0000
a ^ b = 0 (in decimal form)
Therefore, a = b.

Let's have a look at a working example in python language.

def bitCheckEqual(x, y):
    return True if not x ^ y else False
    
print(bitCheckEqual(16, 61))

The above code generates the following output.

False

The code is very simple and does what it is supposed to do, however, keep in mind that you can only share integer values to the bitCheckEqual() function, else you will encounter an error as bitwise operations are generally supported for whole integer values only.

(b) Check which operand is smaller/larger in value

We can also check which value is smaller/larger between the two given values by making use of bitwise operators. We can do that by performing the following steps:

1. Use the XOR operator on both the given values to find out the bits that differ among them.
2. Now we have to determine the most significant bits (MSB) that differ (MSBs are the bits that are present at the left-most side of a given number). This can be done by using the bitwise OR bitwise and Right Shift operators.
3. Perform a check to see as to which value does the MSB belong to.
   Depending upon this check, return the final answer. If a value does not contain the MSB, then it is the smaller value and we can simply return it, else return the other value as there is no other alternative. This operation can be performed by using the bitwise AND and bitwise XOR operators.

For example:
In decimal form, a = 9 & b = 5
In binary form, a = 1001 & b = 101
Let MSB = a ^ b
MSB = 1001 ^ 101
∴ MSB = 1100
It is clear that the bits differ at two places.
Now let us determine the first MSB bit.
MSB = MSB | (MSB >> 1)
MSB = 1100 | (1100 >> 1)
MSB = 1100 | 110
MSB = 1110
∴ MSB = 14 (in decimal form)

We will repeat the same steps and update the value by which we are performing the right shift on MSB by 2, 4, 8 and 16.
Performing these steps, we get the final value of MSB as 1111 (in binary) and 15 (in decimal).

Now we have to reduce the value of MSB by right shifting MSB by 1 and then subtracting it from itself.

Now, MSB = MSB - (MSB >> 1)
MSB = 1111 - (1111 >> 1)
MSB = 1111 - 111
MSB = 1000
∴ MSB = 8 (in decimal form)

Now perform the bitwise AND operation between any of the two given values with MSB and then perform XOR of that value with MSB. Depending upon the value that comes out from this operation, return the final answer to the user.
For the sake of our example, let us perform the AND operation between MSB and y and then use XOR between that value and MSB itself.

(b & MSB) ^ MSB
(101 & 1000) ^ 1000
0 ^ 1000
1000 = 8 (in decimal form)

Since the value is not 0, that means that b is the smaller value of the two, so we can simply return b as our final answer.
To find out the larger value of the two, we can simply flip the condition and return the value of a here.

Let's have a look at a working example for finding out the smaller element in python language.

def bitCheckLess(x, y):
    msb = x ^ y
    msb |= (msb >> 1)
    msb |= (msb >> 2)
    msb |= (msb >> 4)
    msb |= (msb >> 8)
    msb |= (msb >> 16)
    msb = msb - (msb >> 1)
    return x if (not((y & msb) ^ msb)) else y
    
    
print(bitCheckLess(9, 5))

The above code generates the following output.

5

For finding the larger value, the code will be similar except for the if condition part. Here is an example of the same.

def bitCheckLarge(x, y):
    msb = x ^ y
    msb |= (msb >> 1)
    msb |= (msb >> 2)
    msb |= (msb >> 4)
    msb |= (msb >> 8)
    msb |= (msb >> 16)
    msb = msb - (msb >> 1)
    return x if ((y & msb) ^ msb) else y
    
    
print(bitCheckLarge(12314, 12315))

The above code generates the following output.

12315

Once again, both the codes do what they are supposed to do, albeit they use considerably more operations than our previous algorithm. Keep in mind that you can only share integer values to the bitCheckLess() and bitCheckLarge() functions, else you will encounter an error as bitwise operations are generally supported for whole integer values only.

Time and Space Complexity

Time complexity: The comparisons being performed in the comparison function actually depends upon the number of bits that the input number has. Although bitwise operations are considerably faster, this would make the overall time complexity of our algorithm to be O(n), where n = number of bits in the input number.

Space complexity: No extra space is being used other than the msb variable, hence the overall space complexity of our algorithm will be O(1).

With this article at OpenGenus, you must have the complete idea of Comparison using bitwise operations.