CODEWITHSUNDEEP
javadata-structuresinteger
user13278163
user13278163

Reputation:

Can i create a mini int class that only consist of 1, 0, -1?

i'will optimize and increase performance the code that is given by teacher for tic-tac-toe game. Since i'll be only use X = 1, O = -1 and EMPTY = 0, i dont want to keep these numbers in an 32bit int array. Can i create my class just like int class but only have 1, 0, -1. I want to do that;

public static final int X = 1, O = -1, EMPTY = 0;
myDataType[][] board = new myDataType[3][3];
board[0][0] = X;
board[0][1] = O;

Upvotes: 0

Views: 128

Answers (2)

BeUndead
BeUndead

Reputation: 3618

Note: I'm not saying this is a good idea. But...

There's only 3^9 = 19683 possible states of an entire board of tic tac toe. You can easily fit this in a single int. As an example of how to do that, look at it in binary, and consider each pair of bits as a single cell:

private int state = 0b00_00_00_00_00_00_00_00_00;

Where we can use 00 as unset, 10 as X and 11 as O (01 is unspecified, but call it unset too, that way it's unset if the high bit is 0).

Then we can get/set a value by simply shifting the value to the appropriate bits of our state. In this case: ( 3 * row ) + col (to number the cells of the board) and then *2 since we're using 2 bits for each cell.

public static final int UNSET = 0b00;
public static final int X = 0b10;
public static final int O = 0b11;

public void set( final int row, final int col, final int val ) {
    state |= ( val << index( row, col ) );
}

public int get( final int row, final int col ) {
    return 0b11 & ( state >>> index( row, col ) );
}

private static final int index( final int row, final int col ) {
    return 2 * ( ( 3 * row ) + col );
}

Where we use OR to set the values at a specific bits, and use AND to mask the result to the two bits we're interested in. Some validation would probably be good here (check row and col are in bounds, check val is between 0b00 and 0b11, check the cell is unset before setting, whatever else).

With this, then say the first player goes in the middle (with X), your state would be:

state = 0b00_00_00_00_10_00_00_00_00_00;

Then the next player goes top-left with an O:

state = 0b00_00_00_00_10_00_00_00_00_11;

etc.

Again, I'm not saying this is a good idea, or will be any faster for you, or understandable for people quickly reading through the code... But it'll store the whole board in a single int rather than an array of them :shrug:.

Upvotes: 1

Chandimal Adikari
Chandimal Adikari

Reputation: 91

To answer to your question. Let's assume you can use boolean (primitive data type with simple 'b' to for your array). In theory it should only take, 1 bit per array element. However according to java docs. https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-2.html

In Oracle’s Java Virtual Machine implementation, boolean arrays in the Java programming language are encoded as Java Virtual Machine byte arrays, using 8 bits per boolean element.

In this case it takes 8 bits per boolean element. (This is for just for argument sake and we cannot use boolean since it only have true and false)

The next option is use Boolean Boxed type. It can hold the values true,false and null

You can map it like this,

true => 1,
false => -1,
null => 0

and Implement it like this,

 Boolean[][] board = new Boolean[3][3];
    board[0][0] = null;
    board[0][1] = false;
    board[1][0] = true;

How ever it turns out Boolean Boxed type takes 128bits in memory.(https://www.baeldung.com/java-primitives-vs-objects)

If you create a custom class, it will also take more memory. Therefore it is better to use a byte type as below, for your array like most suggested.

byte[][] board = new byte[3][3];
    board[0][0] = -1;
    board[0][1] = 0;
    board[1][0] = 1;

Upvotes: 1

Related Questions