Efficiently dropping 2 bits from a 32bit data type

▲
4
▼

Assume you have a 32bit data type:

// The letters are just to identify the position of each bit later in the post
abcdefgh ijklmnop qrstuvwx yzABCDEF

I'm logging for the most efficient way to "drop" bits at certain locations, where dropping means "removing" the given bits, and moving the following bits to fill in its place.

Example: Let's say I want to drop bits "a" and "q". Then the result should look either like:

bcdefghi jklmnopr stuvwxyz ABCDEF00

or

00bcdefg hijklmno prstuvwx yzABCDEF

Either result would be acceptable.

In my specific case, I can also impose the following constraints:

  • The positions to drop are static in my case; i.e. I will always need to drop exactly the 1st and 16th bit ("a" and "q")
  • The bits to be dropped ("a" and "q") are always 0
  • The bits that end up padding the data (the "00" to the left or right after the operation) don't matter - i.e., doesn't matter if they're actually 0 or 1

Currently I'm using an approach like this (pseudo-code):

// called with number = abcdefgh ijklmnop qrstuvwx yzABCDEF
auto drop_bits_1_16(unsigned int number)
{
    number = number << 1; // number becomes: bcdefghi jklmnopq rstuvwxy zABCDEF0
    unsigned number1 = number & 0xFFFE0000;  // number1 comes: bcdefghi jklmnop0 00000000 00000000

    unsigned number2 = number & 0x0000FFFF; // number2 becomes: 00000000 00000000 rstuvwxy zABCDEF0
    number2 = number2 << 1;  // number2 becomes: 00000000 0000000r stuvwxyz ABCDEF00

    return number1 | number2;  // returns bcdefghi jklmnopr stuvwxyz ABCDEF00
}

but I'm wondering if there's any more clever/efficient way out there?

c++
algorithm
bit-manipulation
asked on Stack Overflow Dec 21, 2018 by Bogey • edited Dec 21, 2018 by Nelfeal

5 Answers

▲
5
▼

Packing to the right is slightly easier than packing to the left, as only 15 bits have to move, instead of two times 15. I don't see how masking can be voided, so

((number & 0x7FFF0000) >> 1) | (number & 0x00007FFF)

This doesn't require the discarded bits to be zeroes. There are four bitwise operations, less will be difficult.

There is a way in three operations !

Add the 15 low-order bits to shift them left one position (multiplies by 2), and right shift the whole.

(number + (number & 0x7FFF)) >> 1

Caution: bit 15 must be a zero.

Maybe the following expression will give the compiler some options for better code generation:

(number + (unsigned short)number) >> 1

Should I add that the other final layout is also possible ?

(number + (unsigned short)number) << 1
answered on Stack Overflow Dec 21, 2018 by Yves Daoust • edited Dec 21, 2018 by Yves Daoust
▲
1
▼

You could do it the other way:

auto drop_bits_1_16(unsigned int number)
{
    unsigned number1 = number & 0x7FFF0000; // number1 becomes: 0bcdefgh ijklmnop 00000000 00000000
    unsigned number2 = number & 0x00007FFF; // number2 becomes: 00000000 00000000 0rstuvwx yzABCDEF
    number1 = number1 >> 1; // number1 becomes: 00bcdefg hijklmno p0000000 00000000

    return number1 | number2;  // returns 00bcdefg hijklmno prstuvwx yzABCDEF
}

That's shorter and has the advantage of being more readable: it's clear what bits are dropped from the bitmasks.

You can also make it a one-liner:

auto drop_bits_1_16(unsigned int number)
{
    return ((number & 0x7FFF0000) >> 1) | (number & 0x00007FFF);
    // Or, relying on operator precedence:
    // return (number & 0x7FFF0000) >> 1 | number & 0x00007FFF;
}

Which is arguably more clear than what your solution becomes as a one-liner:

auto drop_bits_1_16(unsigned int number)
{
    return ((number << 1) & 0xFFFE0000) | (((number << 1) & 0x0000FFFF) << 1);
    // Or, relying on operator precedence:
    // return number << 1 & 0xFFFE0000 | (number << 1 & 0x0000FFFF) << 1;
}

Or, as suggested by @greybeard (but still arguably less clear):

auto drop_bits_1_16(unsigned int number)
{
    return ((number << 1) & 0xFFFE0000) | ((number << 2) & 0x0001FFFC);
    // Or, relying on operator precedence:
    // return number << 1 & 0xFFFE0000 | number << 2 & 0x0001FFFC;
}
answered on Stack Overflow Dec 21, 2018 by Nelfeal • edited Dec 21, 2018 by Nelfeal
▲
1
▼

I came up with this generic solution. From what I can see there needs to be 3 parts.

Removing bits 3 and 20 say. (zero based)

3
1            v                     v  0
hhhh hhhh hhhx mmmm mmmm mmmm mmmm xlll

You need to mask out the low. medium and high parts, then squish them together.

template <size_t low, size_t hi> unsigned int remove_bits(unsigned int all)
{
    // static constants - my compiler pre-computes them.  They are the masks for
    // hhhh, mmmm and llll
    static const unsigned int lowMask = 0x7fffffff >> (31 - low);
    static const unsigned int middleMask = ((0xfffffffe << low) & (0x7fffffff >> (31 - hi) ));
    static const unsigned int highMask = 0xfffffffe << hi;

    // find the values in hhhh, mmmm, and llll
    unsigned int resLow = (all & lowMask);
    unsigned int resMiddle = (all & middleMask);
    unsigned int resHigh = (all & highMask);

    //////////////////////////////////////
    // combine the parts, shifted to the lower end.

    return resLow | resMiddle >> 1 | resHigh >> 2;
}

Call using something like 

printf("Question q %x\n", remove_bits<1, 31>(0x12345678));
answered on Stack Overflow Dec 21, 2018 by mksteve
▲
0
▼

I think there is nothing simpler than the specified implementation:

unsigned int drop_bits_16_32(unsigned int number)
{
    number <<= 1;
    unsigned int high = number & 0xFFFE0000;
    unsigned int low = (number & 0x0000FFFF) << 1;

    return high | low;
}
answered on Stack Overflow Dec 21, 2018 by snake_style
▲
0
▼

You can do the version where bits are dropped on the left with 4 instead of 5 instructions:

unsigned f1(unsigned x) {
    x <<= 1;
    return x + ((signed) (x << 15) >> 15);
}

Note the signed right shift which replicates the bit to be removed such that it cancels out in the add.

answered on Stack Overflow Dec 21, 2018 by Falk Hüffner • edited Dec 21, 2018 by Falk Hüffner

User contributions licensed under CC BY-SA 3.0