Немного сдвиг столбца

Question

Как я могу сместить столбец в области 8x8?Например, у меня есть одно 64-битное целое число без знака следующим образом:

#include <boost/cstdint.hpp>

int main()
{
    /** In binary:
      * 
      * 10000000
      * 10000000
      * 10000000
      * 10000000
      * 00000010
      * 00000010
      * 00000010
      * 00000010
      */
    boost::uint64_t b = 0x8080808002020202;
}

Теперь я хочу сместить первую вертикальную строку, скажем, четыре раза, после чего она становится такой:

/** In binary:
  * 
  * 00000000
  * 00000000
  * 00000000
  * 00000000
  * 10000010
  * 10000010
  * 10000010
  * 10000010
  */

  b == 0x82828282;

Можно ли сделать это относительно быстро, используя только побитовые операторы, или что?

Answer 1

Моя лучшая догадка такова:

(((b & 0x8080808080808080) >> 4 * 8) | (b & ~0x8080808080808080)

Идея состоит в том, чтобы изолировать биты столбцов и сдвигать только их.

Answer 2

Можно ли сделать это относительно быстро, используя только побитовые операторы, или как?

Да.

Как вы это сделаете, будет зависеть от того, насколько «универсальным» вы хотите сделать решение. Всегда первый столбец? Всегда сдвигаться на 4?

Вот идея:

• Первые 4 байта представляют верхние 4 строки. Используйте это, зациклите на вершине 4.
• Замаскируйте первый столбец, используя 0x8, чтобы увидеть, установлен ли бит.
• Сдвиньте этот бит на 4 байта (>>4), конечно, для этого потребуется uint64.
• biwise- или (|) это против нового байта.

Вероятно, вы можете добиться большего успеха, избегая зацикливания и написания большего количества кода.

Answer 3

Для этого может быть инструкция SIMD.Вам придется включить эти инструкции в настройках VC ++, и, конечно, они не будут работать на архитектурах, отличных от процессоров AMD / Intel.

Answer 4

Полное предположение, так как у меня нет ни компилятора, ни Boost libs:

Учитывая b, col (считая от 1 до 8 справа) и shift (расстояние смещения) В вашем примере col будет 8, а shift будет 4.

boost::uint64_t flags = 0x0101010101010101;
boost::uint64_t mask  = flags << (col -1);
boost::int64_t eraser = -1 ^ flags;
boost::uint64_t data = b & mask;
data = data >> (8*shift)
b = (b & eraser) | data;

Answer 5

В этом случае вы хотите разделить значение на две части: первый столбец и другие столбцы. Сдвиньте первый столбец на соответствующую величину, затем объедините их вместе.

b = ((b & 0x8080808080808080)) >> (8*4) | (b & 0x7f7f7f7f7f7f7f7f)