Use Bits. Sacrifice readability for speed.


  • 0

    Basic idea:
    For each number, it only has two status: taken or not. My first thought was to use a boolean array, which is trivial. Actually we can use bits instead of boolean array. For example, an integer can represent status of 32 numbers, and a long can do 64. All we need to do is to map each number to its corresponding bit position. For example, if we use an int[] assigned, then the number 40 should be in assigned[1]. Its bit position index is 8 from right to left, because 40 = 32*1 + 8.

    In this way, the running time reduces (compared to using boolean array), while the code becomes less readable of course.
    Below is my code. I'm not so good at handling bits, to be honest. Please let me know if you find anything that can be improved. Thanks!

    UPDATE:
    I never heard about BitSet class before.... but it seems that it can make my life much easier. Here is a solution using BitSet, which is much more readable than mine. Anyway I'm gonna read its documentation.
    https://discuss.leetcode.com/topic/53102/java-ac-solution-with-bitset-and-efficient-get-comments

    public class PhoneDirectory  {
    
        private static final int SHIFT = 5, MOD = (1 << SHIFT) - 1;
        /**
         * An array of integer. Every bit in each integer indicates if corresponding number has been taken.
         */
        private int[] assigned;
        /**
         * Capacity.
         */
        private int capacity;
    
        /**
         * Constructor.
         *
         * @param maxNumbers max number of numbers
         */
        public PhoneDirectory(int maxNumbers) {
            int arrlen = (maxNumbers >> SHIFT) + (0 == (maxNumbers & MOD) ? 0 : 1);
            assigned = new int[arrlen];
            capacity = maxNumbers;
        }
    
        /**
         * Provide a number which is not assigned to anyone.
         *
         * @return an available number. Return -1 if none is available.
         */
        @Override
        public int get() {
            for (int idx = 0; idx < assigned.length; idx++) {
                if ((idx << SHIFT) >= capacity) {
                    break;
                }
                if (assigned[idx] == (~0)) {
                    continue;
                }
                int low0 = ~assigned[idx];
                low0 &= -low0;
                assigned[idx] |= low0;
                int ret = ((idx << SHIFT) | Integer.numberOfTrailingZeros(low0));
                if (ret < capacity) {
                    return ret;
                }
            }
            return -1;
        }
    
        /**
         * Check if a number is available or not.
         *
         * @param number input number
         * @return true if input number is available.
         */
        @Override
        public boolean check(int number) {
            if (number >= capacity || number < 0) {
                return false;
            }
            int[] loc = locate(number);
            return (assigned[loc[0]] & (1 << loc[1])) == 0;
        }
    
        /**
         * Recycle or release a number.
         *
         * @param number input number
         */
        @Override
        public void release(int number) {
            int[] loc = locate(number);
            assigned[loc[0]] &= ~(1 << loc[1]);
        }
    
        /**
         * Locate the bit position of given number.
         *
         * @param number input number
         * @return an int array. The first element is the index of integer in "assigned" array,
         * the second element is the bit position of input number in the integer.
         */
        private int[] locate(int number) {
            return new int[]{number >> SHIFT, number & MOD};
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.