views:

815

answers:

4

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?

+10  A: 

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 !!

paxdiablo
Dang! You beat me to it! +1
Mitch Wheat
And suddenly it makes a lot more sense. Thank you very much!
John Rudy
+2  A: 

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 ?

@jim: Hey, not knocking the accuracy of you post. Content wise has more to go on than either of the other two, it would be good to use codeblocks and align changes. The posts use wiki markup, and a tute page links off the "?" above the answer box. I had to read it twice to be able to check it.
_ande_turner_
+3  A: 

~(~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.

David Grant
very clear comparative example! feel like book marking it.
_ande_turner_
+3  A: 
Mark Lubin
Spent about an hour and a half doing exactly that yesterday before deciding I "hit the wall" and needed to ask. :)
John Rudy
Love the edits; thanks!
John Rudy