Bitwise setbits function (knr 2-6)

**olbas** · 03-25-2004

Code:

/* getbits: get n bits from position p */
unsigned getbits(unsigned x, int p, int n) 
{
return (x >> (p+1 -n)) & ~(0 << n);
}

This is the example in knr, which is what I have to presumeably adapt to the following:

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

Could someone please re-iterate this. Maybe draw a few diagrams to

**Prelude** · 03-25-2004

Assume x is 01100110 and y is 11010011. With the call setbits ( x, 3, 4, y ), the result is:

Code:

x - 0110
y -     0011
    --------
    01100011

The function takes x up to position p, then replaces n bits with the rightmost n bits of y. Another example would be (using the same bits) and the call setbits ( x, 4, 2, y ):

Code:

x - 011
y -    11
x -      110
    --------
    01111110

Does that help?

**olbas** · 03-25-2004

I see now! Thank you for answering such a lame question

Appreciated.

**olbas** · 03-26-2004

Well, I struggled (still) with the task. I picked the answer off the site, and its below.

return ((x & ((~0 << (p+1)) | (~(~0 << (p+1-n)))) | ((y & (~(~0 << n)) << (p+1 - n));

And I've been breaking it up to try and understand.

(~0 << (p+1))
complement any 0, and left shift by (p+1) fields.

(~(~0 << (p+1-n)))
complement any 0, left shift by (p+1-n), and then complement again back to original value.

Compare the two with Inclusive OR.

...This is where I think I'm wrong. So i try putting it into practise and implementing this... and I get lost.
Could I be looking to closely?

Sorry for being a pain in the neck, really would like to understand. And I have tried checking other bitwise explanations, its jsut the implementation that escapes me.

**Dave_Sinkula** · 03-26-2004

The following is not the easiest thing to look at, but I'm hoping it may help a little.

Code:

#include <stdio.h>

#define WYSIWYG(x)   #x, (x)
const char format[] = "%50s = %08X\n";

/*
 * http://users.powernet.co.uk/eton/kandr2/krx206.html
 *
 * 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.
 */
unsigned setbits(unsigned x, int p, int n, unsigned y)
{
#if 1 /* use 0 to comment out */
   printf(format, WYSIWYG(~0));
   putchar('\n');
   printf("p = %d, n = %d\n", p, n);
   printf(format, WYSIWYG(x));
   printf(format, WYSIWYG(y));
   putchar('\n');
   printf(format, WYSIWYG(      (~0 << (p + 1)                           )));
   printf(format, WYSIWYG(                        (~(~0 << (p + 1 - n)))  ));
   printf(format, WYSIWYG(     ((~0 << (p + 1)) | (~(~0 << (p + 1 - n)) ))));
   printf(format, WYSIWYG((x & ((~0 << (p + 1)) | (~(~0 << (p + 1 - n)))))));
   putchar('\n');
   printf(format, WYSIWYG(      ~(~0 << n)                 ));
   printf(format, WYSIWYG( (y & ~(~0 << n))                ));
   printf(format, WYSIWYG(((y & ~(~0 << n)) << (p + 1 - n))));
   putchar('\n');
#endif
   return (x & ((~0 << (p + 1)) | (~(~0 << (p + 1 - n))))) |
          ((y & ~(~0 << n)) << (p + 1 - n));
}

int main(void)
{
   unsigned k = setbits(0x12341234U, 15, 8, 0x56785678U);
   printf(format, WYSIWYG(k));
   return 0;
}

/* my output
                                                ~0 = FFFFFFFF

p = 15, n = 8
                                                 x = 12341234
                                                 y = 56785678

                                  (~0 << (p + 1) ) = FFFF0000
                            (~(~0 << (p + 1 - n))) = 000000FF
       ((~0 << (p + 1)) | (~(~0 << (p + 1 - n)) )) = FFFF00FF
  (x & ((~0 << (p + 1)) | (~(~0 << (p + 1 - n))))) = 12340034

                                        ~(~0 << n) = 000000FF
                                  (y & ~(~0 << n)) = 00000078
                 ((y & ~(~0 << n)) << (p + 1 - n)) = 00007800

                                                 k = 12347834
*/

**WaltP** · 03-26-2004

Originally posted by olbas
Compare the two with Inclusive OR.

No, the single | means OR the two calues together:

Code:

     a = 010011
     b = 110000

a | b = 110011

**olbas** · 03-26-2004

Thanks for the last note, specifically because I was aware of it, though I was lazy with an explanation, never a good thing, so thanks for bringing this to my attention

In response to your explanation, the FF's baffled me as to a hidden meaning, though I ran with it and re-read both Prelude's explanation and knr's.

~(~0 << (p+1-n))

I couldn't understand the impact of either side of the expression.

Now it reads:
complement bits (p+1-n) from right to left, and then complement the remainder.
EG:
11111111
11111100
00000011

Ahh I understand now, even if it doesn't look like it

Thank you both very much. Really big help.

**Dave_Sinkula** · 03-26-2004

>the FF's baffled me as to a hidden meaning

I find it easier to follow the hex than the binary.

Code:

#include <stdio.h>
#include <limits.h>

#define WYSIWYG(x)   #x, (x), bitstring(buffer, (x))
const char format[] = "%48s = %08X = %s\n";

char *bitstring(char *s, unsigned int value)
{
   unsigned int mask;
   char const letter[2] = { '0', '1' };
   char *start = s;
   for(mask = 1U << ((sizeof(value) * CHAR_BIT) - 1); mask; mask >>= 1)
   {
      *s++ = value & mask ? letter[1] : letter[0];
   }
   *s = 0;
   return start;
}

/*
 * http://users.powernet.co.uk/eton/kandr2/krx206.html
 *
 * 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.
 */
unsigned setbits(unsigned x, int p, int n, unsigned y)
{
#if 1 /* use 0 to comment out */
   char buffer [ sizeof x * CHAR_BIT + 1 ];
   printf(format, WYSIWYG(~0));
   printf("p = %d, n = %d\n", p, n);
   printf(format, WYSIWYG(x));
   printf(format, WYSIWYG(      (~0 << (p + 1)                           )));
   printf(format, WYSIWYG(                        (~(~0 << (p + 1 - n)))  ));
   printf(format, WYSIWYG(     ((~0 << (p + 1)) | (~(~0 << (p + 1 - n)))) ));
   printf(format, WYSIWYG((x & ((~0 << (p + 1)) | (~(~0 << (p + 1 - n)))))));
   putchar('\n');
   printf(format, WYSIWYG(y));
   printf(format, WYSIWYG(      ~(~0 << n)                 ));
   printf(format, WYSIWYG( (y & ~(~0 << n))                ));
   printf(format, WYSIWYG(((y & ~(~0 << n)) << (p + 1 - n))));
   putchar('\n');
#endif
   return (x & ((~0 << (p + 1)) | (~(~0 << (p + 1 - n))))) |
          ((y & ~(~0 << n)) << (p + 1 - n));
}

int main(void)
{
   unsigned k;
   char buffer [ sizeof k * CHAR_BIT + 1 ];
   k = setbits(0x12341234U, 15, 8, 0x56785678U);
   printf(format, WYSIWYG(k));
   return 0;
}

/* my output
                                              ~0 = FFFFFFFF = 11111111111111111111111111111111
p = 15, n = 8
                                               x = 12341234 = 00010010001101000001001000110100
                                (~0 << (p + 1) ) = FFFF0000 = 11111111111111110000000000000000
                          (~(~0 << (p + 1 - n))) = 000000FF = 00000000000000000000000011111111
      ((~0 << (p + 1)) | (~(~0 << (p + 1 - n)))) = FFFF00FF = 11111111111111110000000011111111
(x & ((~0 << (p + 1)) | (~(~0 << (p + 1 - n))))) = 12340034 = 00010010001101000000000000110100

                                               y = 56785678 = 01010110011110000101011001111000
                                      ~(~0 << n) = 000000FF = 00000000000000000000000011111111
                                (y & ~(~0 << n)) = 00000078 = 00000000000000000000000001111000
               ((y & ~(~0 << n)) << (p + 1 - n)) = 00007800 = 00000000000000000111100000000000

                                               k = 12347834 = 00010010001101000111100000110100
*/

**olbas** · 03-26-2004

There's a new method

And it does seem more conveniant, and also more helpful with keeping each number base in my head.

sizeof and limits.h haven't been introduced yet, though I am familiar with them, but I cannot include them in my final answer for the exercise..its cheating you see :P

The buffer array decleration is different, I didn't know you could use expressions for the elements. Also, the for loop has some interesting arguements.

Million and one ways to do things in C, you seem to be a good coder, so forgive me if I don't look for errors

tyvm

**Dave_Sinkula** · 03-27-2004

>Also, the for loop has some interesting arguements.

Oops -- old code for a quick hack. Currently my preferred "high bit thingy" looks like this for unsigned ints.

Code:

#include <stdio.h>
#include <limits.h>

char *bitstring(char *s, unsigned int value)
{
   unsigned int mask;
   char *start = s;
   for ( mask = (-1U >> 1) + 1; mask; mask >>= 1 )
   {
      *s++ = "01"[mask & value ? 1 : 0];
   }
   *s = 0;
   return start;
}

int main(void)
{
   unsigned k = 0x12341234U;
   char buffer [ sizeof k * CHAR_BIT + 1 ];
   printf("k = %08X = %s\n", k, bitstring(buffer, k));
   return 0;
}

/* my output
k = 12341234 = 00010010001101000001001000110100
*/

>The buffer array decleration is different, I didn't know you could use expressions for the elements.

As long as it is constant at compile time, its okay for C89.

**olbas** · 03-27-2004

ok this drove me freakin insane, so i hope i can understand and implement this PITA.

x ^ (~(~0 << n) << p)
x = 1234 1234
n = 8
p = 16
~0 = FFFF FFFF

Step 1: (~0 << n) = FFFF FF00
Step 2: ~ = 0000 00FF
Step 3: << p = 0000 FF00

Step 4: x ^:
1234 1234
0000 FF00
---------------
1234 ED34

Pleaaaase tell me I got that right.

The solution included (~(~0U << n), the U represents an unsigned int type, it's not neccessary though is it?

**olbas** · 03-27-2004

Exercise:

Write a function rightrot(x.n) that returns the value of the integer x to the right by n bit positions.

Given answer:

Code:

unsigned rightrot(unsigned x, unsigned n)
{
    while (n > 0) {
        if ((x & 1) == 1)
            x = (x >> 1) | ~(~0U >> 1);
        else
            x = (x >> 1);
        n--;
    }
    return x;

My answer:

Code:

#include <stdio.h>

unsigned rightrot(unsigned, unsigned);
int main(void) {
        unsigned x = 12;
        unsigned n = 2;

        printf("%u", rightrot(x, n));
        return 0;
        }

unsigned rightrot(unsigned a, unsigned b) {
        return (a >> b);
        }

Why does it seem like I have done it wrongly.. I did what the exercise requested, yet mine seems somewhat simplier. Any comments on why this is? Obviously error checking is missing.

**Dave_Sinkula** · 03-28-2004

Originally Posted by olbas

Why does it seem like I have done it wrongly.. I did what the exercise requested, yet mine seems somewhat simplier. Any comments on why this is?

The test values you use don't demonstrate any difference between a bitwise rotation and a bitwise shift. If you had chosen different values, then the difference would be more noticeable.

Code:

#include <stdio.h>

unsigned rightrot1(unsigned x, unsigned n)
{
   while ( n > 0 )
   {
      if ( (x & 1) == 1 )
         x = (x >> 1) | ~(~0U >> 1);
      else
         x = (x >> 1);
      n--;
   }
   return x;
}

unsigned rightrot2(unsigned a, unsigned b)
{
   return(a >> b);
}

int main(void)
{
   unsigned result;
   unsigned x = 12;
   unsigned n = 2;
   
   result = rightrot1(x, n);
   printf("rightrot1(%u, %u) = %u = %x\n", x, n, result, result);
   result = rightrot2(x, n);
   printf("rightrot2(%u, %u) = %u = %x\n", x, n, result, result);
   
   x = 0x1234U;
   n = 8;
   result = rightrot1(x, n);
   printf("rightrot1(%u, %u) = %u = %x\n", x, n, result, result);
   result = rightrot2(x, n);
   printf("rightrot2(%u, %u) = %u = %x\n", x, n, result, result);
   return 0;
}

/* my output
rightrot1(12, 2) = 3 = 3
rightrot2(12, 2) = 3 = 3
rightrot1(4660, 8) = 872415250 = 34000012
rightrot2(4660, 8) = 18 = 12
*/

**olbas** · 03-29-2004

Ahh I get that now, (a >> b) right shifts the left-most 1-bit n places and returns the value. It doesn't shift all 1-bits.

This is why people use loops to feed test values and not just a single static value.

You know your stuff! Thanks! Another lesson learned

**c_lady** · 03-09-2010

Please answer me these qeestions:

x ^ (~(~0 << n) << p)
x = 1234 1234
n = 8
p = 16
~0 = FFFF FFFF

Step 1: (~0 << n) = FFFF FF00
Step 2: ~ = 0000 00FF
Step 3: << p = 0000 FF00

Step 4: x ^:
1234 1234
0000 FF00
---------------
1234 ED34

I would like someone to explain me the above steps with binary numbers as I am unable to understand it with hexadecimal numbers

Thread: Bitwise setbits function (knr 2-6)

Thread Tools

Search Thread

Display

Bitwise setbits function (knr 2-6)

Similar Threads

Screwy Linker Error - VC2005

Message class Need help befor 12am tonight

Including lib in a lib

Game Pointer Trouble?

Question..