simulating data allocation with an int array

Question

So I have this assignment to simulate allocating data. It goes like this

its an int[] array whose elements in binary make up the allocation table like:

int[0] = 0xFF = 1111 1111;

1 is said to be free and 0 is allocated

if you call the get() method (also get(int) where int is the number of bits to be allocated), then it finds the first chunk of "free" space and changes the value to 0. free() (free(int numbits) or free(int numbits, int fromIndex)) changes the bits back to 1. examples:

data == 1111 0011
x.get(3);
data == 0001 0011
x.get(2);
data == 0001 0000
x.get();
data == 0000 0000
x.free(2);
data == 1100 0000
x.free(2, 5);
data == 1100 0110

All the elements in the int array get pushed together so if theres 2 elements, the binary representation would be 16 1 bits. The allocation has to be able to happen accross all the elements in the array.

How can I accomplish this using the bitwise operators and the Integer.toBinaryString() method. This is an assignment so Id like there to be more advice than actual answers. Hopefully i explained it well enough.

MAK MAK · Accepted Answer · 2011-06-10T04:16:37

Two useful functions that I have in my toolkit for binary ops are given below.

boolean isSet(int value, int bit){
   return (value&(1<<bit))!=0;
}  

int setBit(int value, int bit){
   return value|(1<<bit);
}

Basically you check whether a given bit is set by AND-ing it with another int which has all zeros and only the bit you are interested in set. The resulting value has zeros in every bit but will have that bit set only if it was set in the original value. Otherwise that bit is 0 (since 0 AND 1 is 0) making the whole result 0. Having a non-zero result means the bit was set.

To set a bit you just OR it with a value that has zeros in every bit and a 1 in the bit which you want to set. This gives a result which has all the other bits the same as they were in the original value but a 1 in the bit which you want to set.

Using this you can treat any int much like a size 32 boolean array and set or unset bits at any position.

simulating data allocation with an int array

1 Answers