Jump to: navigation, search

The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 2.06 on page 49

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.



Solution by Vidhan Gupta

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

#include<stdio.h>

unsigned setbits(unsigned x,int p, int n,int y);
void printBinary(int num);

int main(){
    unsigned x = 127;
    unsigned test = setbits(x, 5, 3,12);
    printBinary(x);
    printBinary(12);
    printBinary(test);
    return 0;
}
unsigned setbits(unsigned x,int p, int n,int y){
    return (x & ((y<<(p+1-n)) | ~(~(~0<<n)<<(p+1-n))));
}

void printBinary(int num)
{
    int size = sizeof(num) * 8;
    for (int i = size - 1; i >= 0; i--)
    {
        int bit = (num >> i) & 1;
        printf("%d", bit);
    }
    printf("\n");
}
OUTPUT:-
00000000000000000000000001111111
00000000000000000000000000001100
00000000000000000000000001100111

Solution by Richard Heathfield

This one's scary.

#include <stdio.h>

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

int main(void)
{
  unsigned i;
  unsigned j;
  unsigned k;
  int p;
  int n;
  
  for(i = 0; i < 30000; i += 511)
  {
    for(j = 0; j < 1000; j += 37)
    {
      for(p = 0; p < 16; p++)
      {
        for(n = 1; n <= p + 1; n++)
        {
          k = setbits(i, p, n, j);
          printf("setbits(%u, %d, %d, %u) = %u\n", i, p, n, j, k);
        }
      }
    }
  }
  return 0;
}

A simpler way to do this is,

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

--Ihilt 18:45, 1 April 2009 (BST)


Solution by Xggggg

Considering the least significant bit as "0 position":

#include <stdio.h>

int setbits(const int x, const int p, const int n, const int y)
{
	return x & ~(((1U << n) - 1) << p) | (y & ((1U << n) - 1)) << p;
}

int main(void)
{
	printf("0x%X\n", setbits(0x0FFF, 4, 4, 0xA));

	return 0;
}

Solution by Pilcrow

RH seems to have lots of time on his hands. Checking his output would take years, especially since it's all in decimal. I wrote a function to display the results of this problem and the three that follow as strings of bits. I also left in a display as hex strings. Here is my solution. You can use RH's method to test it if you have lots of time.

