Эффективно отбрасывая 2 бита из 32-битного типа данных

Question

Предположим, у вас есть 32-битный тип данных:

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

Я веду журнал для наиболее эффективного способа «отбрасывать» биты в определенных местах, где удаление означает «удаление» данных битов и перемещениеследующие биты, чтобы заполнить его место.

Пример: Допустим, я хочу сбросить биты "a" и "q".Тогда результат должен выглядеть так:

bcdefghi jklmnopr stuvwxyz ABCDEF00

или

00bcdefg hijklmno prstuvwx yzABCDEF

Любой результат будет приемлемым.

В моем конкретном случае я также могу наложить следующееограничения:

• Позиции для отбрасывания являются статическими в моем случае;т.е. мне всегда нужно будет сбрасывать ровно 1-й и 16-й биты («a» и «q»)
• Биты, которые нужно отбросить («a» и «q»), всегда равны 0
• Биты, которые заканчиваются заполнением данных («00» слева или справа после операции), не имеют значения, т. Е. Не имеет значения, являются ли они на самом деле 0 или 1

В настоящее время я использую такой подход (псевдокод):

// 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
}

но мне интересно, есть ли какой-нибудь более умный / эффективный выход?

Answer 1

Вы можете сделать версию, в которой биты сбрасываются слева, используя 4 вместо 5 инструкций:

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

Обратите внимание на сдвиг вправо со знаком, который воспроизводит удаляемый бит, так что он отменяется вдобавить.

Answer 2

Я придумал это общее решение.Из того, что я вижу, должно быть 3 части.

Удаление битов 3 и 20 говорит.(на основе нуля)

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

Вам необходимо скрыть минимум.средние и высокие части, а затем сожмите их вместе.

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;
} 

Позвоните, используя что-то вроде

printf("Question q %x\n", remove_bits<1, 31>(0x12345678));

Answer 3

Вы можете сделать это по-другому:

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
}

Это короче и имеет преимущество в том, что оно более читабельно: понятно, какие биты выбрасываются из битовых масок.

Вы также можетесделать его однострочным:

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;
}

Что, возможно, более понятно, чем то, что ваше решение становится однострочным:

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;
}

Или, как предложено @greybeard (новсе еще, возможно, менее ясно):

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;
}

Answer 4

Упаковка справа немного проще, чем упаковка слева, так как нужно сдвинуть только 15 бит, а не два раза 15. Я не понимаю, как можно отказаться от маскировки, поэтому

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

Это не требует, чтобы отброшенные биты были равны нулю.Есть четыре побитовые операции, меньше будет трудно.

---

Существует три способа!

Добавьте 15 младших битов, чтобы сдвинуть их влево на одну позицию (умножается на2) и сдвиг вправо целого.

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

Внимание: бит 15 должен быть нулем.

Возможно, следующее выражение даст компилятору некоторые опции для лучшей генерации кода:

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

Стоит ли добавить, что возможна и другая окончательная компоновка?

(number + (unsigned short)number) << 1

Answer 5

Я думаю, что нет ничего проще, чем указанная реализация:

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;
}