Answer to Exercise 2-9, page 51
Solution by Gregory Pietsch
In a two's complement number system, x &= (x-1) deletes the rightmost 1-bit in x . Explain why. Use this observation to write a faster version of bitcount .
bitcount is written on p.50 as this:
/* bitcount: count 1 bits in x */
int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x >>= 1)
if (x & 01)
b++;
return b;
}
Answer: If x is odd, then (x-1) has the same bit representation as x except that the rightmost 1-bit is now a 0. In this case, (x & (x-1)) == (x-1). If x is even, then the representation of (x-1) has the rightmost zeros of x becoming ones and the rightmost one becoming a zero. Anding the two clears the rightmost 1-bit in x and all the rightmost 1-bits from (x-1). Here's the new version of bitcount:
/* bitcount: count 1 bits in x */
int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x &= (x-1))
b++;
return b;
}
'The C Programming Language' 카테고리의 다른 글
Chapter 3 - Control Flow 1 (0) | 2009.03.25 |
---|---|
Chapter 2 - Types, Operators and Expressions 10 (0) | 2009.03.25 |
Chapter 2 - Types, Operators and Expressions 8 (0) | 2009.03.25 |
Chapter 2 - Types, Operators and Expressions 7 (0) | 2009.03.25 |
Chapter 2 - Types, Operators and Expressions 6 (0) | 2009.03.25 |