/* The following function, "getbits", is from K&R p 49 */
/* getbits: get n bits from position p */
unsigned getbits(unsigned x, int p, int n)
{
   return (x >>(p+1-n) & ~(~0 << n);
}


/******************************************/
/* asbits - shows integers as bit strings.*/
/* Usage:                                 */
/*         asbits(x, sizeof(x), FLAG)     */
/* FLAG = 1|0, showing if newline desired */
/******************************************/

void asbits(unsigned x, size_t s, int nl)
{
	int i;

	for(i = s*8-1; i>=0; i--) {
		 getbits(x, i, 1)? putchar('1') : putchar('0');
		 if(!(i%4))putchar(' ');
	}
	if(nl)putchar('\n');
}

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


int main(void)
{
	int off = 27;
	int len = 7;
	unsigned x = 0x12345678;
	unsigned y = 0XffffffFF;

	printf("off: %u  len: %u\n",off,len);
	asbits(x,sizeof(x),1);
	asbits(y,sizeof(y),1);
	asbits(setbits(x,off,len,y),sizeof(x),1);
	printf("%08x %08x %08x\n",x,y,setbits(x,off,len,y));
}

Solution by DevinT

I'm a rookie so I included what was happening to my ints after each step to help keep track of what was happening. I also use the getbits function provided in the book to pull bits out of y.

#include <stdio.h>

unsigned setbits(unsigned x, int p, int n, unsigned y);
unsigned getbits(unsigned x, int p, int n);

int main(void)
{
	int x = 9713;	// 0010 0101 1111 0001
	int y = 3500;   // 0000 1101 1010 1100
	
	printf("Setbit result: %d", setbits(x,11,4,y)); // expecting 0010 1100 1111 0001 - 11761
	
	return 0;
}

/* setbits: set n bits in x starting from position p to the rightmost n bits from y, leaving other bits unchanged */
unsigned setbits(unsigned x, int p, int n, unsigned y)
{
	int mask = ~(~0 << n) << (p - n + 1);	// 0000 1111 0000 0000
	x &= ~mask				// 0010 0000 1111 0001

	y = getbits(y,n-1,n);			// 0000 0000 0000 1100
	y <<= (p - n + 1);			// 0000 1100 0000 0000
	
	return 	x | y;				// 0010 1100 1111 0001
}

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

Solution by Luke Panayi

What I hope is a working solution! I see everyone using (p-n+1) however I'm simply using p-n and seem to get correct results. Unsure if I'm missing something though.

#include <stdio.h>

unsigned setbits(unsigned x, int p, int n, unsigned y)
{
	/*
	Taken from left to right operations (seperated by or operands) with examples x=01011101, p=4, n=3, y=11010011 (numbers here in binary, decimal representations used in program)
		00000111 & 11010011 << 4-3 = 00000110 - the 'mask'
		11110000 & 01011101 = 01010000 - find all bits past point p
		00000001 & 01011101 = 00000001 - find all bits before p-n (the range of bits to be changed)
		00000001 | 01010000 | 00000110 = 00000001 | 01010110 = 01010111 which is the correct awnser
	*/
	return ((~(~0<<p-n) & x) | (((~0<<p) & x) | ((~(~0 << n) & y) << p-n)));
}

int main()
{
	printf("%d\n",setbits(93,4,3,211));
	return 0;
}

(Codybartfast) Thank you Luke for your observation about p+1-n vs p-n. I too had a 'working' solution with p-n, but you got me to investigate and my solution only worked if the first (rightmost) bit was 'called' position 1, however, I'm pretty sure the first position should be position 0, i.e.:

Using setbits(93, 4, 3, 211):

p = 4
n = 3
          p
 pos:  76543210
          vvv 
   x:  01011101 =  93
   y:  11010011 = 211
 
rslt:  01010001 =  81

There are two bits to the right of the selection so we will need to shift
the selection left by two: "<< 2".

But if p is zero-based p - n would give a shift of just 1, (4 - 3), whereas 
p + 1 - n gives the correct value of 2.

Solution by Codybartfast (cat 0)

/*
 * If n has its maximum value (e.g. 32) then "<< n" is undefined (Reference 
 * Manual A7.8 p206).  So to avoid "<< 32" I use "<< (n - 1) << 1".  (On my
 * machine "<< 32" is treated as "<< 0".)
 */

unsigned setbits(unsigned x, unsigned p, unsigned n, unsigned y)
{
	unsigned mask;
	if (n == 0) {
		mask = 0;
	} else {
		mask = ~(~0 << (n - 1) << 1) << (p + 1 - n);
	}
	return (x & ~mask) | (y & mask);
}

Solution by Joseph Maltese

Hello all, my solution may not be as intelligent or proper, but this is how I thought about the problem and for me it is simple to understand and intuitive; I'm hoping this can help someone.

//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){
	for(int i = 0; i < n; ++i){
		int yBits = getbits(y, (n-1-i), (n - i));
		int insertBit = yBits;

		insertBit = insertBit >> (n - i - 1);
		insertBit = insertBit << (p - i);

		if(insertBit != 0){
			x = x | insertBit;
		}
		else{
			insertBit = 1;
			insertBit = insertBit << (p - i);
			insertBit = ~insertBit;

			x = x & insertBit;
		}
	}

	return x;

}

//gets n bits from position p in x. getbits(x, 4, 3) returns 3 bits in position 4, 3, and 2; right adjusted
unsigned getbits(unsigned x, int p, int n){
	return (x >> (p+1-n)) & ~(~0 << n);
	
}

Solution by anonymous

getbits based on book, printBinary based on Pilcrow's asbits, and setbits based on Richard Heathfield's "simpler way" solution. To support most data types, long long ints were used for the function's x and y values. The p and n values were set to unsigned chars since the values must be positive and valid values should never be much longer than 64 based on the current minimum size of long long ints (64 bits). If a system has a data type that is larger than 256 bits, than it would be necessary to change the data type to a short or int

Comments were added to thoroughly explain what is going on.

#include <stdio.h>

/*
    Exercise 2-6. 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
*/

