Author: Bruce Moreland
Date: 21:33:49 11/29/00
Go up one level in this thread
On November 29, 2000 at 19:33:17, James Swafford wrote: >On November 29, 2000 at 15:50:43, Bruce Moreland wrote: >>They will produce the same values on signed ints. If you use unsigned values, a >>/ 2 will be compiled by the Microsoft compiler I use as: >> >> shr eax, 1 >> >>If you use an signed value, you get: >> >> cdq >> sub eax, edx >> sar eax, 1 >> >>This is an attempt to avoid a divide, but it's a lot of evil stuff compared with >>the first one. I bet "cdq" annoys the processor, but I don't know for sure, and >>in any case that's three instructions compared with one. >> > > >cdq is an ugly one for sure. If I'm not mistaken, it involves >a comparison, a conditional jump, and a mov if the flag indicates >the number is negative. Pretty nasty. Seems to me it would be >better to just use unsigned ints wherever possible. I don't know what it is doing, but from context I bet it is putting -1 in EDX if EAX is negative, and 0 otherwise. So what it is doing is adding one (subtracting negative one) from EAX before it's shifted. Essentially this is causing the number to round up rather than rounding down, which is what you want to have happen when you are talking about two's complement negative numbers being divided by two. Assuming one-byte operations for sake of simplicity, you want 0xFF (-1) to convert to 0x00 (0), which is hard to do with a one-bit shift. If you add one to it first, it magically works. Let's see if it works with -2. That's 0xFE, and if you add one to it you get 0xFF (-1), and if you shift that you get 0xFF again, which is -1. So this works, since -2/2 = -1. If you do 0xFD (-3), you get 0xFE, and when you shift that you get -1 again. If you do 0xFC (-4), you get 0xFD, and when you shift that you get 0xFE, which is -2. This shows that the rounding is working properly, and by induction I'm sure we can show that it works for all negative numbers. I could be wrong, since I'm using some intuition here. The reason I thought it might be ugly is that rarely used instructions tend to be pipelined poorly, although I don't know if this one is. bruce
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.