Поменяйте местами каждую пару битов - PullRequest
Новая
       16

Поменяйте местами каждую пару битов

7 голосов
/ 25 января 2011

Этот вопрос был задан представителем NVIDIA на ярмарке вакансий:

Напишите небольшой эффективный код, чтобы поменять каждую пару бит внутри байта;например, 10 11 01 10 должно стать 01 11 10 01.

Есть ли более «эффективный» способ сделать это, чем сделать цикл for через любой другой индекс?Мой код был маленьким, но я не представляю, насколько «эффективнее» это может быть, чем цикл ... Я предполагаю, что может быть способ использовать XOR, чтобы избежать цикла, но я не могуразберись.

Спасибо!

Ответы [ 6 ]

13 голосов
/ 25 января 2011

Как то так должно работать 

(i >> 1) & 01010101 + (i << 1) & 10101010

i >> 1 сдвигает все на 1 бит вправо, а & 01010101 оставляет только биты в четном положении.
Вторая часть имеет дело с нечетными битовыми позициями в одном и том же стиле.

Не уверен, насколько это эффективно.

12 голосов
/ 25 января 2011

Вы можете использовать таблицу поиска с 256 записями.

В качестве альтернативы, ((x & 0x55) << 1) | ((x & 0xAA) >> 1).

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

Без таблицы поиска (или прежде всего для создания объекта) вы также можете:

  • сдвиг влево и AND с левой битовой маской (10101010)
  • сдвиг вправо и AND с битовой маской справа (01010101)
  • ИЛИ результаты вместе.

10 11 01 10

смещено влево на 01 10 11 00 замаскированный с 10101010 дает нам 00 10 10 00

смещено вправо (оригинал) 01 01 10 11 замаскированный с 01010101 дает нам 01 01 00 01

ИЛИ наши результаты вместе

01 11 10 01

Так что в C или C ++ вы могли бы сделать 

unsigned char bitswap( unsigned char uch )
{
   return ((uch<<1) & 0xAA) | (uch>>1) & 0x55 );
}

Просто запустите это для всех значений от 0x00 до 0xff (убедитесь, что ваш цикл завершается!), Чтобы сгенерировать вашу «таблицу».

1 голос
/ 19 июля 2014

Для 32-битного интергера в Java. 

public int swapOddEvenbits(int x)
{
   return (  ((x & 0xaaaaaaaa) >> 1 | ((x & 0X55555555) << 1) );

}

Если вы работаете с 64-битной версией, вам нужно изменить маску.

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

Поиск в таблице (если нет какого-то конкретного решения для NVIDA, которое он искал).

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

Поскольку в байте всего 256 возможных комбинаций, это кажется хорошим кандидатом для использования решения на основе таблицы поиска в любое время, когда скорость непрерывного выполнения более важна, чем первоначальное предварительное вычисление и / или общее использование памяти.

Например: 

lookupTable[00000000] = 00000000
lookupTable[00000001] = 00000010
lookupTable[00000010] = 00000001
...
...