Kernighan and Ritchie confusion

This is a discussion on Kernighan and Ritchie confusion within the C Programming forums, part of the General Programming Boards category; Hi, I am working my way through the Kernighan and Ritchie book alongside my university course. I have been comfortable ...

  1. #1
    Registered User
    Join Date
    Aug 2009
    Posts
    16

    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));
    }

  2. #2
    Registered User
    Join Date
    Aug 2009
    Posts
    16

    The example I am working with

    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));
    }

  3. #3
    Registered User
    Join Date
    Jun 2008
    Posts
    54
    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!
    Last edited by Boxknife; 02-06-2011 at 09:49 AM.

  4. #4
    Registered User
    Join Date
    Aug 2009
    Posts
    16
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C Book Recommendations
    By sean in forum C Programming
    Replies: 160
    Last Post: 07-22-2011, 01:55 PM
  2. Character counting issues from Kernighan text
    By Vampireclown in forum C Programming
    Replies: 2
    Last Post: 05-01-2010, 10:29 AM
  3. doubt about kernighan and ritchie excercise 1-12
    By afol_1 in forum C Programming
    Replies: 12
    Last Post: 01-05-2009, 06:31 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21