Topics

Bitwise operators, Bitwise Masks

Bit-Array Class

Create a class that stores a 64-bit long value.

Example:

Bits	1	1	0	0		0	0	0
Position	63	62	61	60	....	2	1	0

The class will have a method to flip the bit at the given position in the number (up to 64 positions ) using the set method, as well as a get method that inspects the state of the bit at the given position. When interacting with the class a user should only see boolean values when assigning(set) or retrieving(get) values at a position in the binary value as seen in the class diagram below:

BitArray

- data : long

+ get(index : int) : boolean + set(index : int, value : boolean) : void

Field & Method Hints:

• data: This field should be a long value. There should not be any other fields in the class.
• get(index): This method returns a true value if the bit at the given index is 1, otherwise, if the bit is 0 then the method returns false.
• set(index, value): Assigns the bit at the given index 1 if the value is true, otherwise if the value is false the bit is assigned 0.

Test your class thoroughly using a Junit class. In particular, make sure you can assign both true and false to all indices.

@Test public void testSetMethod(){ BitArray bits = new BitArray(); // set all bits to true for (int i = 0; i < Long.SIZE; i++) { bits.set(i,true); } // verify all bits are true for (int i = 0; i < Long.SIZE; i++) { assertTrue("get("+i+") incorrectly returned false",bits.get(i)); } // set all bits to false for (int i = 0; i < Long.SIZE; i++) { bits.set(i,false); } // verify all bits are false for (int i = 0; i < Long.SIZE; i++) { assertFalse("get("+i+") incorrectly returned true",bits.get(i)); } } 

@Test public void testSetMethodB(){ BitArray bits = new BitArray(); // set 32 bits to true for (int i = 0; i < Integer.SIZE; i++) { bits.set(i,true); } // verify 32 bits are true for (int i = 0; i < Integer.SIZE; i++) { assertTrue("get("+i+") incorrectly returned false",bits.get(i)); } // verify other 32 bits are false for (int i = Integer.SIZE; i < 64; i++ ){ assertFalse("get("+i+") incorrectly returned true",bits.get(i)); } }

@Test public void testSetMethodC(){ BitArray bits = new BitArray(); bits.set(0,true); bits.set(1,true); bits.set(2,false); assertFalse("get(2) incorrectly returned true",bits.get(2)); assertTrue("get(0) incorrectly returned false",bits.get(0)); assertTrue("get(1) incorrectly returned false",bits.get(1)); }

The Lockers Problem

There is a well-known mathematical logic problem called the lockers problem. Here is a description of the problem.

A new high school has just opened! There are 50 lockers in the school and they have been numbered from 1 through 50. When the school opens the first student to enter the school walks into the hallway and opens all the locker doors! Afterwards, the second student closes each door whose number is a multiple of 2. Similarly, the third student changes every door that is a multiple of 3 (closing open doors, opening closed doors). The fourth student changes each door that is a multiple of 4 and so on. After 50 students have entered the hallway, which locker doors are open?

Using your BitArray class described above, solve the lockers problem. Each bit in your BitArray should represent a locker, where true is an open locker and false is a closed locker. Once you have finished altering each bit according to the problem statement, print out the number and state of each locker, for example:

1: open 2: closed 3: closed 4: open 5. closed 6. closed 7. closed ... Submit BitArray.java Lockers.java