Zero-fill shift

[Eli Stevens (WG.c)]

Daniel Orner <cs993442 at cs.yorku.ca> wrote:
> Great, this works. 8-) Unfortunately, I've run into another problem.
> In the Java algorithm, two integers are added. This often results in
> an overflow and a negative number, which is the desired result.
> However, I can't seem to duplicate that in Python, as adding two
> integers that are too large just results in a long (and using the
> int() method doesn't work). I've tried various solutions, but haven't
> come up with something that duplicates this behavior exactly.

The behavior you are after is called "Two's complement," and is tied to
using fixed-size integers and to simplifying how negative numbers are
handled in hardware.  Google, of course, knows all (provided you know the
questions... ;).

But more to the point:  Here's something that will do the trick if your
overflow isn't ever more than one bit.  Note the last two cases - you may
need to do some additional bounding if cases like those might occur for you
(I haven't really dug into your algorithm, sorry! :).  You will also need to
extend it out to 32 bits.

>>> def cp(myint):
...   if myint > 0x7f:
...     return -1 * (0xff - myint + 1)
...   return myint
...
>>> cp(1)
1
>>> cp(127)
127
>>> cp(128)
-128
>>> cp(255)
-1
>>> cp(0)
0
>>> cp(256)
0
>>> cp(257)
1
>>> cp(513)
257
>>> cp(-257)
-257



Heh, implementing 2's complement in software...  Who'd have thought?  :)

Enjoy!  HTH,
Eli

-- 
Give a man some mud, and he plays for a day.
Teach a man to mud, and he plays for a lifetime.
WickedGrey.com uses SpamBayes on incoming email:
               http://spambayes.sourceforge.net/
                                              --