How does a computer compare numbers?

[Insectoid]

How does a computer actually compare numbers to be greater than or less than each other? In actual binary/cpu/whatever stuff, not programming.

My guess is that is would subtract the 'smaller' number from the 'larger' number in terms of the comparison, then use the negative/positive bit as the result.

ex. 3>5

in this case, 3 would be the 'larger' number because the comparison is asking if 3 is larger than 5.

3-5 returns -2. Take the negative bit as the answer (is that bit high for positive or negative?) and return it as the true/false result. This would, however, not account for equality.

I'm just curious as to how it actually works.

[OneOffDriveByPoster]

Subtraction is exactly it. I believe comparisons are usually thought of as less-than.

[Insectoid]

I was right? Yay!

Usually my assumptions are more complicated than the actual solution...I am quite pleased with myself!

Huzzah! Newbie God-dom! And with minimal spammage!

[OneOffDriveByPoster]

Just to elaborate:
A < B is already using <
A > B can be rewritten B < A
A <= B can be rewritten !(A > B), so !(B < A)
A >= B can be rewritten !(A < B)

[matt271]

why would it subtract? that seems like a lot of work for a simple check

what if u just checked for the first most significant bit that is a 1. if it comes first in 1 number that number is bigger.
if it comes at the same time, checked the 2nd, 3erd, etc. until it finds the first difference

this is how i would do it

3 -> 0011
5 -> 0101

0011
0101
neither are 1 so keep checking

0011
0101
second one is a 1

therefore 5 is bigger than 4

or,

10 -> 1010
11 -> 1011

1010
1011
both are 1 so keep checking

1010
1011
neither are 1 so keep checking

1010
1011
both are 1, so keep checking

1010
1011
sec one is a 1

therefore 11 is bigger than 10

[Tony]

matt271 @ Mon Apr 06, 2009 2:11 pm wrote:

if it comes first in 1 number that number is bigger.

How would you handle negative numbers?

[md]

Doing subtraction is easy in hardware - the ALU is there, and us used for lots of things. Comparing bits is hard - the hardware is very specific and not there.

And subtraction with transistors can be thought of as atomic. It takes one unit of time. Your bitwise comparison would be just as fast or could indeed be slower.

[Zren]

Tony @ Mon Apr 06, 2009 2:38 pm wrote:

matt271 @ Mon Apr 06, 2009 2:11 pm wrote:

if it comes first in 1 number that number is bigger.

How would you handle negative numbers?

Aren't negative numbers just the first half of the maximum of an integer? Like say 256 is the maximum numbers possible if we were using whole numbers (Only Positive Integers).

00000000 = -128
10000000 = 0
11111111 = 127

So in total there is 256 possibilities. So in a sense, matt271's checking alghorythm would still work. PS: 0011 = 3 not 4.

I'm not 100% on this...but I always wondered why you could have double the size for a non-negative number.

[Tony]

Zren @ Mon Apr 06, 2009 4:51 pm wrote:

Aren't negative numbers just the first half of the maximum of an integer?

No, binary numbers are stored as Two's complement

Quote:

127 = 0111 1111
1 = 0000 0001
0 = 0000 0000
-1 = 1111 1111
-128 = 1000 0000

Edit:

Zren @ Mon Apr 06, 2009 4:51 pm wrote:

but I always wondered why you could have double the size for a non-negative number.

I think you might be referring to signed vs unsigned integers. If an integer is unsigned (no negative numbers), then you could use 1 more bit, which represents one more power of 2. (the range is the same though, just shifted out of the negatives).

[matt271]

Zren @ Mon Apr 06, 2009 5:51 pm wrote:

PS: 0011 = 3 not 4.

my bad :]

md @ Mon Apr 06, 2009 5:20 pm wrote:

And subtraction with transistors can be thought of as atomic. It takes one unit of time. Your bitwise comparison would be just as fast or could indeed be slower.

interesting. im going to look into exactly how that works. i thought math operations where done by some complicated and highly refined method using bit shifts and boolean operations



but yeah i thought of negative numbers and kinda shrugged it off

[Tony]

Math operations are complicated. But it's all done in one clock cycle. If you are comparing two 32 bit numbres, then your best case scenario is getting a conclusive match on the first try, and worst case is that the numbers are equal.

So in the best case, you spend as much time as it would take to do a subtraction; in the worse case the method of checking individual bits is 32 times slower. (Unless there's specialized hardware involved, but you still can't beat 1 clock via subtraction)

[DanielG]

would subtraction always work? what happens if you have a huge -ve and a huge +ve, subtracting one from the other might result in a number that is greater than maxint or smaller than miniint, which would cause problems.

[Tony]

depends on the hardware, most would detect an overflow. Then the ALU can figure out the result based on the overflow and the high-bit.

Edit:
Note how the IF condition works correctly, but the program crashes at the last line

Turing:

var high : int := maxint var low : int := minint put high put low if high > low then    put "win" else    put "fail" end if put high - low

[matt271]

this is pretty interesting. i didnt realize the cpu could do stuff like subtract two integers in 1 clock.

is clock the unit of speed of a cpu? like does 500MHz = 500 million clocks per sec?


i remember somebody telling me that 500MHz means 500 million "operations" per second and that "1+1" would be *several* operations.

i want to learn this kind of thing. im only first year cs and we havnt jumped into anything interesting yet

[Tony]

matt271 @ Mon Apr 06, 2009 8:25 pm wrote:

i remember somebody telling me that 500MHz means 500 million "operations" per second and that "1+1" would be *several* operations.

Indeed. One way to increase CPU's clock speed is to split instructions into more steps, have each (smaller) step run faster, and thus claim that CPU's speed is faster. Pentium 4s have gotten up to 31 clock steps per instruction. That's why back in the day "slower" AMDs and PowerPCs were outperforming crazy-fast P4s on benchmarks.

Although to make things more complicated to understand, this is where pipelineing comes in -- running multiple instructions are the same time.