маска и агрегированные биты

Question

Я пытаюсь эффективно выполнить следующую задачу:

INPUT VALUE: 01101011 
MASK:  00110010 
MASK RESULT: --10--1- 
AGGREGATED: 00000101 

Я надеюсь, что это объясняет примеры ясно, что я пытаюсь добиться. Каков наилучший способ сделать это не наивным способом?

Answer 1

Эта операция называется compress_right или просто compress, и она умеренно ужасна для реализации без аппаратной поддержки. Не наивный код из Восторга Хакера «7-4 компресса или обобщенного Extract» для реализации этой функции является

unsigned compress(unsigned x, unsigned m) { 
    unsigned mk, mp, mv, t; 
    int i; 
    x = x & m; // Clear irrelevant bits. 
    mk = ~m << 1; // We will count 0's to right. 
    for (i = 0; i < 5; i++) { 
     mp = mk^(mk << 1); // Parallel suffix. 
     mp = mp^(mp << 2); 
     mp = mp^(mp << 4); 
     mp = mp^(mp << 8); 
     mp = mp^(mp << 16); 
     mv = mp & m;  // Bits to move. 
     m = m^mv | (mv >> (1 << i)); // Compress m. 
     t = x & mv; 
     x = x^t | (t >> (1 << i)); // Compress x. 
     mk = mk & ~mp; 
    } 
    return x; 
} 

BMI2 (реализовано в Haswell и позже) будет иметь инструкции pext для этой операции.

---

Если маска является постоянным (или не является постоянной, но повторно несколько раз), сравнительно очевидно, оптимизация предварительного расчета 5 значений, которые принимает mv во время цикла. Расчет mv не зависит от x, так что можно вычислить independantly, как этот (тот же алгоритм, как указано выше, на самом деле)

mk = ~m << 1; 
for (i = 0; i < 5; i++) { 
    mp = mk^(mk << 1); 
    mp = mp^(mp << 2); 
    mp = mp^(mp << 4); 
    mp = mp^(mp << 8); 
    mp = mp^(mp << 16); 
    mv = mp & m; 
    mask[i] = mv; 
    m = m^mv | (mv >> (1 << i)); 
    mk = mk & ~mp; 
} 

Тем не менее выглядит сложным, но все здесь является константой, поэтому она может быть предварительно (если компилятор не может этого сделать, то вы можете, просто выполнив его, а затем вставив результат в код). «Реальная часть» кода, код, который на самом деле должен работать во время выполнения заключается в следующем:

x = x & m; 
t = x & mask[0]; 
x = x^t | (t >> 1); 
t = x & mask[1]; 
x = x^t | (t >> 2); 
t = x & mask[2]; 
x = x^t | (t >> 4); 
t = x & mask[3]; 
x = x^t | (t >> 8); 
t = x & mask[4]; 
x = x^t | (t >> 16); 

(это также в Делайт Хакера, отформатированных немного по-другому)

Во многих случаях может быть проще опять же, например:

• если m = 0, результат 0.
• если m = -1, результат x.
• если m = 1, результат x & 1.
• если m = ((1 << n) - 1) << k, результат (x >> k) & m.
• если m = 0x80000000, результат x >> 31.
• если m является другой степенью двойки, результат (x >> numberOfTrailingZeros(m)) & 1
• если m переменный, можно использовать «идеальный unshuffle алгоритм».
• Если m состоит из нескольких «групп», можно использовать алгоритм «перемещение группы бит» (т. Е. Маскировать группу, сдвигать ее на место (или сначала сменять, маскировать вторую), либо все сдвинутые группы вместе, хотя больше существуют сложные подходы), это, вероятно, самый важный случай на практике.
• ...

Например, маска из вашего вопроса будет падать в «группе битов перемещения» случай, с кодом, как это:

return ((x >> 1) & 1) | ((x >> 3) & 6);