Преобразовать байт в конкретную маску с помощью битового хака - PullRequest
Новая
       31

Преобразовать байт в конкретную маску с помощью битового хака

1 голос
/ 31 января 2011

У меня есть номер с двоичным представлением 0000abcd.

Как преобразовать его в 0a0b0c0d с наименьшим количеством операций? Как конвертировать 0a0b0c0d обратно в 0000abcd?

Я искал решение здесь: http://graphics.stanford.edu/~seander/bithacks.html и другие

Как правило, проблема немного больше, чем описано.

Дано первое число a₁b₁c₁d₁a₂b₂c₂d₂ и второе число a₃a₄b₃b₄c₃c₄d₃d₄

Если (a₁ и a₂ = 0), очистите оба a₃ и a₄, если (a₃ и a₄ = 0), очистите оба a₁ и a₂ и т. Д.

Мое решение: 

    a₁b₁c₁d₁a₂b₂c₂d₂
OR  0 0 0 0 a₁b₁c₁d₁ ( a₁b₁c₁d₁a₂b₂c₂d₂ >> 4)
    ----------------
    0 0 0 0 a b c d
? (magic transformation)
    ? ? ? ? ? ? ? ?
    ----------------
    0 a 0 b 0 c 0 d
OR  a 0 b 0 c 0 d 0  (0 a 0 b 0 c 0 d << 1)
    ----------------
    a a b b c c d d
AND a₃a₄b₃b₄c₃c₄d₃d₄
    ----------------
    A₃A₄B₃B₄C₃C₄D₃D₄ (clear bits)

ОБНОВЛЕНО: (спасибо за @AShelly) 

x = a₁b₁c₁d₁a₂b₂c₂d₂
x = (x | x >> 4) & 0x0F
x = (x | x << 2) & 0x33
x = (x | x << 1) & 0x55
x = (x | x << 1)

y = a₃a₄b₃b₄c₃c₄d₃d₄
y = (y | y >> 1) & 0x55
y = (y | y >> 1) & 0x33
y = (y | y >> 2) & 0x0F
y = (y | y << 4)

работает для 32-битных с константами 0x0F0F0F0F, 0x33333333, 0x55555555 (и вдвое длиннее для 64-битных).

Ответы [ 4 ]

2 голосов
/ 31 января 2011

Если вы ищете наименьшее количество операций, используйте справочную таблицу.

0 голосов
/ 02 февраля 2011

У меня есть номер с двоичным представительство 0000abcd. Как конвертировать это 0a0b0c0d с наименьшим числом операции?

Разве это не точно " Чередование битов X и Y" , где Y равно 0? У хитов Bit Twiddling есть несколько решений , которые не используют справочную таблицу.

Как преобразовать 0a0b0c0d обратно в 0000abcd?

См. " Как удалить чередование битов (UnMortonizing?)"

0 голосов
/ 31 января 2011

Я думаю, что невозможно (без таблицы поиска) сделать это за меньшее количество операций, используя двоичную арифметику и архитектуру процессора x86 или x64.Поправь меня, если я ошибаюсь, но твоя проблема в перемещении битов.Имея abcd бит, вы хотите получить 0a0b0c0d бит за одну операцию.Проблема начинается, когда вы посмотрите, сколько битов должны пройти «a», «b», «c» и «d». 

'a' was 4-th, became 7-th, distance travelled 3 bits
'b' was 3-rd, became 5-th, distance travelled 2 bits
'c' was 2-nd, became 3-rd, distance travelled 1 bit
'd' was 1-st, became 1-st, distance travelled 0 bits

Нет такой инструкции процессора, которая будет перемещать этибиты динамически на другое расстояние.Хотя, если у вас есть разные входные представления одного и того же числа бесплатно, например, вы предварительно рассчитали несколько значений, которые вы используете в цикле, то, возможно, удастся добиться некоторой оптимизации, это эффект, который вы получаете при использовании дополнительных знанийо топологии.Вам просто нужно выбрать, будет ли это: 

[4 cycles, n^0 memory]
[2 cycles, n^1 memory]
[1 cycle , n^2 memory]
0 голосов
/ 31 января 2011

Вы не можете сделать это за один раз, вы должны сдвигать биты на основе битов:

Псевдокод: 

    X1 = a₁b₁c₁d₁
    X2 = a₂b₂c₂d₂
    Bm = 1 0 0 0 // Bit mask

    Result = 0;

    while (/* some bytes left */)
    {
       Result += (X1 and Bm) << 1 or (X2 and Bm);
       Bm = Bm shr 1
       Result = Result shl 2;
    }

В результате вы получите a1a2b1b2c1c2d1d2

...