CODEWITHSUNDEEP
binaryintegermaxboolean-logic
Charles
Charles

Reputation: 1239

Finding the maximum of two integers in binary using bit logic only

This is a bit tricky, it's a nice challenge for those up to the task I think. And I did search through all the questions previously asked, but I couldn't find what I want.

The aim here is, given 2 integers written in binary on n bits, to find the greatest one of them using only logic operations (AND, OR, ...) on the n bits of each integer (result would be 0 if the first integer is the greatest, and 1 otherwise). Ultimately, the aim is to be able to draw an electronic circuit where the 2*n bits would be wires with or without tension, and plug the wires into actual electronic components that would perform logical operations.

I started thinking about this problem by realizing that whatever happens (i.e. whatever n is), 2^n is greater 2^0 + ... + 2^(n-1) (mathematically speaking, that's easy to come up with). That means that whichever integer has a bit (say number k) that's at 1 when the corresponding bit in the other integer is 0, with all other bits between n and k (all bits to the left of k) identical, is the greatest. Example :

A : 010(1)1011 is greater than B : 010(0)1111 with the significant bit in parentheses. All bits to its left are identical, and we don't have to care about the others.

So one can perform an exclusive OR (XOR) on all pairs of bits : the significant one would yield a 1, and then I can perform a NAND between corresponding bit of A with the result of that XOR, so that it'd yield a 0 if A's k-th bit is a 1 and a 1 if it's B's k-th bit that is a 1. The only thing is ... what about the bits to the right of the significant one ? They can be different (thus also yielding a 1 when performing a XOR) but I have to ignore that ... Any ideas ?

Upvotes: 6

Views: 12821

Answers (5)

PutinReloaded
PutinReloaded

Reputation: 11

Greater of two integers:

unsigned int a, b, max;
max = ((~(a >= b)+1) & a) | ((~(b >= a)+1) & b);

Explanation: Let's assume an integer is 4 bytes. (a >= b) translates into either 0001 or 0000. The same for (b >= a). Adding 1 after a negation "~X + 1" gives the two's complement. This way the 1 from the comparison is converted into FFFF. The 0 remains 0000. If a = b we have: FFFF & a | FFFF & b = a. If a > b we have: FFFF & a | 0000 & b = a. If b > a we have: 0000 & a | FFFF & b = b.

Upvotes: 1

user40521
user40521

Reputation: 2129

A : 010(1)1011 
B : 010(0)1111

shift of first bits 

C : 0
D : 0

if they match shift of the next one, if they dont match return D.

Upvotes: 0

praemdonck
praemdonck

Reputation: 66

There are ICs that to what you want to do, one example is cmos 4063. This IC can only compare numbers of 4 bits, however it give the possibility of expansion by cascading more than one device.

If what you are interested is the logic to implement it yourself you can have a look at the datasheet http://www.intersil.com/content/dam/Intersil/documents/fn33/fn3318.pdf which has a diagram of the logic of the comparator

Upvotes: 0

Luca Geretti
Luca Geretti

Reputation: 10286

You care for a hardware implementation, so I guess you are better off treating A and B as signed N-bit integers, then

  1. Invert B to its -B representation;
  2. Sum A to B with a N-bit Full Adder;
  3. Use the sign of the result as a selector variable of a 2-input, N-bit multiplexer.

It is expressible with logical functions only, of course.

More in detail on the third point, just checking the sign S (1: negative, 0: positive) satisfies the predicate B>A. So if the input taken by the multiplexer for selector value 0 is A (and for selector value 1 is B), you have your result. In the case of equality, you still pick A, but A=B so that's logically irrelevant which one you pick.

Being A and B variables, this is the most sensible way to go, since you can reuse the adder for, well, addition. An optimization for the specific case of checking the maximum is certainly possible, I guess.

ADDITIONAL COMMENT:

It is important to underline that sequential implementations that progressively check each digit of A and B suffer from requiring, in the worst case, N checks to return a result. If you have two streams of values for A and B, you must guarantee to be able to keep up with them. Consequently, the logic of your max() function works at N times the frequency of the data streams. Seen from another perspective, you need to slow down the rate that your data is fed to your max() logic.

On the contrary, the combinatorial implementation that I suggested (or any optimization of it) trades speed with hardware resources. In other terms, it is as fast as you can produce data for A and B. Propagation delay for a combinatorial implementation is also usually higher compared to a sequential implementation, but that is not an issue in terms of frequency.

Upvotes: 3

napolux
napolux

Reputation: 16094

I will iterate on the two numbers (let's call them a and b) by adding a digit to the second operator of the binary AND until one of the number becomes 0...

If one of the number is 0 and the other one is > 0 you'll have the maximum of the two...

1st loop:

a & 1 b & 1

2nd loop:

a & 10 b & 10

3rd loop:

a & 100 b & 100

And so on...

To check if one of the number is equal to zero after the operation you can (given n, the length of the number as known) make an and with a number that is n times zero plus 1 at the most significant n+1 position...

My 2 (maybe wrong) cents :)

Upvotes: 0

Related Questions