BitBoard rotation

[scozzese]

Ragazzi,

sto lavorando a un progetto in cui la massima efficenza è il centro di tutto. Ho una "board" (scacchiera) rappresentata a bits.
Quindi supponiamo che la scacchiera è una 4 * 4:

0 0 1 0
1 0 0 1
0 0 1 0
1 1 0 0

utilizzando BitSet essa apparirà come: 0010100100101100

Come è possibile ruotare la scacchierà di 90° utilizzando le operazioni logiche e di shift per ottenere questo risultato:

1 0 1 0
1 0 0 0
0 1 0 1
0 0 1 0

cioè: 1010100001010010

E' possibile ruotare la scacchiera anche di 45° gradi?

Vi ringrazio tutti in anticipo

[scozzese]

Sono riuscito a ruotare la matrice di 90°

               // Crea la scacchiera e assegna i valori positivi in alcune posizioni.
                BitSet board = new BitSet(16);
                 board.set(2);
		board.set(4);
		board.set(7);
		board.set(10);
		board.set(12);
		board.set(13);

               // Stampo la scacchiera
		for(int i = 0; i < 16; i ++) {
			boolean value = board.get(i);
			if(value == false) {
				System.out.print(0);
			} else {
				System.out.print(1);
			}

		}

		// Vertical rotation (90°right).
		BitSet newBoard = new BitSet(16);
		int indexOfShift = 3;
		int numberInTheSet = 0;
		for (int i = 0; i < 16; i++) {
			if(board.get(i) == true) {
				newBoard.set(indexOfShift + (numberInTheSet * 4));
			}
			numberInTheSet++;

			if(numberInTheSet > 3) {
				numberInTheSet = 0;
				indexOfShift--;
			}
		}
		
                // Stampo la nuova scacchiera.
		System.out.println("");
		for(int i = 0; i < 16; i ++) {
			boolean value = newBoard.get(i);
			if(value == false) {
				System.out.print(0);
			} else {
				System.out.print(1);
			}

		}

Tuttavia mi chiedevo se fosse possibile ottenere lo stesso risultato utilizzando operazioni di shift e booleane, in modo tale da rendere la trasformazione più veloce.

[scozzese]

Gentilissimi tutti,

mi rendo conto della difficoltà del quesito. In ogni caso dopo innumerevoli ricerche sono arrivato alla soluzione.
Di seguito posto il codice che potrebbe sempre ritornare utile a chiunque voglia cimentarsi nella programmazione di un gioco su scacchiera.
Sottolineo inoltre il fatto che non ho più utilizzato BitSet ma long. Long supporta 64 bits (scacchiera 8x8), operazioni logiche e anche operazioni di shift.

public static void main(String[] args) {

		// Un numero qualsiasi usato per testate il codice.
		long x = 1235323499;
		// Stampa la scacchiera iniziale.
		printBoard(x);

		/*
		 * 180°
		 * 
		long h1 = (0x5555555555555555L);
		long h2 = (0x3333333333333333L);
		long h4 = (0x0F0F0F0F0F0F0F0FL);
		long v1 = (0x00FF00FF00FF00FFL);
		long v2 = (0x0000FFFF0000FFFFL);
		x = ((x >>  1) & h1) | ((x & h1) <<  1);
		x = ((x >>  2) & h2) | ((x & h2) <<  2);
		x = ((x >>  4) & h4) | ((x & h4) <<  4);
		x = ((x >>  8) & v1) | ((x & v1) <<  8);
		x = ((x >> 16) & v2) | ((x & v2) << 16);
		x = ( x >> 32)       | ( x       << 32);
		 */

		/*
		 * 45° CLOCKWISE 
		 *
		 */

		/*
		long k1 = (0xAAAAAAAAAAAAAAAAL);
		long k2 = (0xCCCCCCCCCCCCCCCCL);
		long k4 = (0xF0F0F0F0F0F0F0F0L);
		x ^= k1 & (x ^ rotateRight(x,  8));
		x ^= k2 & (x ^ rotateRight(x, 16));
		x ^= k4 & (x ^ rotateRight(x, 32));
		 */
		
		

		/*
		 * 45° ANTI-CLOCKWISE
		 * 
		 */
		/*
		long k1 = (0x5555555555555555L);
		long k2 = (0x3333333333333333L);
		long k4 = (0x0f0f0f0f0f0f0f0fL);
		x ^= k1 & (x ^ rotateRight(x,  8));
		x ^= k2 & (x ^ rotateRight(x, 16));
		x ^= k4 & (x ^ rotateRight(x, 32));
		 */




		/*
		 * 
		 * 90° CLOCKWISE 
		 */

		//x = flipVertical (flipDiagA1H8 (x) );



		/*
		 * 90° ANTI-CLOCKWISE   
		 */
		//x = flipDiagA1H8 (flipVertical (x) );


		// Stampa il risultato.
		printBoard(x);
	}

Metodi utilizzati per le rotazioni.

	private static long flipDiagA1H8 (long x) {

		long t;
		long k1 = (0x5500550055005500L);
		long k2 = (0x3333000033330000L);
		long k4 = (0x0f0f0f0f00000000L);
		t  = k4 & (x ^ (x << 28));
		x ^=       t ^ (t >> 28) ;
		t  = k2 & (x ^ (x << 14));
		x ^=       t ^ (t >> 14) ;
		t  = k1 & (x ^ (x <<  7));
		x ^=       t ^ (t >>  7) ;
		return x;
	}

	private static long flipVertical (long x) {

		long k1 = (0x00FF00FF00FF00FFL);
		long k2 = (0x0000FFFF0000FFFFL);
		x = ((x >>  8) & k1) | ((x & k1) <<  8);
		x = ((x >> 16) & k2) | ((x & k2) << 16);
		x = ( x >> 32)       | ( x       << 32);
		return x;

	}



	private static long rotateRight(long x, int s) {
		return ((x >> s) | (x << (64-s)));
	}



	private static void printBoard(long board) {

		System.out.println("-----------------");

		String boardBits = Long.toBinaryString(board);

		String zeroString = "";
		for (int i = 0; i < 64 - boardBits.length(); i++) {
			zeroString += "0";
		}
		boardBits = zeroString + boardBits;
		System.out.println(boardBits);
		for (int i = 0; i < 8; i++) {
			System.out.println(boardBits.substring(i * 8, i * 8 + 8));
		}

	}

Ci tengo a sottolineare che le rotazioni di 45° avvengono secondo il sistema descritto da: Gillgasch and Heinz (http://chessprogramming.wikispaces.c...ated+Bitboards).

Questi metodi sono stati adattati al linguaggio Java. La fonte principale è: http://chessprogramming.wikispaces.c...g+and+Rotating
in cui è possibile trovare al trasformazioni.