Exercise 2.6 - Setting bits at a position n¶

Question¶

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.

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

#include <stdio.h>

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

int main(void) { printf("%u", setbits((unsigned)12, 3, 2, (unsigned)57)); }

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

Explanation¶

The important piece of the program is this:

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

Let’s look at some inner terms. The expression ~(~0<<n) will thus always yield right most n bits set to 1. And (p+1-n) will give a integer value for the n digits at position p we want. We do p+1 because our position is 0 indexed while count of digits n is 1 indexed. For e.g. in a number 1111 1111, the 4 digits starting the position 3 is 1111

Let’s refactor the program to understandable portions.

RIGHT_MOST_N_1S = ~(~0 << n) GET_N_DIGITS = (p + 1 -n)

The above expression becomes:

(x & ~(RIGHT_MOST_N_1S << GET_N_DIGITS)) | (( y & RIGHT_MOST_N_1S) << GET_N_DIGITS);

For a moment, let’s take the word that left shifting operation will give us expected bits. For e.g: 0000 1111 << 4 will give us 1111 0000

Reducing it further, it becomes:

(x & ~(Expected bits marked as 1) | ((Right most bits in y) << GET_N_DIGITS);

(x & (Expected bits marked as 0) | (Expected bits marked as 1 in y and rest as 0);

So in x we switch off the expected bits by and ing it to 0. And and in y, we just get expected bits we want by and ing it to 1 and we OR the two expressions and thus get the result.

Why left shift?

We left shift because we want it from a position p.

Suppose we want two bits from position 4, we we need to our bit patterns to be like this:

0001 1000
7654 3210

In the above, from position 4, we have 2 bits set 1 and rest 0.

In order to do this, we get two bits at the right most position:

~(~0 << n)
0000 0011

And then we shift it by position 4 using the expression p+1-n:

~(~0 << n) << (4+1-n)
0011 << (5-2)
0011 << 3
0011 000
1000

So we determined our expected bits and we can follow the rest for the program.

Let’s get concrete and work out the program using the values:

x = 1111 1111 (= 255 )
p = 3
y = 0000 0000 (= 0)
n = 4

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

Right most 4 bits of y = 0000 So, we our return value should be:

= 1111 0000
= 240

Let’s follow how the program determines it. We take the LHS of |

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

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

(~0 << n)
      = (~ 0000 0000 << 4)
      = (1111 1111 << 4)
      = (1111 0000)

~(~0 << n)
  = ~(1111 0000)
  = 0000 1111

(~(~0 << n) << (p+1-n))
  = 0000 1111 << 0
  = 0000 1111

~(~(~0 << n) << (p+1-n))
          = ~ (0000 1111)
          = 1111 0000

(x & ~(~(~0 << n) << (p+1-n)))
          =  1111 1111 & 1111 0000
          =  1111 0000

Now we take the RHS of |

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

(p + 1 - n) = 0

~(~0 << n)  = 0000 1111

( y & ~(~0<<n))
    = 0000 0000 & 0000 1111
    = 0000 0000

(( y & ~(~0<<n)) << (p+1-n))
                = 0000 0000 << 4
                = 0000 0000

We write the entire expression:

(x & ~(~(~0 << n) << (p+1-n))) | (( y & ~(~0<<n)) << (p+1-n));
            = 1111 0000  | 0000 0000
            = 1111 0000

Converting 1111 0000 to decimal gives us 240 and that is answer.

Exercise 2.6 - Setting bits at a position n¶

Question¶

Explanation¶

Visualization¶