Author: Gerd Isenberg
Date: 11:55:02 02/28/06
Go up one level in this thread
I admit, that my first impression was - witchcraft.
Somehow similar to the Kogge-Stone shock you gave me once ;-)
The key was "rippling a carry through the unwanted bits" - yes so simple.
But the expression was a mystery to me at the first glance.
Reinhard's expression was much more intuitive to understand the carry rippling.
Now i see it is no witchcraft but simple algebra ;-)
Here the initial steps again as suggested by Reinhard:
1.) or with the complement of the original set (d) to set all unwanted bits,
so that a possible overflow walks through.
2.) increment and ripple the carry through unwanted bits
3.) reset all unwanted bits by anding with the original set (d)
For step one we can safely replace "or" by "add" (or even xor).
Because unwanted bits are always zero and become never member of a subset(d).
n = ((n + ~d) + 1) & d;
Now we replace the One's complement by Two's complement minus one:
n = ((n + (-d-1)) + 1) & d;
to finally get
n = (n-d) & d;
your expression.
Thanks for sharing this neat trick!
Cheers,
Gerd
This page took 0.01 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.