2 ms·

Bit Manipulation Brain Teaser

• deleted 17y ago
  [deleted]
• paulbaumgart 17y ago
  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
  • deleted 17y ago
    [deleted]
  • mightybyte 17y ago
    Yeah, the diagonal flip is really the whole point of the problem. Horizontal and vertical are just warm-ups.
    • paulbaumgart 17y ago
      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.
      • mightybyte 17y ago
        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.