A bit column shift

Question

How can I shift a column in 8x8 area? For example, I have this one 64-bit unsigned integer as follows:

#include <boost/cstdint.hpp>

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

Now, I want to shift the first vertical row let say four times, after which it becomes this:

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

  b == 0x82828282;

Can this be done relatively fast with only bit-wise operators, or what?

Answer 1

Can this be done relatively fast with only bit-wise operators, or what?

Yes.

How you do it will depend on how "generic" you want to make the solution. Always first column? Always shift by 4?

Here's an idea:

• The first 4 bytes represent the top 4 rows. Exploit that, loop over the top 4.
• Mask out the first column using 0x8, to see if the bit is set.
• Shift that bit over by 4 bytes (>>4), of course it'll need to be in a uint64 to do that.
• biwise-or (|) it against the new byte.

You can probably do better, by avoiding looping and writing more code.

Answer 2

My best guess is this:

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

The idea is to isolate the column bits and shift only them.

Answer 3

There might be a SIMD instruction for this. You'd have to turn on those instructions in your VC++ settings, and of course they won't work on architectures other than AMD/Intel processors.

Answer 4

In this case, you want to split the value into two pieces, the first column and the other columns. Shift the first column by the appropriate amount, then combine them back together.

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

Answer 5

Complete guess since I don't have a compiler nor Boost libs available:

Given b, col (counting 1 to 8 from right), and shift (distance of shift) In your example, col would be 8 and shift would be 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;