long long int getbits(long long int x, unsigned char p, unsigned char n);
void printBinary(long long int x, size_t size);
long long int setbits(long long int x, unsigned char p, unsigned char n, long long int y);

int main(void)
{
    unsigned char a = 0xFF; // 1111 1111
    unsigned char b = 0xFA; // 1111 1010
    printBinary(a, sizeof(a));
    printBinary(b, sizeof(b));
    a = setbits(a, sizeof(a) * 8 - 1 - 2, 3, b);
    printBinary(a, sizeof(a));

    return 0;
}

// returns x with the n bits that begin at position p set to the rightmost n bits of y, leaving the other bits unchanged.
// p and n are positive values less than 256
long long int setbits(long long int x, unsigned char p, unsigned char n, long long int y)
{
    // creates a mask n bits long (e.g. if n = 3, then mask == 0000000000000000000000000000000000000000000000000000000000000011)
    long long int mask = ~(~0ULL << n);
    
    // sets the shift the size of the zero index based position p minus the length of n
    // the p + 1 makes it zero based (e.g if p == 7, it would start at position 7 + 1 or 8 (8th bit), but would be "index 7" if you thought of the number as an array (e.g. x[7]))
    // if you didn't want p to be zero index based, just get rid of the + 1
    // the shift is used to move the mask over for x to zero out the values where the y values will be
    // this is also used to move the 1 values from (y & mask) to the correct position so that it will update the values at position p in x that were just zeroed out
    unsigned int shift = p + 1 - n;

    // Since words can only do so much, see below to understand what this code does
    // However, if one was to explain this.... the mask is shifted to the left to align the 1's at the start of position p and end at position p + n
    // Then the updated mask has its values inversed so the 1's are now zeros at position p to p + n and the rest are 1s. This mask is then bitwised AND on x, which
    // clears out the bits in x that will be replaced by the rightmost n bits in y (which once again is from position p to p + n).
    // Meanwhile, on the right side of the bitwise OR operator, the mask is bitwised AND with y to clear out everything but the rightmost n bits
    // The result of this is shifted to the left so these n bits start at position p and end at p + n
    // finally, the updated x is bitwised OR with updated y to set the position p to p + n bits in x to the rightmost n bits of y
    return (x & ~(mask << shift)) | ((mask & y) << shift);

    /*
        Here is an example of setbits being called:
        setbits((char) 0xFF, sizeof(char) * 8 - 1 - 2, 3, (char) 0xFA);
        If the above function was executed, this is essentially what would happen:


        long long int mask = ~(~0ULL << n)
        long long int mask = ~(~0ULL << 3)
        long long int mask = ~(~0000000000000000000000000000000000000000000000000000000000000000 << 3)
        long long int mask = ~(1111111111111111111111111111111111111111111111111111111111111111 << 3)
        long long int mask = ~1111111111111111111111111111111111111111111111111111111111111000
        long long int mask = 0000000000000000000000000000000000000000000000000000000000000111

        unsigned int shift = p + 1 - n
        unsigned int shift = (sizeof(char) * 8 - 1 - 3) + 1 - 3
        unsigned int shift = (1 * 8 - 1 - 3) + 1 - 3
        unsigned int shift = 2

        (x & ~(mask << shift)) | ((mask & y) << shift)
        (0xFF & ~(mask << shift)) | ((mask & 0xFA) << shift)
        (0000000000000000000000000000000000000000000000000000000011111111 & ~(mask << shift)) | ((mask & 0000000000000000000000000000000000000000000000000000000011111010) << shift)
        (0000000000000000000000000000000000000000000000000000000011111111 & ~(0000000000000000000000000000000000000000000000000000000000000111 << 2)) | ((0000000000000000000000000000000000000000000000000000000000000111 & 0000000000000000000000000000000000000000000000000000000011111010) << 2)
        (0000000000000000000000000000000000000000000000000000000011111111 & ~0000000000000000000000000000000000000000000000000000000000011100) | ((0000000000000000000000000000000000000000000000000000000000000111 & 0000000000000000000000000000000000000000000000000000000011111010) << 2)
        (0000000000000000000000000000000000000000000000000000000011111111 & ~0000000000000000000000000000000000000000000000000000000000011100) | (0000000000000000000000000000000000000000000000000000000000000010 << 2)
        (0000000000000000000000000000000000000000000000000000000011111111 & ~0000000000000000000000000000000000000000000000000000000000011100) | 0000000000000000000000000000000000000000000000000000000000001000
        (0000000000000000000000000000000000000000000000000000000011111111 & 1111111111111111111111111111111111111111111111111111111111100011) | 0000000000000000000000000000000000000000000000000000000000001000
        0000000000000000000000000000000000000000000000000000000011100011 | 0000000000000000000000000000000000000000000000000000000000001000
        return 0000000000000000000000000000000000000000000000000000000011101011
    */
}

