Function that extracts bits from an unsigned int

Question

Write a function called bitpat_get() to extract a specified set of bits. Have it take three arguments: the first an unsigned int, the second an integer starting bit number, and the third a bit count. Using the convention that bit numbering starts at 0 with the leftmost bit, extract the specified number of bits from the firstargument and return the result. So the call

bitpat_get(x, 0, 3)

extracts the three leftmost bits from . The call

bitpat_get(x, 3, 5)

extracts five bits starting with the fourth bit in from the left.

I didn't really know what the author meant by extracting bits, so I'm almost certain that my code is wrong and whatever it returns is not the intended return value. However, I'll post it anyway:

#include <stdio.h>

unsigned int bitpat_get(unsigned int from, int start, int n);

int main(void)
{
    unsigned int x = 0xe1f4;

    printf("%x\n", bitpat_get(x, 0, 3));
    printf("%x\n", bitpat_get(x, 3, 5));
}

unsigned int bitpat_get(unsigned int from, int start, int n)
{
    unsigned int result = from;
    int bits;

    for (bits = 0; (from >> bits) != 0; ++bits)
        continue;

    unsigned int mask = (((1U << n) - 1) << (bits - n - start));

    result = from ^ mask;

    return result;
}

Output:

1f4
fef4

@davernator that's true, it helped me understand bit manipulation better, even though I the result I arrived at turned out to be wrong. — Areg Sarvazyan
Very good @Areg. Also, it has been my experience that a good benchmark (instance with a known result) can help you debug the code. The probability that your code is correct vastly increases if it produces correct results on a known set of data. — davernator
@davernator of course. However, since I'm unsure as to what the author meant by to extract a specified set of bits, so I'm not very sure what a good benchmark would be. — Areg Sarvazyan
That can happen, can't it @Areg (:-). If you have contact info for the author, maybe you can email him/her. A good related google might be to see what there is about the shift operators << and >>, and how they operate on systems with little endian vs big endian architecture. Very pertinent, but maybe overkill depending on how deep a dive you want to take. (:-) — davernator

paxdiablo paxdiablo · Accepted Answer · 2018-03-19T00:51:40

I didn't really know what the author meant by extracting bits.

Let's solve this bit first. Say you have a 16-bit unsigned integer, the bit positions would be:

                     1 1 1 1 1 1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

So the expression bitpat_get(x, 0, 3) should give you the three bits starting at offset zero, or abc. Similarly, bitpat_get(x, 3, 5) would give you the five bits at offset three, or defgh.

That should be enough to understand what you need to do.

In terms of what you need to do to achieve this, it's a two-step operation. The first is to actually shift the bits right^(a) so that the ones you need are in the rightmost positions. This depends on three pieces of information:

the bit width of the unsigned int;
the offset where you want to extract; and
the number of bits you wish to extract.

The distance to shift is bitWidth - offset - bitsNeeded. For your first case, that would be 16 - 0 - 3 = 13 and you can see that shifting the bits right by thirteen would place the desired bits in the rightmost section:

                     1 1 1 1 1 1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|0|0|0|0|a|b|c|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

For your second case, right shifting by 16 - 3 - 5 = 8 gives you:

                     1 1 1 1 1 1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|a|b|c|d|e|f|g|h|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The second step is to mask out the bits on the left that you don't actually need. We'll do the second case first since that has an actual effect.

The mask is basically a series of one-bits on the right, and can be obtained by starting with zero and left shifting in a one bit for each bit position you need. For the case where we need five bits, the sequence would be binary 0, 1, 11, 111, 1111, and 11111. Bitwise and-ing that with the value would give:

                     1 1 1 1 1 1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|a|b|c|d|e|f|g|h| <- value
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|0|0|1|1|1|1|1| <- "and" with
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|0|0|d|e|f|g|h| <- gives
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

For the first case where we need three bits, the mask will be binary 111 so will have no effect on the original value since all the left-most bits are already zero.

Note that you don't need to do this in a loop since, as your code shows, you can calculate it with a single expression 2ⁿ - 1:

unsigned mask = (1U << n) - 1U;

In terms of the code you've posted, I see a few problems.

First, I think your for..continue section is meant to find out the bit width of the unsigned int, based on your later use of the value. However, you calculate it based on the value passed in, which is incorrect. What you should base it on is a bit pattern where the left-most bit is one.

In other words, think about what your current loop will do if the value you pass in is three (binary 11) - the bit width will be calculated as two because you'll end up with a zero value after only two shifts. So, a better way to do it would be:

unsigned testVal = ~0U; // all one bits
for (bits = 0; testVal != 0; ++bits, testVal = testVal >> 1)
    ;

Second is your mask calculation. Your code is set up to extract the bits in-place, meaning you will just set all the other bits to zero around them. It would be better to shift them to the right for extraction^(a).

Thirdly, you should be aware that ^ is the xor operation which, if you use with a mask of all one bits, will invert the bits rather than extracting them as-is. The operator you're looking for is &.

By way of example, using the xor operator with bitpat_get(21, 11, 5) would give:

                     1 1 1 1 1 1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|0|0|1|0|1|0|1| <- value (21)
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|0|0|1|1|1|1|1| <- "xor" with
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|0|0|0|1|0|1|0| <- `01010` (10): NOT the correct `10101`
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Having said all that, I would have written the function as something like:

unsigned bitpat_get(unsigned from, unsigned start, unsigned count) {
    // Only need calculate this once, first time it's called.

    static unsigned bitWidth = 0;
    if (bitWidth == 0) {
        unsigned testVal = ~0U;
        while (testVal != 0) {
            bitWidth++;
            testVal = testVal >> 1;
        }
    }

    // Get the value you need to shift by.

    unsigned shiftCount = bitWidth - start - count;

    // Use this line if in-place bits needed.
    // unsigned mask = ((1U << count) - 1U) << shiftCount;

    // Or use these two lines if you need it on the right.
    from = from >> shiftCount;
    unsigned mask = (1U << count) - 1U;

    // Mask and return the bits.

    unsigned result = from & mask;

    return result;
}

The only tricky bit there is the use of a static bitWidth so it only needs to be calculated once. This is just an optimisation to speed things up in subsequent calls. If you don't want that (such as if you're not comfortable with the concepts, or if it's possible this function may be called the first time from multiple threads concurrently, causing a data race), simply replace it with:

unsigned bitWidth = 0;
unsigned testVal = ~0U;
while (testVal != 0) {
    bitWidth++;
    testVal = testVal >> 1;
}

^(a) This is based on experience. It's possible that you may want them in-place but, in my long and (occasionally) illustrious career, I've always found it more useful to have them in the shifted section. For example, if bits 11-13 are an integral value of some sort, moving them to the right-most bits actually gives you the value 0..7 rather than a value from the set {0, 4, 8, ..., 28}.

That may not be the case, so the code I've provided covers both cases if you just comment out the alternate case.

Function that extracts bits from an unsigned int

1 Answers