Bit Manipulation Brain Teaser | Hacker News Reader

Bit Manipulation Brain Teaser

softwaresimply.blogspot.com

15 pointsmightybyte4 comments

My attempt (it works when I run it in my head :-):

  const uint numBits = 3*numPieces;
  const u64 lowBits = ((1ULL << numBits)-1);
  const u64 highBits = lowBits << numBits;

  // Flip around horizontal axis
  flippedIndex = index ^ 4;

  // Flip around vertical axis
  flippedIndex = index ^ 2;

  // Flip around diagonal axis
  flippedIndex = (index & highBits) | ((index & lowBits) ^ lowBits) ^ ((index & highBits) >> numBits))

Edit: my last one ain't right

Yeah, the diagonal flip is really the whole point of the problem. Horizontal and vertical are just warm-ups.

  const uint numBits = 3*numPieces;
  const u64 lowBits  = ((1ULL << numBits)-1);
  const u64 highBits = lowBits << numBits;
  const u64 allFours = 04040404040404040404;
  const u64 allTwos  = 02020202020202020202;

  // Flip around horizontal axis
  flippedIndex = index ^ (allFours & lowBits);
  
  // Flip around vertical axis
  flippedIndex = index ^ (allTwos & lowBits);

Is my fix for the first two, but, as you point out, they're significantly easier.

The patterns are pretty neat, but I can't figure out how they result in any sort of rule for diagonal flipping.

The spirit of your answer is correct, but the code won't quite work the way the problem was stated. allFours should actually be 4444... and the same for allTwos. This way, it doesn't matter whether you keep the high and low bits together as I described or just concatenate the piece indices. Correct choices of the lowBits and highBits masks will handle the difference.

Reply on news.ycombinator.com