// prints out the binary representation of a value
void printBinary(long long int x, size_t size)
{
    int i;
    // starts at the leftmost bit and goes to the rightmost, using getbits to obtain the value, and printing it accordingly
    for(i = size * 8 - 1; i >= 0; i--)
    {
        if (getbits(x, i, 1) == 1)
            printf("1");
        else
            putchar('0'); // printf("0"); was here but clc-wiki <c> code blocks apparently don't allow "0" unless it is in a comment. Bug?

        // this improves readability, but not required
        if(i % 4 == 0)
            printf(" ");
    }
    printf("\n");
}

// get n bits from position p. Does not support negative numbers for p or n, p is zero based index
// doesn't seem to care if right shift is arithmetic or logical. Returns -1 if p and/or n is invalid
long long int getbits(long long int x, unsigned char p, unsigned char n)
{
    size_t size = sizeof(x) * 8;

    // set's the shift size based on the zero based index position p minus the length of n bits.
    // this is used by (x >> shift) to get the desired bits in the rightmost position for the bitwised AND
    char shift = p + 1 - n;

    // if zero based index p is greater than or equal to size, it is invalid
    // if the shift is negative, it is invalid since the n bits requested at position p go past the least signifiacnt bit of x
    if (p >= size || shift < 0)
        return -1;
    // if asking for all bits, return x since left shift doesn't work when shift size is number of bits
    else if (n == size && shift == 0)
        return x;

    // first, the shift gets the desired bits to the rightmost position. Next, 0 is inversed by the bitwised one's complement.
    // this value is shifted to the left by n bits (adds in n zeros to the rightmost side). Then this value is bitwised one's complement
    // once more, making the n zero bits ones and the rest zeros. This is a mask that will turn off everything but the rightmost n bits
    // finally, the updated x it bitwised AND with the mask to turn off (change to 0) everything but the rightmost n bits where are left alone
    return (x >> shift) & ~(~0ULL << n);
    /*
        For example, this is how you could get the last four bits of a number:
        getbits(197, 3, 4);

        size = sizeof(x) * 8
        size = 8 * 8
        size = 64

        shift = p + 1 - n
        shift = 3 + 1 - 4
        shift = 0

        // passes checks
        
        (x >> shift) & ~(~0ULL << n)
        (197 >> 0) & ~(~0ULL << 4)
        (0000000000000000000000000000000000000000000000000000000011000101 >> 0) & ~(~(0000000000000000000000000000000000000000000000000000000000000000) << 4)
        (0000000000000000000000000000000000000000000000000000000011000101 >> 0) & ~(1111111111111111111111111111111111111111111111111111111111111111 << 4)
        (null -> 0000000000000000000000000000000000000000000000000000000011000101 = 0000000000000000000000000000000000000000000000000000000011000101) & ~(1111111111111111111111111111111111111111111111111111111111111111 <- 0000 = 1111111111111111111111111111111111111111111111111111111111110000)
        0000000000000000000000000000000000000000000000000000000011000101 & ~(1111111111111111111111111111111111111111111111111111111111110000)
        0000000000000000000000000000000000000000000000000000000011000101 & 0000000000000000000000000000000000000000000000000000000000001111
        0000000000000000000000000000000000000000000000000000000000000101;
        return 5
    */
}

Solution by Foowar

/*
 * Exercise 2-6:
 *
 * 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 int
setbits(unsigned int x, int p, int n, unsigned int y)
{
	unsigned int mask;

	mask = ~(~0 << n);
	mask <<= p+1-n;

	y <<= p+1-n;

	y &= mask;
	x &= ~mask;

	return x | y;
}
Personal tools