Kernighan and Ritchie confusion

Hi,

I am working my way through the Kernighan and Ritchie book alongside my university course. I have been comfortable with all exercises so far until this one. The K&R wiki has the code available but I cannot understand it.

If anyone has a minute to break down this code for me it would be much appreciated

Write a function setbits(x,p,n,y) that returns x with the n bits that begin at position p set to the rightmost n bits of y, leaving the other bits unchanged.

Code:

SetBits(unsigned int x, int p, int n, unsigned int y)
{
            return ((x & ~(~(~0 << n) << p+1-n)) | ((~(~0 << n) & y) << p+1-n));
}

Before I prompt the user to input their own values of x, p, n and y I am sending set values I know the desired output for.

Code:

#include <stdio.h>

unsigned int SetBits(unsigned int x, int p, int n, unsigned int y);
void DisplayBits(unsigned value);


int main()
{

	unsigned int k;
	k = SetBits(170, 5, 3, 167);
	DisplayBits(k);
	printf("%d\n", k);
	return 0;
}

unsigned int SetBits(unsigned int x, int p, int n, unsigned int y)
{
	return ((x & ~(~(~0 << n) << p + 1 - n)) | ((~(~0 << n) & y) << p + 1 - n));
}

If you don't already have something for DisplayBits(), you can use

Code:

void DisplayBits(unsigned value)
{
	int i = 0, numbits = sizeof(unsigned int)*8;
	for(;i<numbits;i++)
	{
		if(!(i%4) && i)
			printf(" ");
		printf("%d", !(!(value & (1<<(numbits-i-1)))));
	}
	printf("\n");
}

Printing out the individual parts of that little monster of a statement in SetBits()
will help you follow what's going on. Let's call SetBits(170, 5, 3, 167) and try
to visualize what's going on in the statement by building it up piece by piece.

Keep in mind that << "pushes" bits off of the left end and fills the right end in with zeros. Also remember that addition and subtraction have higher precedence than << and >>. (Normally you ought to just group what you want to happen together in parentheses to make your code clearer, but here I will just use the parts of the statement as they were written.)


Let's start with the left half.

~0:
1111 1111 1111 1111 1111 1111 1111 1111
~0<<3:
1111 1111 1111 1111 1111 1111 1111 1000
~(~0<<3):
0000 0000 0000 0000 0000 0000 0000 0111
~(~0<<3) << 5+1-3:
0000 0000 0000 0000 0000 0000 0011 1000
~(~(~0 << 3) << 5 + 1 - 3):
1111 1111 1111 1111 1111 1111 1100 0111
170 & ~(~(~0 << 3) << 5 + 1 - 3): // (170 in binary is 10101010 with 24 zeros to its left)
0000 0000 0000 0000 0000 0000 1000 0010

Remember that last value. NOW FOR THE RIGHT SIDE.

~(~0 << 3) & 167:
0000 0000 0000 0000 0000 0000 0000 0111
(~(~0 << 3) & 167) << 5+1-3:
0000 0000 0000 0000 0000 0000 0011 1000

BOTH SIDES DONE. Now we BITWISE OR THE LEFT AND RIGHT PARTS TOGETHER

AHHHHHH COMBIIIINE

0000 0000 0000 0000 0000 0000 1000 0010
BITWISE OR
0000 0000 0000 0000 0000 0000 0011 1000
EQUALS
0000 0000 0000 0000 0000 0000 1011 1010

That's 186 in decimal! What's the point of the function? I don't have a clue, but at least now we know how it works!

Thank you BoxKnife!

There is no point in the program at all I don't think. It's just a fairy complicated example to get you using bitwise shift.

I had omitted DisplayBits() from the posted code to keep things short but forgot to omit the declaration as well as the definition.

That was really nicely explained. Thank you again

Ben