Transformations on a game board represented as a bitset

I’m using a long as a bitset to represent a game board. If a field is set (X) the corresponding bit is set, if it’s empty (-), it’s not. The fields are numbered from left to right starting from 0.

For example, the following board

0 1 2       X - X
3 4 5       - X -
6 7 8       X - X

becomes 1 * 2^0 + 1 * 2^2 + 1 * 2^4 + 1 * 2^6 + 1 * 2^8 = 341.

This has the limitation that it can only support boards with < 64 fields (which is fine).

The following are some methods to transform the board, i.e. mirror it horizontally, vertically and along each diagonal, as well as rotate it clockwise by 180, 90 and 270 degrees (the latter two only make sense for quadratic boards; I omitted the code to check for this here).

int h;    // height of the board
int w;    // width of the board
long val; // binary representation

// The field at (x, y) is the nth bit with n = y * width + x.

// mirror the board vertically along its centre
void fliplr() {
  for (int j = 0; j < h; j++) {
    for (int i = 0; i < w / 2; i++) {
      swap(i, j, w - 1 - i, j);
    }
  }
}

// mirror the board horizontally along its centre
void flipud() {
  for (int j = 0; j < h / 2; j++) {
    swapRow(j, h - 1 - j);
  }
}

// mirror the board along its first diagonal (top left to bottom right)
void flipd1() {
  for (int i = 1; i < h; i++) {
    for (int j = 0; j < i; j++) {
      swap(i, j, j, i);
    }
  }
}

// mirror the board along its second diagonal (top right to bottom left)
void flipd2() {
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w - 1 - i; j++) {
      swap(i, j, h - 1 - j, w - 1 - i);
    }
  }
}

void rotate180() {
  flipud();
  fliplr();
}

void rotate270() {
  long tmp = 0;
  for (int j = 0; j < h; j++) {
    for (int i = 0; i < w; i++) {
      tmp = set(tmp, w - i - 1, j, get(i, j));
    }
  }
  val = tmp;
}

void rotate90() {
  long tmp = 0;
  for (int j = 0; j < h; j++) {
    for (int i = 0; i < w; i++) {
      tmp = set(tmp, i, h - j - 1, get(i, j));
    }
  }
  val = tmp;
}

long set(long val, int y, int x, long newVal) {
  long mask = 1L << (y * w + x);
  return (val & ~mask) | ((newVal << (y * w + x)) & mask);
}

void swap(int x1, int y1, int x2, int y2) {
  swap(y1 * w + x1, y2 * w + x2);
}

// swap n bits starting from position b1 with n bits from b2
void swap(int b1, int b2, int n) {
  long xor = ((val >> p1) ^ (val >> p2)) & ((1L << n) - 1);
  val ^= ((xor << b1) | (xor << b2));
}
 
void swapRow(int r1, int r2) {
  swap(r1 * w, r2 * w, w);
}

My questions:

• Is there a more efficient way to perform the rotations? I believe
  rotation by 180 degrees should be possible in a single pass and 90
  and 270 without the need of a new variable but I couldn’t figure it
  out yet.
• Is there a better way to perform swapping and setting of bits?

EDIT, 2021-09-24: changed flipud to swap entire rows at once (instead of individual bits).

The questions / replacement algorithms

Is there a more efficient way to perform the rotations?

All the major rotate/flip/transpose operations on bitboards can be implemented efficiently as seen on chessprogramming.org. The way all of them work is by moving/swapping groups of bits at once, never single bits (which is really a waste of using bitboards: the point of bitboards is that they enable replacing slow bit-by-bit algorithm with the efficient multiple-bits-at-once algorithms). The code from chessprogramming.org is specialized for 8×8 boards, but could be used (with minor modifications) for any board to fits in an 8×8 square, though that requires a different representation than you are currently using (namely padding rows to 8 bits instead of a tight packing). Supporting any dimensions with 64 or fewer cells would be more difficult, but it shouldn’t be impossible, at the cost of implementing a handful of special cases..

I believe rotation by 180 degrees should be possible in a single pass and 90 and 270 without the need of a new variable but I couldn’t figure it out yet.

I feel like it should be possible, but I don’t think that makes sense as a metric. Especially not the number of variables, local variables are practically free. But “passes” are also a metric that doesn’t really fit bitboards. The efficient algorithms don’t really have “passes” at all, and even for the bit-by-bit algorithms it doesn’t set apart the good from the bad: for every rotation/flip/permutation and a given w and h there is an implementation that is just a single expression built up as a big bitwise-OR of w*h terms of “extract one bit from the board and shift it to its target position”. For most board sizes, that’s much worse than doing a handful of delta-swaps (a generalization of your swap function), but it satisfies the “single pass” and even “no new variable” criteria.

Is there a better way to perform swapping and setting of bits?

Not really, but they form an inherent bottleneck: they take wide 64-bit integer operations and force them to work on one or two bits at the time. Your swap function generalizes to swapNBits or a delta swap (depending on how it is generalized) which use a really similar sequence of operations but can perform a lot more work with it (this is how the efficient rotate/flip algorithms get their efficiency).

The code

One thing that really jumps out at me is that the swap-based methods repeatedly modify a field of the instance of the board they’re working with, rather than computing a value and then storing it. That makes the object transition through a succession of intermediate states during the most of the process, which is sometimes unavoiable, but when it is easily avoidable I think it should be avoided. Additionally, in my experience it’s often more efficient (or at least not slower) to implement this kind of code in the “compute a value and then store it”-way.