BulbString.java

/** * The BulbString class uses an int to represent the current state * (either on or off) of a string of light bulbs. * BulbString simply has one private data field-bulbsInt which is capable of * storing the state of each light bulb by updating its value so that its * binary representation reflects the state of bulbs at each index. It does this * using bit manipulation and operators. In doing so, it significantly optimizes * the space and performance needed by such a system when compared to storing * the state of the bulbs in a data structure like a HashMap. It effectively reduces the space and time complexity * of the isOn(int bulbIndex) and toggle(int startIndex, int endIndex) to constant, or O(1) time. * Additionally, BulbString has a constructor which takes in a binary String * representing the initial length and state of the bulbs and initializes * an appropriately sized bulbsInt field to represent these bulbs. BulbString also has methods * isOn(int bulbIndex) to check if the bulb at index BulbIndex is on or off, * and toggle(int startIndex, int endIndex) to toggle the bulbs from indices startIndex to endIndex (inclusive). * * NOTE: because of the bit manipulaiton used to check and toggle bits, the states of the bulbs are stored from rightmost * bit to leftmost bit. For example, in a string of 5 bulbs represented as 10010 the rightmost bit (set to 0) * would be the first bulb and the leftmost bit (set to 1) would be the last bit. Additionally, toggle uses 1 as its beginning index and isOn uses 0. * For example, isOn(0) of the above string of bulbs would check the rightmost bit and return false. toggle(1,3) would toggle * the first to third bits from right to left and return 10101. */ public class BulbString { private int bulbsInt; //bulbsInt field to store the state of the bulbs in its binary representation public static void main(String args[]) { BulbString bs = new BulbString("1101001"); bs.toggle(2,4); System.out.println(Integer.toBinaryString(bs.bulbsInt)); bs.toggle(1,3); System.out.println(Integer.toBinaryString(bs.bulbsInt)); System.out.println(bs.isOn(1)); System.out.println(bs.isOn(4)); System.out.println(bs.isOn(6)); } // Constructor that takes in a String input to represent the string of bulbs and initializes an appropriate bulbsInt variable public BulbString(String input) { this.bulbsInt = Integer.parseInt(input, 2); } // boolean isOn which takes in an int bulbIndex and uses bit manipulation to check if the bulb at that index is 0 (off) or 1 (on). Refer to note aboe about indices and order of bits. public boolean isOn(int bulbIndex) { return (bulbsInt & 1 << bulbIndex) != 0; } // void toggle which takes in ints startIndex and endIndex and toggles the bits from startIndex to endIndex. Refer to note above about indices and order of bits. public void toggle(int startIndex, int endIndex) { int mask = ((1 << endIndex) - 1) ^ ((1 << (startIndex - 1)) - 1); int toggledValue = bulbsInt ^ mask; bulbsInt = toggledValue; } }