Need help understanding "getbits()" method in Chapter 2 of K&R C

Question

In chapter 2, the section on bitwise operators (section 2.9), I'm having trouble understanding how one of the sample methods works.

Here's the method provided:

unsigned int getbits(unsigned int x, int p, int n) {
    return (x >> (p + 1 - n)) & ~(~0 << n);
}

The idea is that, for the given number x, it will return the n bits starting at position p, counting from the right (with the farthest right bit being position 0). Given the following main() method:

int main(void) {
    int x = 0xF994, p = 4, n = 3;
    int z = getbits(x, p, n);
    printf("getbits(%u (%x), %d, %d) = %u (%X)\n", x, x, p, n, z, z);

    return 0;
}

The output is:

getbits(63892 (f994), 4, 3) = 5 (5)

I get portions of this, but am having trouble with the "big picture," mostly because of the bits (no pun intended) that I don't understand.

The part I'm specifically having issues with is the complements piece: ~(~0 << n). I think I get the first part, dealing with x; it's this part (and then the mask) that I'm struggling with -- and how it all comes together to actually retrieve those bits. (Which I've verified it is doing, both with code and checking my results using calc.exe -- thank God it has a binary view!)

Any help?

Solution 1

Let's use 16 bits for our example. In that case, ~0 is equal to

1111111111111111

When we left-shift this n bits (3 in your case), we get:

1111111111111000

because the 1s at the left are discarded and 0s are fed in at the right. Then re-complementing it gives:

0000000000000111

so it's just a clever way to get n 1-bits in the least significant part of the number.

The "x bit" you describe has shifted the given number (f994 = 1111 1001 1001 0100) right far enough so that the least significant 3 bits are the ones you want. In this example, the input bits you're requesting are there, all other input bits are marked . since they're not important to the final result:

ff94             ...........101..  # original number
>> p+1-n     [2] .............101  # shift desired bits to right
& ~(~0 << n) [7] 0000000000000101  # clear all the other (left) bits

As you can see, you now have the relevant bits, in the rightmost bit positions.

Solution 2

I would say the best thing to do is to do a problem out by hand, that way you'll understand how it works.

Here is what I did using an 8-bit unsigned int.

1. Our number is 75 we want the 4 bits starting from position 6. the call for the function would be getbits(75,6,4);

2. 75 in binary is 0100 1011

3. So we create a mask that is 4 bits long starting with the lowest order bit this is done as such.

~0 = 1111 1111
<<4 = 1111 0000
~ = 0000 1111

Okay we got our mask.

4. Now, we push the bits we want out of the number into the lowest order bits so we shift binary 75 by 6+1-4=3.

0100 1011 >>3 0000 1001

Now we have a mask of the correct number of bits in the low order and the bits we want out of the original number in the low order.

4. so we & them
   

  0000 1001 

& 0000 1111
============

  0000 1001

so the answer is decimal 9.

Note: the higher order nibble just happens to be all zeros, making the masking redundant in this case but it could have been anything depending on the value of the number we started with.

Solution 3

~(~0 << n) creates a mask that will have the n right-most bits turned on.

0
   0000000000000000
~0
   1111111111111111
~0 << 4
   1111111111110000
~(~0 << 4)
   0000000000001111

ANDing the result with something else will return what's in those n bits.

Edit: I wanted to point out this programmer's calculator I've been using forever: AnalogX PCalc.

Solution 4

Nobody mentioned it yet, but in ANSI C ~0 << n causes undefined behaviour.

This is because ~0 is a negative number and left-shifting negative numbers is undefined.

Reference: C11 6.5.7/4 (earlier versions had similar text)

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. [...] If E1 has a signed type and nonnegative value, and E1 × 2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

In K&R C this code would have relied on the particular class of system that K&R developed on, naively shifting 1 bits off the left when performing left-shift of a signed number (and this code also relies on 2's complement representation), but some other systems don't share those properties so the C standardization process did not define this behaviour.

So this example is really only interesting as a historical curiosity, it should not be used in any real code since 1989 (if not earlier).

View more solutions