24.4LogicFormulas 395
Case
010
b
vv
120
b
vv
221
b
vv
01
|
b
b
01
&
b
b
Sum
0
v
largest 0 0 0 0 0 0
0 0 1 0 0 0
1
v
largest 1 0 0 1 0 1
1 1 0 1 0 1
2
v
largest 0 1 1 1 1 2
1 1 1 1 1 2
Impossible 0 1 0 1 0 1
1 0 1 1 0 1
Table 24.3. This table lists all possible combinations for the truth values
0
b
,
1
b
, and
2
b
relating the
values
0
v
,
1
v
, and
2
v
. The sum of
01
|
b
b
and
12
&
b
b gives the index of the largest value.
template <typename T> int GetGreatestValueIndex(const T *value)
{
bool b0 = (value[1] > value[0]);
bool b1 = (value[2] > value[0]);
bool b2 = (value[2] > value[1]);
return ((b0 | b1) + (b1 & b2));
}
Listing 24.9. This function returns the index, in the range
0, 2
, corresponding to the largest value
in a set of three.
24.4LogicFormulas
We end this chapter with Table 24.4, which lists several simple logic formulas
and their effect on the binary representation of a signed integer. (See also [Eric-
son 2008].) With the exception of the last entry in the table, all of the formulas
can be calculated using two instructions on the PowerPC processor due to the
availability of the
andc, orc, and eqv instructions. Other processors may require
up to three instructions.
396 24.BitHacksforGames
Formula Operation / Effect Notes
x & (x - 1) Clear lowest 1 bit. If result is 0, then x is 2
n
.
x | (x + 1) Set lowest 0 bit.
x | (x - 1) Set all bits to right of lowest 1 bit.
x & (x + 1) Clear all bits to right of lowest 0 bit. If result is 0, then x is 21
n
.
x & -x Extract lowest 1 bit.
~x & (x + 1) Extract lowest 0 bit (as a 1 bit).
~x | (x - 1) Create mask for bits other than lowest 1 bit.
x | ~(x + 1) Create mask for bits other than lowest 0 bit.
x | -x Create mask for bits left of lowest 1 bit, inclusive.
x ^ -x Create mask for bits left of lowest 1 bit, exclusive.
~x | (x + 1) Create mask for bits left of lowest 0 bit, inclusive.
~x ^ (x + 1) Create mask for bits left of lowest 0 bit, exclusive. Also x ≡ (x + 1).
x ^ (x - 1) Create mask for bits right of lowest 1 bit, inclusive. 0 becomes 1
.
~x & (x - 1) Create mask for bits right of lowest 1 bit, exclusive. 0 becomes 1
.
x ^ (x + 1) Create mask for bits right of lowest 0 bit, inclusive. 1
remains 1
.
x & (~x - 1) Create mask for bits right of lowest 0 bit, exclusive. 1
remains 1
.
Table 24.4. Logic formulas and their effect on the binary representation of a signed integer.
References
[Anderson 2005] Sean Eron Anderson. “Bit Twiddling Hacks.” 2005. Available at http://
graphics.stanford.edu/~seander/bithacks.html.
[Ericson 2008] Christer Ericson. “Advanced Bit Manipulation-fu.” realtimecollision de-
tection.net - the blog, August 24, 2008. Available at http://realtimecollision detec-
tion.net/blog/?p=78.
[Hoxey et al. 1996] Steve Hoxey, Faraydon Karim, Bill Hay, and Hank Warren, eds. The
PowerPC Compiler Writer’s Guide. Palo Alto, CA: Warthman Associates, 1996.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.