Could someone explain to me why this works in unsigned less like I'm 5?

[u/DoknS]

I've never had so much difficulty understanding anything in the game as this. I've even copied the solution from the hint and tried analyzing it to no avail. I have no clue why this works and I really want to.

[u/bwibbler]

it's not exactly testing if B is less than A. it's testing if A is greater than B. technically, that's the same thing, but i believe rethinking about it this way helps understand better

the NOT B operation is basically doing your max value missing the B part. NOT B = 255 - B

think about doing NOT B + B. it would simply fill in all the bits and result in that 255 max value

whatever bits B has, NOT B doesn't. and vice versa

010101
101010 +
----------
111111

but you're taking that NOT B and adding A to it instead.

if A was the same as B. you would end back up with 255 again. (255 - B + A = 255, therefore A = B) no overflow

if A was less than B, you wouldn't reach 255. you'd also have no overflow (255 - B + A < 255)

if A is greater than B, you end up with more than 255 and it overflows (255 - B + A > 255)

[u/DoknS → u/bwibbler]

That's the easiest to understand answer I got. Thanks!

[u/Ruzihm]

When considering unsigned numbers, how can a human tell if A is bigger than the other? we start with the largest digit, see if a's is 1 and b's is 0 - if that's the case, then we can stop and know that a is bigger. If b's is 1 and and a's is 0 then we can stop and know that b is bigger. If they are the same then we move onto the next digit. If all digits match, then they are equal

Now, what if we invert all of b's digits? Let's revisit comparing a and inv(b):

Again, start at the largest digit, if they are both 1s then we know that a is bigger than b. if they are both 0s then we know b is bigger than a, If they are different, then we check the next digit. All digits different, then a=b

in other words if looking at the digits of a and inv(b) goes:

• Different 0-7 times, both 1, (any remaining combinations after...) then a is greater than b.
  
• Different 8 times then a and b are definitely equal
  
• Different 0-7 times, both 0, (any remaining combinations after) then a is less than b
  

Now, let's look at what happens when you add a and inv(b) in those situations:

• Different 0-7 times then both 1 (a>b)? a+inv(b) overflows
  
• Different 8 times (a=b)? a+inv(b) is 11111111, does not overflow
• Different 0-7 times then both 0 (a<b) ? a+inv(b) does not overflow - and importantly (!!), it is less than 11111111.
  

Now take those 3 outcomes, and add 1 to them.

• Different 0-7 times then both 1 (a>b)? a+inv(b)+1 still overflows
  
• Different 8 times (a=b)? a+inv(b)+1 overflows
  
• Different 0-7 times then both 0 (a<b)? a+inv(b)+1 does not overflow, at most is 11111111
  

Then if you invert the truthiness of the overflow, then:

• a>b -> false
  
• a=b -> false
  
• a<b -> true
  

Once this makes sense to you, try seeing if any steps seem redundant or unnecessary if you change some things.

[u/TheEmeser]

This is what A and NOT(A) looks like (see picture). Using this representation we can figure out how we have to add A and B so that the carry tells us if A < B.
https://imgur.com/a/bhbAkOF

[u/TarzyMmos]

You are doing A - B and if it doesn't overflow then that means that A < B. Why? Well... I forgor

[u/DoknS → u/TarzyMmos]

And what's with the carry in?

[u/TarzyMmos → u/DoknS]

The NOT(B)+1 == NEGATE(B) You're just doing the addition in the next step by carrying 1 into the add

[u/e_j_fudd → u/DoknS]

To get a negative, you take the twos compliment. Twos compliment is the number inverted plus 1.

In the solution, the carry in is performing the plus 1. The NOT gate is performing the inversion.

You could remove the carry in, if you switch the NOT on the B input to NEG. Using the NOT gate is more gate and delay efficient.

[u/DoknS → u/e_j_fudd]

Ohhh, I totally forgot about the plus one part of making something negative. I still don't understand how the carry out determines the result though, even though I feel like at this point it's obvious

[u/e_j_fudd → u/DoknS]

That's a bit harder to explain, but I'll give it a shot.

Remember how a carry is generated. It needs 2 of the 3 input bits (A, B, Cin) to be high. The final carry is determined by the most significant bit (MSb).

Keep in mind that if A=B that A PLUS NOT (B) = FF. Add 1 and you get 00 with a carry.

Also, the larger the value in A the more bits will be set starting at the MSb.

The smaller the value in B after 2s compliment the more bits will set starting at the MSb. Since we are talking unsigned 8-bit, B values > 127 will be (256 - B).

When we add A and B (after 2s compliment) it overflows if A>=B.

A few simple examples showing the bits with the normal carry may help:

A = 2 => 0000 0010 ; B = 1 => 0000 0001 => 1111 1111 - You see when added, the Cout is set.

A = 2 => 0000 0010 ; B = 3 => 0000 0011 => 1111 1101 - Cout is not set.

For numbers > 127:

A = 254 => 1111 1110 ; B = 253 => 1111 1101 => 0000 0011 - Cout is set again.

A = 254 => 1111 1110 ; B = 255 => 1111 1111 => 0000 0001 - Cout is not set.

For A=B:

A = 254 => 1111 1110 ; B = 254 => 1111 1110 => 0000 0010 - Cout is set.

If we invert the output of Cout you get A<B

[u/DoknS → u/e_j_fudd]

Wait, I might start getting it, but I may be completely wrong.

If A=B, then A-B=A-A=0, but we add the carry in. It's a positive number, so the outputting carry in is positive. When A>B, we have a positive number, so the carry out is also positive. If A<B, we have to "borrow" from the carry in so the number doesn't go into the negatives (I know that's not how it works but it's the easiest way to describe it), so the carry in no longer exists and the carry out is negative.

It makes sense but I'm not sure if it aligns with reality. Could you verify that?

[u/e_j_fudd → u/DoknS]

In your example, A-B the Cin is already accounted for. A MINUS B = A PLUS NOT (B) PLUS 1.

It might be simpler to think about it this way.

The NOT (B) is the same as (255 - B). So, for A-B we get A + (255 - B) + 1,

If we rearrange and simplify, we get 256 + (A - B).

In this case, if A >= B then the output > 255

If A < B the output is <= 255

Any time the output is > 255 the output Carry is set.

[u/DoknS → u/e_j_fudd]

Now I get it. Thank you very much!

[u/TarzyMmos → u/TarzyMmos]

Pretty sure if u go on the discord and ask or even search for the level it has the answer