In Running Bash on Ubuntu on Windows 10, I mentioned that I have been learning to program in C as part of a change of roles within the development team. I also mentioned that I have been doing so, primarily, via the book The C Programming Language 2nd Edition (also known as K&R).

This is a book that takes no prisoners. It was written in the days before the world-wide web, before personal computers were mainstream, when PCs didn’t always have permanent storage and when RAM was recorded in KBs. Modern high-level abstraction layers like .NET and the Java VM that manage your code and hide what is really happening under the hood didn’t yet exist.

If you were reading the K&R book in 1988 when it was first published, the chances are, therefore, that you were already a serious programmer with a keen interest in computing and already had some experience programming at such a low-level of abstraction — and it shows.

I’ve been using this book, on and off whilst also studying some of the other things that I need to learn for the new role. When doing so, I have been following along with the examples and exercises along the way. I’m only into the third chapter so far and already some of the exercises have already been devilishly difficult (at least for beginners).

Here’s the one of the most recent ones that I’ve been looking at, 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.

The solution to this involved chaining together multiple bitwise operations, but the exercise was preceded with only the briefest of introductions in bitwise operations. Perhaps other developers would take a different view, but bitwise operations strike me as the kind of thing that “modern” languages and platforms abstract away when possible. That is to say, that these are not the kind of problems that .NET developers such as myself encounter particularly often. They are also often the result of trying to cram as much information into as small a space as possible so as to consume fewer resources, such as RAM — again, the kind of thing that isn’t often much of a concern to developers in today’s world of cheap, fast and plentiful hardware.

So this is a new kind of problem and suffice it to say that the solution required a lot of thinking through. A less brutal book would have you practicing a few bitwise operations first. This style is both a blessing and a curse though; it certainly tests you, but when you arrive at a solution you feel like you’ve really achieved something and you will be all the better for it.

Anyway, on to the solution. I solved it first by writing two arbitrary 8-bit bytes, each representing an unsigned integer, on a piece of paper, in binary code form…

x-and-y-in-binary-uncoloured

…and then picking a value for p (4) and n (3) before highlighting the bits that I need to overwrite in x (red, below), and the bits that I need to overwrite them with from y (blue, below).

x-and-y-in-binary

The result, which I have called z, is shown below:

z-in-binary

So, I now had two steps that I knew needed to turn into code:

  1. Get the rightmost n bits from y
  2. Replace the n bits starting with p with the bits from step one

The book provides an example called getbits(x,p,n):

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

view raw
getbits.c
hosted with ❤ by GitHub

It occurred to me that this would do nicely for step 1 above (i.e. Get the first n bits from y). I also knew the signature for setbits() because the exercise brief defined it. I then set about coding all of this up:

/* 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, page 49 */
#include
unsigned setbits(unsigned x, int p, int n, unsigned y);
unsigned getbits(unsigned x, int p, int n);
int main()
{
printf("%u\n", setbits(209, 4, 3, 187));
}
/* getbits: get n bits from position p */
unsigned getbits(unsigned x, int p, int n)
{
return (x >> (p+1-n)) & ~(~0 << n);
}
/* setbits: replace bits p -> p+n of x with rightmost n bits from y */
unsigned setbits(unsigned x, int p, int n, unsigned y)
{
int bits, result;
bits = getbits(y, n-1, n);
/* result = ; */
return result;
}

view raw
setbits-pt1.c
hosted with ❤ by GitHub

I could now retrieve the bits that I needed, so I then moved onto step 2 (i.e. Replace the n bits starting with p with the bits from step one).

I studied the bitwise operators in the book and came to the conclusion that there wasn’t a single one that could do what I wanted.

The bitwise operators are as follows:

  • & (bitwise AND)
  • | (bitwise inclusive OR)
  • ^ (bitwise exclusive OR)
  • << (left shift)
  • >> (right shift)
  • ~ (one’s complement)

This was going to require multiple sub-steps, combining multiple bitwise operations.

If you use bitwise AND (e.g. a = b & c) then all bits that are equal to 1 in both operands will be set to 1 in the result, with every other bit being set to 0 (see examples below):

bitwise-AND

If you use bitwise inclusive OR (e.g. a = b | c) then all bits that are set to 1 in either of the two operands are set to 1, with every other bit being set to 0 (see examples below):

bitwise-OR

If you use bitwise exclusive OR (e.g. a = b ^ c) then bits are set to 1 in the result only if they differ in both operands, with every other bit being set to 0

bitwise-XOR

The left shift and right shift operations move the bits left and right respectively, replacing the vacated bits with 0s

bitwise-shift

The one’s complement operation (e.g. a = ~b) reverses all bits

bitwise-ones-complement

From here I could work backwards to find the solution. I needed to end up in a position where I could use the bitwise inclusive OR operation on a version of x with bits 4, 3 & 2 set to 0 and a new variable with the n bits from y, as follows:

x-y-z-bitwise-OR

In order to get to that I needed to do two things: shift the bits from to the left by the difference between of p+1 and n, and then mask off the required bits from y.

I added the following line after getbits() in order to shift the result to the left:

bits = bits << (p+1-n);

Masking off the bits in x was a bit more tricky, but I achieved as follows:

  • create a new unsigned int variable and set it to the one’s complement of 0 (all bits set to 1)
  • shift the bits to the left by a factor of n (all bits set to 1 apart from the first n which are 0s.
  • perform a one’s complement on the mask and shift the bits left by a factor of p+1-n (all bits will now be set to 0 apart from the n bits starting at p which will be set to 1s)
  • perform another one’s complement on the mask (all bits will now be set to 1s apart from the n bits starting at p which will be set to 0s)
  • and then finally perform a bitwise AND between the new x and the mask.

The code for the above looked like this:

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

Now I had the bits and the new x, all that I had to do was the final bitwise OR

return x | bits;

The final solution has been embedded below:

/* 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, page 49 */
#include <stdio.h>
unsigned setbits(unsigned x, int p, int n, unsigned y);
unsigned getbits(unsigned x, int p, int n);
int main()
{
unsigned x, y;
int p, n;
x = 209U;
p = 4;
n = 3;
y = 187U;
printf("%u\n", setbits(x, p, n, y));
}
/* getbits: get n bits from position p */
unsigned getbits(unsigned x, int p, int n)
{
return (x >> (p+1-n)) & ~(~0 << n);
}
/* setbits: replace bits p -> p+1-n of x with rightmost n bits from y */
unsigned setbits(unsigned x, int p, int n, unsigned y)
{
unsigned bits, mask;
/* get the rightmost n bits from y and shift them to position p */
bits = getbits(y, n-1, n);
bits = bits << (p+1-n);
/* create a mask containing all 1s apart from bits p to p+1-n */
mask = ~0;
mask = mask << n;
mask = (~mask) << (p+1-n);
mask = ~mask;
/* mask off the bits in x that we want to overwrite */
x = x & mask;
/* return the overwritten bits in x */
return x | bits;
}

view raw
setbits-pt2.c
hosted with ❤ by GitHub

Of course, I could condense of this into fewer lines — into one line, even — but for the time being at least, I think  that it is easier understood as it is.