@@ -0,0 +1,1776 @@
+package org.speedfirst.leetcode.bit;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.Arrays;%0Aimport java.util.List;%0Aimport java.util.Random;%0A%0A/**%0A * Created by jiankuan on 1/15/15.%0A */%0Apublic class FindNotExistedNumber %7B%0A%0A    List%3CInteger%3E getNotExistedNumber(List%3CInteger%3E nums) %7B%0A        int%5B%5D bitset = new int%5B256%5D; // 128 integer * 4byte * 8bit = total 4096 numbers%0A        Arrays.fill(bitset, 0);%0A        for (int num: nums) %7B%0A            int offset = num & 0x1F;%0A            int idx = num %3E%3E 5;%0A            bitset%5Bidx%5D %7C= (1 %3C%3C offset);%0A        %7D%0A%0A        // bit set done%0A        // check%0A        ArrayList%3CInteger%3E res = new ArrayList%3C%3E();%0A        for (int i = 0; i %3C4096; i++) %7B%0A            int offset = i & 0x1F;%0A            int idx = i %3E%3E 5;%0A            boolean exists = (((bitset%5Bidx%5D %3E%3E offset) & 0x1) == 1);%0A            if (!exists) %7B%0A                res.add(i);%0A            %7D%0A        %7D%0A%0A        return res;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Random r = new Random();%0A        List%3CInteger%3E nums = new ArrayList%3C%3E();%0A        for (int i = 0; i %3C 20000; i++) %7B%0A            nums.add(r.nextInt(4096));%0A        %7D%0A%0A        FindNotExistedNumber findNotExistedNumber = new FindNotExistedNumber();%0A        List%3CInteger%3E res = findNotExistedNumber.getNotExistedNumber(nums);%0A%0A        // get expected result%0A        int%5B%5D tmp = new int%5B4096%5D;%0A        Arrays.fill(tmp, 0);%0A        for (int num: nums) %7B%0A            tmp%5Bnum%5D = 1;%0A        %7D%0A        List%3CInteger%3E expectRes = new ArrayList%3C%3E();%0A        for (int i = 0; i %3C 4096; i++) %7B%0A            if (tmp%5Bi%5D == 0) %7B%0A                expectRes.add(i);%0A            %7D%0A        %7D%0A        System.out.println(res.equals(expectRes));%0A        System.out.println(res);%0A        System.out.println(expectRes);%0A    %7D%0A%7D%0A

Implement GetNotExistNumber