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 */ }
