creating int from contiguous bits in an int

Discussion in 'C Programming' started by Digital Puer, Nov 26, 2005.

  1. Digital Puer

    Digital Puer Guest

    I'd like to be able to create an integer from a range of contiguous
    bits
    in another integer. I'm on a big-ending machine, in case that matters.
    I would ideally like to create a function with this prototype:

    unsigned long long extractValue(unsigned long long target, int a, int
    b)

    where a and b are the range of bits counted off from the most
    significant
    bit (where the msb is the 0th bit). For instance, 12345678900 is

    00000000 00000000 00000000 00000010 11011111 11011100 00011100
    00110100

    A call to extractValue(value, 32, 35) should result in 13 (1101 in
    binary).

    Can someone please help?
    Digital Puer, Nov 26, 2005
    #1
    1. Advertising

  2. Digital Puer

    Skarmander Guest

    Digital Puer wrote:
    > I'd like to be able to create an integer from a range of contiguous
    > bits
    > in another integer. I'm on a big-ending machine, in case that matters.
    > I would ideally like to create a function with this prototype:
    >
    > unsigned long long extractValue(unsigned long long target, int a, int
    > b)
    >
    > where a and b are the range of bits counted off from the most
    > significant
    > bit (where the msb is the 0th bit). For instance, 12345678900 is
    >
    > 00000000 00000000 00000000 00000010 11011111 11011100 00011100
    > 00110100
    >
    > A call to extractValue(value, 32, 35) should result in 13 (1101 in
    > binary).
    >
    > Can someone please help?
    >

    You've chosen an unhelpful way of specifying the bits you want. :)

    The idea is that we shift enough bits to the left for the desired MSB to
    be the actual MSB, then shift back to make the desired LSB the actual
    LSB, losing undesired bits in the overflow. This can be done in one
    expression, but I'll do it in more for clarity.

    #include <limits.h>

    unsigned long long extractValue(unsigned long long target, int msb,
    int lsb) {
    const size_t ull_bits = CHAR_BIT * sizeof(unsigned long long);
    unsigned long long result;
    if (msb > lsb) {
    /* empty range */
    result = 0;
    } else {
    /* shift the desired msb to the actual msb */
    result = target << msb;
    /* there are (lsb - msb + 1) bits in the range, shift them
    from high to low */
    result >>= ull_bits - (lsb - msb + 1);
    }
    return result;
    }

    This function does not check if the arguments are in range; it assumes
    you know what bits you can access.

    S.
    Skarmander, Nov 26, 2005
    #2
    1. Advertising

  3. Digital Puer

    Joe Wright Guest

    Digital Puer wrote:
    > I'd like to be able to create an integer from a range of contiguous
    > bits
    > in another integer. I'm on a big-ending machine, in case that matters.
    > I would ideally like to create a function with this prototype:
    >
    > unsigned long long extractValue(unsigned long long target, int a, int
    > b)
    >
    > where a and b are the range of bits counted off from the most
    > significant
    > bit (where the msb is the 0th bit). For instance, 12345678900 is
    >
    > 00000000 00000000 00000000 00000010 11011111 11011100 00011100
    > 00110100
    >
    > A call to extractValue(value, 32, 35) should result in 13 (1101 in
    > binary).
    >
    > Can someone please help?
    >

    I'll try.
    First though, why declare msb the 0th bit? It seems arbitrary and
    counterintuitive in C where we think of the lsb as the 0th. Endianess
    does not seem to be an issue.

    Using 32 and 35 calculate that you need a four-bit mask and create it.

    00000000 00000000 00000000 00000000 00000000 00000000 00000000 00001111

    Now shift 'value' right such that the four bits of interest are the
    least significant. Now 'and' the shifted value with the mask. Voila, 13.

    --
    Joe Wright
    "Everything should be made as simple as possible, but not simpler."
    --- Albert Einstein ---
    Joe Wright, Nov 26, 2005
    #3
  4. Digital Puer

    Digital Puer Guest

    Skarmander wrote:
    > You've chosen an unhelpful way of specifying the bits you want. :)


    What's a better way of specifying the bits?



    > unsigned long long extractValue(unsigned long long target, int msb,
    > int lsb) {



    thank you. This works perfectly.
    Digital Puer, Nov 26, 2005
    #4
  5. Digital Puer

    Digital Puer Guest

    Joe Wright wrote:

    > I'll try.
    > First though, why declare msb the 0th bit? It seems arbitrary and
    > counterintuitive in C where we think of the lsb as the 0th.


    Sorry. I guess I'm thinking of the bit representation as a
    character array, so '0010' would have the '1' bit in the
    array[2] position. That's probably not too helpful.



    >
    > Using 32 and 35 calculate that you need a four-bit mask and create it.
    >
    > 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00001111
    >
    > Now shift 'value' right such that the four bits of interest are the
    > least significant. Now 'and' the shifted value with the mask. Voila, 13.
    >



    Thank you for the insight. Here's an implemention based on
    your suggestion.


    unsigned long long extract(unsigned long long target, int msb, int lsb)
    {
    int mask_size = lsb - msb + 1;
    unsigned long long mask;
    unsigned long long result;
    int ull_size = CHAR_BIT * sizeof(unsigned long long);

    mask = (1 << mask_size) - 1;
    target >>= (ull_size - lsb - 1);
    result = mask & target;

    return result;

    }
    Digital Puer, Nov 26, 2005
    #5
  6. Digital Puer

    Skarmander Guest

    Digital Puer wrote:
    > Skarmander wrote:
    >
    >>You've chosen an unhelpful way of specifying the bits you want. :)

    >
    >
    > What's a better way of specifying the bits?
    >

    Well, bits are usually numbered from the LSB, starting at 0. Also, a
    range specified by its ends needs checking to handle the case when it's
    empty. An easier function to write would be

    unsigned long long extractBits(unsigned long long source, int low,
    int count) {
    return (source >> low) && ((1ull << count) - 1);
    }

    Shorter, clearer, and it doesn't actually need to know how many bits are
    in an unsigned long long. But, of course, this may not be what you need
    at all, and may instead make things more difficult at the calling end. I
    was just making the observation that *if* I had been free to write the
    function as conveniently as possible, this would be its interface. :)

    S.
    Skarmander, Nov 27, 2005
    #6
  7. Digital Puer

    Michael Mair Guest

    Digital Puer wrote:
    > Skarmander wrote:
    >
    >>You've chosen an unhelpful way of specifying the bits you want. :)

    >
    > What's a better way of specifying the bits?


    Specify them as you do with decimal digits
    42 base 10
    means
    4 * 10^1 + 2 * 10^0

    Just in the same way,
    10 base 2
    means
    1 * 2^1 + 0 * 2^0

    You can leave out leading digits evaluating to zero.
    So, if talking about bit 0 (the binary digit associated
    with 2^0), everyone knows that it is the least
    significant bit and toggles +0/+1 -- irrespective of the
    absolute number of available bits.
    So, you'd rather go at it like that:
    binary ... x ... 1 0 1 1
    bit no ... n ... 3 2 1 0

    Cheers
    Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
    Michael Mair, Nov 27, 2005
    #7
  8. Digital Puer wrote:
    > I'd like to be able to create an integer from a range of contiguous
    > bits
    > in another integer. I'm on a big-ending machine, in case that matters.
    > I would ideally like to create a function with this prototype:
    >
    > unsigned long long extractValue(unsigned long long target, int a, int
    > b)
    >
    > where a and b are the range of bits counted off from the most
    > significant
    > bit (where the msb is the 0th bit). For instance, 12345678900 is
    >
    > 00000000 00000000 00000000 00000010 11011111 11011100 00011100
    > 00110100
    >
    > A call to extractValue(value, 32, 35) should result in 13 (1101 in
    > binary).
    >
    > Can someone please help?


    It's easier going from the lsb rather than the msb, because it makes
    the shifting easier. Then you have:

    unsigned long long
    extractValue(unsigned long long target, int a, int b)
    {
    return (target >> a) & ~(~0ULL << (b - a + 1));
    }

    Rewriting this to work going from the msb is left as an exercise to the
    reader.

    Gregory Pietsch
    Gregory Pietsch, Nov 28, 2005
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. cppaddict

    creating an int from bits

    cppaddict, May 8, 2004, in forum: C++
    Replies:
    19
    Views:
    4,368
    David Harmon
    May 14, 2004
  2. GGG
    Replies:
    10
    Views:
    12,510
    Donar
    Jul 6, 2006
  3. Schnoffos
    Replies:
    2
    Views:
    1,196
    Martien Verbruggen
    Jun 27, 2003
  4. Hal Styli
    Replies:
    14
    Views:
    1,613
    Old Wolf
    Jan 20, 2004
  5. Vish
    Replies:
    3
    Views:
    680
    Lawrence Kirby
    Apr 29, 2005
Loading...

Share This Page