CODEWITHSUNDEEP
cbit-manipulationbitwise-operatorsbit-shift
Mourad Kejji
Mourad Kejji

Reputation: 71

How do I perform bitwise comparison on variables that are not the same size/type

I am currently doing a little problem solving challenge in C so here's my problem : I get to make a console program that gets Tetris pieces in standard input like this

.#..
.#..
.#..
.#..

..#.
###.
....
....

....
.##.
.##.
....

etc... (max 26 pieces)

and I have to figure out how to make them fit in the smallest possible square (without rotation) and the most top-left concentrated in order to output the following for the previous example :

ABB.
ABBC
ACCC
A...

(where letters are assigned by order of appearance).

So I figured the fastest way for my computer to test if a piece fits in a spot in the map is to perform bitwise & operation. If it gives 0, it fits.

That way I can check if a 

1100
1100
0000
0000

fits in :

1000
1000
1000
1000

I can just if (a & b == 0) and if it's true then it fits. Now my piece doesn't fit this way but if I shift it right it will :

b >> 1 = 
0110
0110
0000
0000

That way I can successively compare possible positions for a piece and put it on the map when I found a spot that fits.

My only problem is that my pieces are stocked in a short int (16 bit) and I have to compare it with a bigger type (for example a long long if my map is 8x8)0 Because it's easy to go from :

0110
0110
0000
0000

to 

0000
0000
0011
0011

just by shifting the bits but how can I get to this :

00000000
00110000
00110000
00000000
00000000
00000000
00000000
00000000

a 64 bit int with the same shape of 1's in a sea of 0's.

Upvotes: 4

Views: 394

Answers (2)

user694733
user694733

Reputation: 16033

When you use lesser type (short int) in bit shift operator, it is converted to int automatically. In your case this is not usually enough, but solution is simple:

First assign piece to bigger type, and then fix lines by bit masking and shifting. Then shift once more to move element into position you wish.

Also I recommend using unsigned integer types, as shifting on signed types is implementation defined at some cases. And while you are at it, I really recommend using uintN_t types from stdint.h.

So you'll need something like this:

// bool type is from stdbool.h
bool isPieceInMap(uint16_t piece, uint64_t map) {
    uint64_t bigPiece = piece;
    // Fix lines
    bigPiece = 
        (bigPiece & 0x000F) |
        (bigPiece & 0x00F0) << 4 |
        (bigPiece & 0x0F00) << 8 |
        (bigPiece & 0xF000) << 12;
    bigPiece = // Do position shifting as needed
    return (bigPiece & map) == 0;
}

Upvotes: 3

Patrick Roberts
Patrick Roberts

Reputation: 51756

Following up on @user694733's suggestion, here's an implementation to transpose a little piece to the lower-right quadrant of the big map:

uint64_t pieceToMap(uint16_t little) {
  static uint16_t row = 0b1111;
  uint64_t big = 0;

  for (char i = 0; i < 16; i += 4) {
    big |= (little & (row << i)) << i;
  }

  return big;
}

I've written a test program to confirm the algorithm works correctly:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

uint64_t pieceToMap(uint16_t);
void printPiece(uint16_t);
void printMap(uint64_t);

int main(int argc, char *argv[]) {
  uint16_t a = 0b0110011000000000;
  uint64_t b = pieceToMap(a);
  uint64_t c = b << 36;

  printPiece(a);
  printf("\r\n");
  printMap(b);
  printf("\r\n");
  printMap(c);

  return EXIT_SUCCESS;
}

uint64_t pieceToMap(uint16_t little) {
  static uint16_t row = 0b1111;
  uint64_t big = 0;

  for (char i = 0; i < 16; i += 4) {
    big |= (little & (row << i)) << i;
  }

  return big;
}

void printPiece(uint16_t little) {
  static uint16_t i = 1;
  char row, col;

  for (row = 3; row >= 0; row--) {
    for (col = 3; col >= 0; col--) {
      printf("%c", (little & (i << (row * 4 + col))) ? '1' : '0');
    }

    printf("\r\n");
  }
}

void printMap(uint64_t big) {
  static uint64_t i = 1;
  char row, col;

  for (row = 7; row >= 0; row--) {
    for (col = 7; col >= 0; col--) {
      printf("%c", (big & (i << (row * 8 + col))) ? '1' : '0');
    }

    printf("\r\n");
  }
}

The output, as I expected, is:

0110
0110
0000
0000

00000000
00000000
00000000
00000000
00000110
00000110
00000000
00000000

01100000
01100000
00000000
00000000
00000000
00000000
00000000
00000000

Upvotes: 2

Related Questions