How to Find the Larger Number Without Conditional Operators Part 1 (Using Bitwise Operators)

Given two (2) signed integer numbers, A and B, where:

• size = ( Integer size int = 4 bytes* = 32 bits ) - 1
• -2^size ≤ A ≤ 2^size-1, and
• -2^size ≤ B ≤ 2^size-1

* May differ on other machines or programming languages

Find the larger number between variables A and B, without using conditional operators. Provide a solution to the following:

1. Assign 0 to X, if A = B, or assign the larger number between A and B
2. Assign the larger number between A and B to Y, or assign either A or B, if A = B

Let us start by abstracting the following idea:

• (a) Show A, if A > B 
• (b) Show B, if B > A 
• (c) Show 0, if A = B

Observe items (a) and (b) and ask, what would it take to know whether A > B or B > A, without using conditional operators? The answer is to get the difference.

• (d) If A > B then A - B is (+positive), if A < B, then A - B is (-negative).

We need to find a solution where we want to show the value of A, if A > B. You can do this by multiplying A with 1 if A > B and zero (0) otherwise.

• (e) (1 or 0) * A

Now, the challenge is to find a similar solution to (e) that will emulate 0 if A < B, and 1 if A > B, using what we know from (d). 

In college, we know that programming languages use 2's complement to implement signed integers, thus one solution is to shift right the bits with size of integer x 8 - 1 times, to the right. Doing this will result negative integers to 0xffff (-1), and positive integers will result to 0x0000 (zero), hence we can write:

• (f) B - A >> sizeof(int) * 8 - 1

The size of integer in bytes is 4 bytes, but it may be different on other machines. You need to multiply the size of integer by 8 since bit shifting operates in bits. You also need to deduct 1 because you do not need to count the starting position of the integer. We can also do the same for item (b)

• (g) A - B >> sizeof(int) * 8 - 1

However, based on item (e), if we multiply A with item (f), we will get erroneous result if item (f) = 0xffff, hence a workaround is to perform an AND operation between A and (f), and B with (g), thus we get the following lines (Note that we are using AND operation as a bitwise operator and not as a conditional operation, hence we are not violating any constraints of the problem):

• (h) B - A >> sizeof(int) * 8 - 1 & A

• (i) A - B >> sizeof(int) * 8 - 1 & B

Based on observation, item (h) and item (i)  are mutually exclusive and adding these two (2) will yield the greater number. If A = B, then it will result to 0 - This is our solution to the first requirement.

• (k) X = (A - B >> sizeof(int) * 8 - 1 * B) + 
• (B - A >> sizeof(int) * 8 - 1 * A)

We can use the result of item (k) or X, to solve for Y. But first, we need to find a solution wherein we want to multiply either A or B (assuming they are equal) to either 1 (if A = B) or 0 (if A not equal to B).

• (l) (1 or 0) * A

One way to do it is to (again) get the difference of A - B, but the difference of A and B, when they are equal is zero (0). The reverse of what we are expecting. The quick fix is to negate the result, which also happens to be the solution when the difference of A - B is not zero (0). 

Experimenting on the negate operator yields to the following results:

• !0 = 1
• !100 = 0
• !3 = 0
• !-7 = 0

And so we get:

• (m) !(A - B) * A

Item (m) only gives us the value of A, when A = B, but does not give us the value of X or item (k). Since (k) and (m) are mutually exclusive, we can add (k) and (m) resulting to the solution of the second requirement.

• (n) Y = X + !(A - B) * A

The C++ program below implements the complete solution in finding the larger number between two (2) integer variables using bitwise operators.

    // Sets the larger number to X, otherwise set X to 0
    // Assumming X, Y, A and B have the same integer type
    int X = (A - B >> sizeof(A) * 8 - 1 & B) + 
            (B - A >> sizeof(A) * 8 - 1 & A);
    
    // Sets the larger number to X, otherwise set X to A
    int Y = X + !(A - B) * A;

If you're interested in finding out how to know the larger number between two (2) variables without using conditional and bitwise, click here.