K & R Question: Need help understanding "getbits()" method in Chapter 2

Question

As I've mentioned before, I'm going through K&R, and overall am doing all right with it. However, in chapter 2, the section on bitwise operators (section 2.9), I'm having trouble understanding how one of the sample methods works -- and as a result, I'm having trouble with the associated exercises.

(This isn't a dupe of my prior question on bit-shifting, btw. This is new-and-improved!)

So 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.

(Note that I'm not looking for help with the associated exercises -- I think if I "got" this, I'd be able to get those.)

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?

Answer 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) right far enough so that the least significant 3 bits are the ones you want. In this example, the bits you're requesting are surrounded by '.' characters.

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

And there you have your bits. Ta da !!

Answer 2

Using the example: int x = 0xF994, p = 4, n = 3; int z = getbits(x, p, n);

and focusing on this set of operations ~(~0 << n)

for any bit set (10010011 etc) you want to generate a "mask" that pulls only the bits you want to see. So 10010011 or 0x03, I'm interested in xxxxx011. What is the mask that will extract that set ? 00000111 Now I want to be sizeof int independent, I'll let the machine do the work i.e. start with 0 for a byte machine it's 0x00 for a word machine it's 0x0000 etc. 64 bit machine would represent by 64 bits or 0x0000000000000000

Now apply "not" (~0) and get 11111111
shift right (<<) by n and get 11111000
and "not" that and get 00000111

so 10010011 & 00000111 = 00000011
You remember how boolean operations work ?

Answer 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.