K&R Exercise 2-6 : Inserting part of a bitset into another

Question

"Inserting" part of a bitset into another

This is Exercise 2-6 on the K&R book, 2nd edition. The reader is asked to:

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.

Parameters Description

Here's what each parameter does informally:

• x -> serves as the "destination" bitset
• y -> serves as the "source" bitset
• p -> serves as the insertion point for the bits from y to be inserted on x
• n -> serves as the length of the segment to "cut" from y and replace in x

Special Notes

• I've tested with a number of different scenarios, and this code has passed all of them.
• At the bottom of the question there's an outline of a test-case and my logic behind solving the problem

Code

#include <stdio.h>
//setbits: returns x with n bits that begin at p set to the rightmost n bits of y
//informally: "chop" n bits right->left from y, insert on x at position p
unsigned setbits(unsigned x, int p, int n, unsigned y)
{
 return ((~(~0 << n) & y) << p) | ((~(~(~0 << n) << p)) & x);
}
int main(void) {
 // Example test cases:
 // First scenario:
 // x = 100 -> 0110 0100
 // y = 5 -> 0000 0101
 // p = 4
 // n = 3
 // Expected outcome: 0101 0100 (84)
 // Second scenario:
 // x = 94 -> 0101 1110
 // y = 195 -> 1100 0011
 // p = 0
 // n = 3
 // Expected outcome: 0101 1011 (91)
 // Third scenario:
 // x = 94 -> 0101 1110
 // y = 195 -> 1100 0011
 // p = 6 
 // n = 4
 // Expected outcome: 1101 1110 (222)
 printf("%d\n", setbits(100, 4, 3, 5));
 printf("%d\n", setbits(94, 0, 3, 195));
 printf("%d\n", setbits(94, 6, 4, 195));
 return 0;
}

Outline

problem outline
Click for full-size image

Answer 1

Avoid UB

Shifting a 1 into the sign position is undefined behavior (UB). (C11 §6.5.7 4) Instead, use unsigned types. 0 is an int constant. 0u is an unsigned constant.

// return ((~(~0 << n) & y) << p) | ((~(~(~0 << n) << p)) & x);
return ((~(~0u << n) & y) << p) | ((~(~(~0u << n) << p)) & x);

Clarity

Code for clarity and let the compiler form optimal code.

// return ((~(~0u << n) & y) << p) | ((~(~(~0u << n) << p)) & x);
unsigned new_mask = ~(~0u << n);
unsigned old_mask = ~(mask << p);
return ((new_mask & y) << p) | (old_mask & x);

Specifier matching

"%d" with unsigned should have raised a compiler warning/note. Enable all compiler warnings to avoid such easy to identify problems.

// printf("%d\n", setbits(100, 4, 3, 5));
printf("%u\n", setbits(100, 4, 3, 5));

For this task, using "%4x" would be more informative than "%u".

Wider testing

"I've tested with a number of different scenarios, and this code has passed all of them.". --> Testing with UINT_MAX, UINT_MAX-1, 1, 0 would help check out the "corners" of the function.

Document restrictions

Code limited to 0 <= p < bit_width and 0 <= n < bit_width. Since code cannot handle all possible input values, stating restrictions lessens incorrect usage.

Defining behavior for all possible inputs has the advantage of not needing to list limitations, yet may not be functional needed (and code over-kill).

Still good to post limitations.

On this last point, perhaps a slight code re-write is in order as one could easily expect n == bit_width to be valid.

// This assumes no padding in `unsigned`
#define UINT_BIT_WIDTH (CHAR_BIT * sizeof(unsigned))
unsigned setbits(unsigned x, int p, int n, unsigned y) {
 unsigned new_mask = n >= UINT_BIT_WIDTH ? UINT_MAX : ~(~0u << n);
 ...
}

• M. Lago: Thank you very much for such a detailed review! I must admit that I thought I was handling everything in unsigned terms, but I see how your correction is what is supposed to be done. I used variables like you stated for the next bitwise assignments, and I agree that it makes it more readable. The testing restrictions are actually a really good point that I don't usually think about, so thanks for pointing this out as well!
• chux: @M.Lago Note that the first issues also appears with all warnings enabled (conversion signed to unsigned). That would have mitigated the "thought I was handling everything in unsigned terms" issue.
• M. Lago: After some research, I found out that -Wall actually leaves some warnings out. Thanks!