• Advertisement
Sign in to follow this  

Bitfields.

This topic is 4322 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am starting work on a J2ME(Java) game which holds the game-board as a bitfield have you any good articles or references that explain how its best used? Never used this method before in previous games and seems like a very efficient and elegant way to hand game boards. Haven’t found anything on flipcodes archive or in the articles here. Thanks guys.

Share this post


Link to post
Share on other sites
Advertisement
Java and bit-wise operations do not mix well. For one, you do not have access to various pointer magic and there are no unsigned types. While it doesn't limit you, it results in code that is uglier than it should be.

Generally, all the magic that is needed in dealing with bit fields comes from understanding how shift, "and" and "or" operations work.


int w;
int h;
int N;
int S = 32; // fixed number of bits in int
int[] playfield;

long[] initializePlayfield(int _w, int _h)
{
w = _w; h = _h;
N = w * h / S + 1;
playfield = new long[N];
}

boolean isBitSet(int x, int y) {
int index = (y * w + x) / S;
int offset = x % S;
return ((playfield[index] & (1 << offset)) > 0);
}

void setBit(int x, int y, boolean how)
int index = (y * w + x) / S;
int offset = x % S;
if (how)
playfield[index] = playfield[index] | (1 << offset)
else
playfield[index] = playfield[index] & ~(1 << offset);
}



Replace the mod (%) operator with int offset = x & 31. or (S - 1)
Replace the division with int index = (y * w + x) >> 5. or 2^(5) = 32.
If w is a power of two, replace that with appropriate << operation.


I left the generic S for data size, since using a 32 bit int might not be optimal for J2ME. short would be 16 bits, byte is 8, so choose whatever is most suitable.

Using bit shifts instead of multiplications may result in faster operations, depending on both compiler and VM. Surprisingly, under Sun's JVM 1.4.x, even divisions with constants and obvious powers of two do not get compiled into appropriate shift opcodes, so doing that manually helps.

Share this post


Link to post
Share on other sites
For Java I recomend you to use only 32 bit (integers) as any operations on other types do conversion to 32 bit first.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Java and bit-wise operations do not mix well. For one, you do not have access to various pointer magic and there are no unsigned types. While it doesn't limit you, it results in code that is uglier than it should be.


I really don't see why "pointer magic" is going to make things less ugly, or even be all that useful. Also, there is one unsigned type: 'char'. :)

But actually, I'm writing to clean up your code. First of all, let's make sure the types of variables and function returns match up. Also, arrays "know" their length, so there is no reason to track it separately. And FFS, why wouldn't you use a constructor?


class Bitfield {
private int width, height;
private int[] bits;
private static final int SIZE_SHIFT = 5; // log2(32)
private static final int SIZE_MASK = 31; // 32 - 1

public static final int INSPECT = 0;
public static final int SET = 1;
public static final int CLEAR = 2;
public static final int TOGGLE = SET | CLEAR;

public Bitfield(int width_, int height_) {
width = width_; height = height_;
// The size of all Java types is guaranteed, and the only reason you'd
// care about the type of an array underlying a bitfield is for alignment
// reasons. But honestly, I can't think of any reason why int[] wouldn't
// be as good as anything else.
bits = new int[(width * height + SIZE_MASK) >> SIZE_SHIFT];
}

public boolean twiddle(int x, int y, int action) {
// Perform the indicated action on the bit, and return the new status.
return twiddle(y * width + x, action);
}

private boolean twiddle(int bit, int action) {
int mybyte = bit >> SIZE_SHIFT;
int mask = 1 << bit;
boolean current = (playfield[mybyte] & mask) != 0;
// it could be negative if it's the high bit :)
// Also, we have to shift left, because any right-shifting would just give
// us a zero value. That may mean we store the bits in an unintuitive order,
// but the class users won't know or care.
// Oh, BTW, you don't need to mod your arguments for a left shift by the
// integer size; the operator semantics are such that this happens anyway.

boolean set = current;
if ((action & SET) != 0 && !set) { set = true; }
if ((action & CLEAR) != 0 && set) { set = false; }
if (set) {
// make sure the bit is set.
playfield[mybyte] |= mask;
} else {
// make sure it is clear.
playfield[mybyte] &= ~mask;
}
return set;
}
}


Quote:
Surprisingly, under Sun's JVM 1.4.x, even divisions with constants and obvious powers of two do not get compiled into appropriate shift opcodes, so doing that manually helps.


That kind of work is normally done by the JIT compiler instead. javac is pretty basic.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
But actually, I'm writing to clean up your code. First of all, let's make sure the types of variables and function returns match up. Also, arrays "know" their length, so there is no reason to track it separately. And FFS, why wouldn't you use a constructor?


Just to justify:

I just demonstrated the principles, didn't intend to provide the class, hence no constructor. The code was merely proof of principle, not intended for scalability.

Yes, arrays can be queried, no real reason why I chose a separate variable. I forgot that arraylength is an opcode, a static variable would be more suitable when using Collections, where size() is a method call, assuming constant length as the case with static bit field.

Good catch on the non-negative/non-zero condition.

J2ME was specifically mentioned, so I assumed that implementation may be completely proprietary, perhaps with different underlying core that is most efficient with 16-bit ints.

Quote:
That kind of work is normally done by the JIT compiler instead. javac is pretty basic.


I mentioned that specifically because I had different experience. Just to make sure, I double checked it.

// Test method that gets called from a for loop
public static int testDiv(final int x) {
return x >> 2;
// return x / 4;
}
int testValue = 256;
int testResult = 0;
// loop is repeated several times to allow JIT warmup
// (1000 cycles per default setting)
for (int i = 0; i < 1000000000; i++) {
testResult = testDiv(testValue );
}
// print out to avoid dead code removal
System.out.println(testResult);


Running Sun's java 1.5 under Windows XP on AMD 3000, I got the following timings:
Using SHR: 2.242 nsec
Using division: 2.935 nsec

Quote:
I really don't see why "pointer magic" is going to make things less ugly, or even be all that useful. Also, there is one unsigned type: 'char'. :)


True, I was a bit inacurate. What I had in mind was various similar routines, such as cryptology methods, raw I/O (serial for example) or more working with raw data pointers (image buffers). My comment applied more to lack of general unsigned type than bitwise operations. Even with best intentions, things can get more cluttered that it might be necessary.
And I didn't really intend to imply that pointer magic is always a good thing.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement