K&R C chapter 2 assignment operators and expressions

Question

Assignment operators are not something I expected to struggle with. Everything in this section so far is familiar, but the way they explain it makes it seem foreign. I think it's the bitwise operators I'm confused about.

Anyway here is the part I don't get.

The function bitcount counts the number of 1-bits in its integer argument.

/*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;
}

Declaring the argument x to be unsigned ensures that when it is right-shifted, vacated bits will be filled with zeros, not sign bits, regardless of the machine the program is run on.

Not that I really understand the code, but this last sentence is confusing me the most. What does this mean? Does it mean "ones" by "sign bits" and does this have to do with twos complement?

I really had trouble getting through the bitwise operations. Can anyone recommend some comprehensive material to supplement the bitwise stuff in this book?

Answer 1

Suppose x is two’s complement. For illustration, let‘s use an eight-bit width. (C always shifts in a wider width, at least that of int.)

If x is 64 (01000000₂) and we shift it right one bit, we get 32 (00100000₂). When we repeat that, we get 16 (00010000₂), 8 (00001000₂), 4 (00000100₂), 2 (00000010₂) , and 1 (00000001₂).

When x is −64, two’s complement represents it with 11000000₂. If we shift that right and bring in a 0 bit, the bits are 01100000₂, which represents 64+32 = 96. So −64 becomes 96. Now, that might be fine if one were just working with bits. But, if we want to use bit-shifting to divide numbers, we want −32, not 96. The bits for −32 are 11100000₂. So we can get that by bring in a 1 bit instead of a 0 bit. And the bits for −16 are 11110000₂. Then −8, −4, −2, and −1 are 11111000₂, 11111100₂, 11111110₂, 11111111₂. In each case, we bring in a 1 bit when shifting.

So, if we want to use bit-shifting for division, there is a simple rule for a one-bit shift: Shift all bits right one spot and leave the sign bit as is (0 or 1). If we are shifting more than one bit, keep copying the sign bit.

That is called an arithmetic right shift. So, we have two kinds of right shift: An arithmetic right shift that copies the sign bit, and a logical right shift that brings in 0 bits.

For unsigned types, the C standard says a right shift is logical.

For signed types, the C standard does not say whether it is arithmetic or logical. It leaves it to the implementation to define which that implementation uses (or possibly to define something else). That might be due to the history; early machines might not have provided arithmetic right-shift instructions (and may not even have used two’s complement), although it seems hard to imagine these days.

So, when you are writing code that shifts right and you want to be sure of the result you will get, you can use an unsigned type to be sure to get a logical shift.