Hi,
I'm reading "the c programming language" by kerningham and ritchie.
Looking through the original "bitcount" expression at
http://users.powernet.co.uk/eton/kandr2/krx209.html, It looks like if
the first bit of the input integer x is a "1", then it will be
ignored.
Nope.
Let's show the C source you refer to...
/* 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;
}
The object is to count the number of bits (in an unsigned integer of
arbitrary value) which are set to 1 (as opposed to those bits that are set
to zero).
In the code above, we enter a loop that
1) sets the count of one bits (b) to zero
2) tests if the arbitrary unsigned integer (x) is non-zero
(and exits the loop if it isn't)
3) tests if the low order bit of the arbitrary unsigned integer (x) is
set to one, and increments the bit-count (b) if it was
4) shifts the arbitrary unsigned integer (x) one bit to the right,
disposing of the old low order bit, and filling the (now vacant)
high-order bit with a zero
5) return to the top of the loop, at step 2
While there are "one bits" in the arbitrary unsigned integer (x), its value
can never be zero. Because it is unsigned, its value can never be less than
zero either, and the right-shift will pad the high order end with zeros.
Thus, the loop can only end when all the "one bits" have been shifted down
to the low order bit position, and counted.
I understand the second version of bitcount on the link above though.
For the audience, let's show the code you refer to:
/* bitcount: count 1 bits in x */
int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x &= (x-1))
b++;
return b;
}
Do the bit patterns of all unsigned integers begin with a zero?
No. They may start with a 1. And your question indicates to me that you
don't quite understand the second version as well as you indicate you do.
Also, in the for loop initiation for(b = 0; x != 0; x >>= 1), how does
x know what number to start at?
x starts at what ever value was passed into the function (notice that the
function prototype is " int bitcount(unsigned x) ")
It looks to me like it cannot start at zero
Sure it can. And if it does, then the loop will exit immediately after
setting b to zero (b = 0
, and the count of one-bits will be zero.
--
Lew Pitcher
Master Codewright & JOAT-in-training | Registered Linux User #112576
http://pitcher.digitalfreehold.ca/ | GPG public key available by request
---------- Slackware - Because I know what I'm doing. ------
