public class BitSet1 implements Cloneable, java.io.Serializable {    // >>>左边补0， <<  右边补0。    public final static int ADDRESS_BITS_PER_WORD = 6;    public final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;//2^6=64    public final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;//63    public static final long WORD_MASK = 0xffffffffffffffffL;//16进制64bit,全1，就是-1    //序列化字段，第i位存储在位位置i%64的位[i/64]中    public static final ObjectStreamField[] serialPersistentFields = {        new ObjectStreamField("bits", long[].class),    };    public long[] words;//long数组来作为内部存储结构。Bitset至少为一个long的大小    //数组长度    public transient int wordsInUse = 0;//使用的words数组，小于等于words.length。wordsInUse-1是不为0的long的最大位置。一直到words.length可以等于0。    //“words”的大小是否由用户指定。    public transient boolean sizeIsSticky = false;    public static final long serialVersionUID = 7997698588986878753L;    public static int wordIndex(int bitIndex) {        return bitIndex >> ADDRESS_BITS_PER_WORD;//除以64，右移6位，取整。        //1-6位全部移出去，第6位=32移出去了变成了0。第7位=64变成第一位=1，第8位=128变成第二位=2。从第7位到32位全部除以64，不要余数取整。    }    //wordsInUse >= 0 , wordsInUse <= words.length , words[wordsInUse - 1] != 0 , words[wordsInUse] == 0    public void checkInvariants() {        //左边走了，右边就不走了。        assert(wordsInUse >= 0 && wordsInUse <= words.length);          assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);        //wordsInUse等于0可以，就不走右边了。不等于0那么words[wordsInUse - 1]就不能为0。wordsInUse-1是不为0的long的最大位置。        assert(wordsInUse == words.length || words[wordsInUse] == 0);        //wordsInUse == words.length可以就不走右边了。如果2者不相等wordsInUse要小，words[wordsInUse]就要等于0。words[wordsInUse - 1]就不能为0。    }    //清除为0的，减少内存。    public void recalculateWordsInUse() {        int i;        for (i = wordsInUse-1; i >= 0; i--)            if (words[i] != 0)                break;        wordsInUse = i+1; // 从后往前找，第一个非0的后面一个元素    }    public BitSet1() {        initWords(BITS_PER_WORD);//64长度，words数组只有1个长度。        sizeIsSticky = false;//为false表示使用的是默认大小    }    public BitSet1(int nbits) {        if (nbits < 0)            throw new NegativeArraySizeException("nbits < 0: " + nbits);        initWords(nbits);//传进来的是bit位的位数        sizeIsSticky = true;//为true表示大小是传进来的    }    public void initWords(int nbits) {
   //nbits是总位数，一个long是64位。        words = new long[wordIndex(nbits-1) + 1];//wordIndex是取整    }    public BitSet1(long[] words) {        this.words = words;//[113, 289, 8481]        this.wordsInUse = words.length;//>=0,3        checkInvariants();    }    //BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0) for all n < 64 * longs.length .    public static BitSet1 valueOf(long[] longs) {        int n;//都要先除去0的元素，节约内存。        for (n = longs.length; n > 0 && longs[n - 1] == 0; n--);//n-1是longs数组最后一个不为0的索引位置，n就是个数。        return new BitSet1(Arrays.copyOf(longs, n));//拷贝longs前n个元素或者longs数组长度个元素，取2者较小者。    }    //把lb中真实元素（position到limit），并且去除多余的0，然后给bitset。    public static BitSet1 valueOf(LongBuffer1 lb) {
   //LongBuffer是提供对long[]数组操作。对于读取到的long[]做一些增删改查后再使用，就是缓冲区。        //mark=-1,pos=0,lim=limit-position,cap=limit-position,offset=position。 slice()得到的是原来position到limit的位置的数据，包括position不包括limit。所有元素相对原来数组的相对值是offset，        //从0开始一直到remaining()。        lb = lb.slice();        int n;        //确定最后一个不为0的数据的个数。都要先除去0的元素，节约内存。        //slice()之后的put和set都会加上offset=pisition，就是获取原数组的position到limit的所有位置元素，不包括limit。        for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--);//从0开始一直到remaining()，除去后面为0的。        long[] words = new long[n];//n是不为0的位置个数，包括开头一共n个，        lb.get(words);//把lb的值全部复制到words里面去。        return new BitSet1(words);    }    public static BitSet1 valueOf(byte[] bytes) {        return BitSet1.valueOf(ByteBuffer.wrap(bytes));    }    //把bb中真实元素（position到limit），并且去除多余的0，然后给bitset。    public static BitSet1 valueOf(ByteBuffer bb) {        bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN);//slice()之后，所有元素相对原来数组的相对值是offset，从0到remaining。        int n;        for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--);//除去0重新计算n = position到limit除去0之后元素个数。        long[] words = new long[(n + 7) / 8];//取整加1        bb.limit(n);//bb的limit之前等于remainnig，现在为n。        int i = 0;        while (bb.remaining() >= 8)            words[i++] = bb.getLong();//position移动8位，        for (int remaining = bb.remaining(), j = 0; j < remaining; j++)            words[i] |= (bb.get() & 0xffL) << (8 * j);//0xffL:前面全0，后面一个字节8个1。移8n位再或。        return new BitSet1(words);    }    /*      byte[] bytes = s.toByteArray();       bytes.length == (s.length()+7)/8 and s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)：实例画图。    */    public byte[] toByteArray() {
   //bit是从long数组低位开始放，一直放到最高位，最高位是从低位开始放。        int n = wordsInUse;        if (n == 0)            return new byte[0];        int len = 8 * (n-1);        for (long x = words[n - 1]; x != 0; x >>>= 8)//最后一个的值，一直除以256，            len++;        byte[] bytes = new byte[len];        ByteBuffer bb = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN);        for (int i = 0; i < n - 1; i++)            bb.putLong(words[i]);        for (long x = words[n - 1]; x != 0; x >>>= 8)            bb.put((byte) (x & 0xff));        return bytes;    }    public long[] toLongArray() {        return Arrays.copyOf(words, wordsInUse);    }    public void ensureCapacity(int wordsRequired) {        if (words.length < wordsRequired) {            int request = Math.max(2 * words.length, wordsRequired);            words = Arrays.copyOf(words, request);//长度还是request个长度，只是复制 Math.min(words.length, request)元素过去。            sizeIsSticky = false;        }    }    public void expandTo(int wordIndex) {        int wordsRequired = wordIndex+1;        if (wordsInUse < wordsRequired) {            ensureCapacity(wordsRequired);            wordsInUse = wordsRequired;        }    }    public static void checkRange(int fromIndex, int toIndex) {        if (fromIndex < 0)            throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);        if (toIndex < 0)            throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);        if (fromIndex > toIndex)            throw new IndexOutOfBoundsException("fromIndex: " + fromIndex + " > toIndex: " + toIndex);    }    public void flip(int bitIndex) {
   //65，指定位反转。        if (bitIndex < 0)            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);        int wordIndex = wordIndex(bitIndex);//1        expandTo(wordIndex);        words[wordIndex] ^= (1L << bitIndex);//移动位数对64取模，异或就是其余位置不变，这个位置取反。        recalculateWordsInUse();        checkInvariants();    }    public void flip(int fromIndex, int toIndex) {        checkRange(fromIndex, toIndex);        if (fromIndex == toIndex)            return;        int startWordIndex = wordIndex(fromIndex);//开始数组索引        int endWordIndex   = wordIndex(toIndex - 1);//结束数组索引，要减1。        expandTo(endWordIndex);        //fromIndex对64取模位置开始(包括这个位置)一直到最前面都是1，后面都是0。        long firstWordMask = WORD_MASK << fromIndex;//用于异或的值        //>>>左边补上0，左边是0右边是1。右移64-toIndex%64         //6>>>-2相当于6>>>30,(32+(-2))==30。        long lastWordMask  = WORD_MASK >>> -toIndex;//无符号右移，忽略了符号位扩展，0补左边。用于异或的值        if (startWordIndex == endWordIndex) {            // 一个数组里面异或            words[startWordIndex] ^= (firstWordMask & lastWordMask);//对1异或，就是取反。        } else {            // 开始数组异或            words[startWordIndex] ^= firstWordMask;            // 中间数组异或            for (int i = startWordIndex+1; i < endWordIndex; i++)                words[i] ^= WORD_MASK;            // 结尾数组异或            words[endWordIndex] ^= lastWordMask;        }        recalculateWordsInUse();        checkInvariants();    }    public void set(int bitIndex) {
   //设置bit位为1        if (bitIndex < 0)            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);        int wordIndex = wordIndex(bitIndex);        expandTo(wordIndex);        words[wordIndex] |= (1L << bitIndex);          checkInvariants();    }    public void set(int bitIndex, boolean value) {        if (value)            set(bitIndex);        else            clear(bitIndex);    }    public void set(int fromIndex, int toIndex) {        checkRange(fromIndex, toIndex);        if (fromIndex == toIndex)            return;        int startWordIndex = wordIndex(fromIndex);        int endWordIndex   = wordIndex(toIndex - 1);        expandTo(endWordIndex);        long firstWordMask = WORD_MASK << fromIndex;        long lastWordMask  = WORD_MASK >>> -toIndex;        if (startWordIndex == endWordIndex) {            words[startWordIndex] |= (firstWordMask & lastWordMask);//0变成1，1变成1，就是全设置为1。        } else {            words[startWordIndex] |= firstWordMask;//或操作就是设置为1，            for (int i = startWordIndex+1; i < endWordIndex; i++)                words[i] = WORD_MASK;            words[endWordIndex] |= lastWordMask;        }        checkInvariants();    }    public void set(int fromIndex, int toIndex, boolean value) {        if (value)            set(fromIndex, toIndex);        else            clear(fromIndex, toIndex);    }    public void clear(int bitIndex) {        if (bitIndex < 0)            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);        int wordIndex = wordIndex(bitIndex);        if (wordIndex >= wordsInUse)            return;        words[wordIndex] &= ~(1L << bitIndex);//指定位变为0，&是与操作，1L<
     
      = wordsInUse)            return;        int endWordIndex = wordIndex(toIndex - 1);        if (endWordIndex >= wordsInUse) {            toIndex = length();            endWordIndex = wordsInUse - 1;        }        long firstWordMask = WORD_MASK << fromIndex;        long lastWordMask  = WORD_MASK >>> -toIndex;        if (startWordIndex == endWordIndex) {            words[startWordIndex] &= ~(firstWordMask & lastWordMask);//00000111111100000        } else {            words[startWordIndex] &= ~firstWordMask;            for (int i = startWordIndex+1; i < endWordIndex; i++)                words[i] = 0;            words[endWordIndex] &= ~lastWordMask;        }        recalculateWordsInUse();        checkInvariants();    }    public void clear() {        while (wordsInUse > 0)            words[--wordsInUse] = 0;//全部清0    }    public boolean get(int bitIndex) {
   //返回的0,1就是true,false。        if (bitIndex < 0)            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);        checkInvariants();        int wordIndex = wordIndex(bitIndex);        //通过与操作得到一个long的值，来判断某一位是0还是1。        //&就能按位操作        //1L << bitIndex就能得到移位后的long值        return (wordIndex < wordsInUse) && ((words[wordIndex] & (1L << bitIndex)) != 0);    }    public BitSet1 get(int fromIndex, int toIndex) {
   //包头不包尾，获取指定区间的bitset，返回的也是long[]数组装着。        checkRange(fromIndex, toIndex);        checkInvariants();         int len = length();//总共多少bit位        if (len <= fromIndex || fromIndex == toIndex)            return new BitSet1(0);        if (toIndex > len)            toIndex = len;        BitSet1 result = new BitSet1(toIndex - fromIndex);//bit的长度        //toIndex - fromIndex:::0-64:1,65-128:2,129-192:3。        int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;//数组个数        int sourceIndex = wordIndex(fromIndex);//开始数组索引        //对64取余为0，开始位置就是64的整数倍0,64,128,192。        boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);        //除了最后一个word。为数组前n-1个元素赋值        for (int i = 0; i < targetWords - 1; i++, sourceIndex++)            result.words[i] = wordAligned ? words[sourceIndex] : //开始位置是64整数倍，整个long拿出去                (words[sourceIndex] >>> fromIndex) | (words[sourceIndex+1] << -fromIndex);//数组相邻位置凑成64个。从左边fromIndex位置到右边fromIndex位置取出64个来成为一个long，包括左边fromIndex不包括右边fromIndex。            //一直到最后一个的fromIndex的位置（最后一个fromIndex还没有取出去），并且最后一个的fromIndex到toIndex构成不了64个。                    long lastWordMask = WORD_MASK >>> -toIndex; //WORD_MASK = 0xffffffffffffffffL。toIndex右边都是1（不包括toIndex）。        result.words[targetWords - 1] =                //64取余，一个数组里面谁在左边右边。                //toIndex-1 < fromIndex，fromIndex取余后要大，由于是反的，fromIndex在左边toIndex-1在右边。所以有2个long元素综合起来。            ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK)//BIT_INDEX_MASK=63。            ?             ((words[sourceIndex] >>> fromIndex) | //最后一个没有取完的，                    (words[sourceIndex+1] & lastWordMask) << -fromIndex)//加上toIndex右边的，            :            ((words[sourceIndex] & lastWordMask) >>> fromIndex);//toIndex-1 > fromIndex，toIndex在左边，        result.wordsInUse = targetWords;        result.recalculateWordsInUse();        result.checkInvariants();        return result;    }    public int nextSetBit(int fromIndex) {
   //从fromIndex开始第一个1在哪个位置（包括fromIndex），返回的位置是索引，        if (fromIndex < 0)            throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);        checkInvariants();        int u = wordIndex(fromIndex);        if (u >= wordsInUse)            return -1;        long word = words[u] & (WORD_MASK << fromIndex);//words[u]左边fromIndex（取模）开始为1（包括fromIndex位置）。fromIndex右边要置为0。        System.out.println(Long.toBinaryString(word));        System.out.println(Long.toBinaryString(WORD_MASK << fromIndex));        while (true) {            if (word != 0) {
   //等于0就全是0，                System.out.println(Long.numberOfTrailingZeros(word));                return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);//numberOfTrailingZeros右边有多少个0，            }            if (++u == wordsInUse)//u加1一直到wordsInUse-1，就退出                return -1;            word = words[u];//修改word的值，不移位了。        }    }    public int nextClearBit(int fromIndex) {
   //从fromIndex开始第一个为0的位置，包括fromIndex。返回的位置是索引，        if (fromIndex < 0)            throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);        checkInvariants();        int u = wordIndex(fromIndex);        if (u >= wordsInUse)            return fromIndex;        long word = ~words[u] & (WORD_MASK << fromIndex);        while (true) {            if (word != 0)                return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);//numberOfTrailingZeros右边有多少个0，            //word全1就++，            if (++u == wordsInUse)                return wordsInUse * BITS_PER_WORD;            word = ~words[u];        }    }    public int previousSetBit(int fromIndex) {
   //从fromIndex开始（包括fromIndex）前面第一个1,        if (fromIndex < 0) {            if (fromIndex == -1)                return -1;            throw new IndexOutOfBoundsException("fromIndex < -1: " + fromIndex);        }        checkInvariants();        int u = wordIndex(fromIndex);        if (u >= wordsInUse)            return length() - 1;        long word = words[u] & (WORD_MASK >>> -(fromIndex+1));//fromIndex到右都是1，包括fromIndex，        while (true) {            if (word != 0)                return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);//左边有多少个0            if (u-- == 0)                return -1;            word = words[u];        }    }    public int previousClearBit(int fromIndex) {        if (fromIndex < 0) {            if (fromIndex == -1)                return -1;            throw new IndexOutOfBoundsException("fromIndex < -1: " + fromIndex);        }        checkInvariants();        int u = wordIndex(fromIndex);        if (u >= wordsInUse)            return fromIndex;        long word = ~words[u] & (WORD_MASK >>> -(fromIndex+1));        while (true) {            if (word != 0)                return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word);            if (u-- == 0)                return -1;            word = ~words[u];        }    }    public int length() {        if (wordsInUse == 0)            return 0;        return BITS_PER_WORD * (wordsInUse - 1) +  //前面64*(length-1)个位的个数            //numberOfLeadingZeros()一个long值里面左边有多少个0，            (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));    }    public boolean isEmpty() {        return wordsInUse == 0;    }    public boolean intersects(BitSet1 set) {        for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)            if ((words[i] & set.words[i]) != 0)//&是位操作，等于0就继续，等于0就是没有1跟1相对的。                return true;        return false;    }    public int cardinality() {        int sum = 0;        for (int i = 0; i < wordsInUse; i++)            sum += Long.bitCount(words[i]);//为1的个数        return sum;    }    public void and(BitSet1 set) {        if (this == set)            return;        while (wordsInUse > set.wordsInUse)            words[--wordsInUse] = 0;        for (int i = 0; i < wordsInUse; i++)            words[i] &= set.words[i];//逻辑与操作        recalculateWordsInUse();        checkInvariants();    }    public void or(BitSet1 set) {
   //逻辑或操作        if (this == set)            return;        int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);        if (wordsInUse < set.wordsInUse) {            ensureCapacity(set.wordsInUse);            wordsInUse = set.wordsInUse;        }        for (int i = 0; i < wordsInCommon; i++)            words[i] |= set.words[i];        if (wordsInCommon < set.wordsInUse)            System.arraycopy(set.words, wordsInCommon, words, wordsInCommon, wordsInUse - wordsInCommon);        checkInvariants();    }    public void xor(BitSet1 set) {        int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);        if (wordsInUse < set.wordsInUse) {            ensureCapacity(set.wordsInUse);            wordsInUse = set.wordsInUse;        }        for (int i = 0; i < wordsInCommon; i++)            words[i] ^= set.words[i];        if (wordsInCommon < set.wordsInUse)            System.arraycopy(set.words, wordsInCommon, words, wordsInCommon, set.wordsInUse - wordsInCommon);        recalculateWordsInUse();        checkInvariants();    }    public void andNot(BitSet1 set) {
   // Perform logical (a & !b) on words in common        for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)            words[i] &= ~set.words[i];        recalculateWordsInUse();        checkInvariants();    }    public int hashCode() {        long h = 1234;        for (int i = wordsInUse; --i >= 0; )            h ^= words[i] * (i + 1);        return (int)((h >> 32) ^ h);    }    public int size() {        return words.length * BITS_PER_WORD;    }    public boolean equals(Object obj) {        if (!(obj instanceof BitSet1))            return false;        if (this == obj)            return true;        BitSet1 set = (BitSet1) obj;        checkInvariants();        set.checkInvariants();        if (wordsInUse != set.wordsInUse)            return false;        for (int i = 0; i < wordsInUse; i++)            if (words[i] != set.words[i])                return false;        return true;    }    public Object clone() {        if (! sizeIsSticky)            trimToSize();        try {            BitSet1 result = (BitSet1) super.clone();            result.words = words.clone();            result.checkInvariants();            return result;        } catch (CloneNotSupportedException e) {            throw new InternalError(e);        }    }    public void trimToSize() {        if (wordsInUse != words.length) {            words = Arrays.copyOf(words, wordsInUse);//只要wordsInUse和words.length较小者            checkInvariants();        }    }    public void writeObject(ObjectOutputStream s) throws IOException {        checkInvariants();        if (! sizeIsSticky)            trimToSize();        ObjectOutputStream.PutField fields = s.putFields();        fields.put("bits", words);        s.writeFields();    }    public void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {        ObjectInputStream.GetField fields = s.readFields();        words = (long[]) fields.get("bits", null);        // Assume maximum length then find real length        // because recalculateWordsInUse assumes maintenance        // or reduction in logical size        wordsInUse = words.length;        recalculateWordsInUse();        sizeIsSticky = (words.length > 0 && words[words.length-1] == 0L); // heuristic        checkInvariants();    }    public String toString() {
   //所有的1的索引位置，{0, 4, 5, 6, 64, 69, 72, 128, 133, 136, 141}        checkInvariants();        //大于128就看1的个数，小于就看所有个数        int numBits = (wordsInUse > 128) ? cardinality() : wordsInUse * BITS_PER_WORD;        StringBuilder b = new StringBuilder(6*numBits + 2);//1154        b.append('{');        int i = nextSetBit(0);//从0开始的第一个1在哪个位置，        System.out.println("i1="+i);        if (i != -1) {            b.append(i);//i是所有的1的索引位置，            System.out.println("b="+b);            while (true) {                if (++i < 0) break;//超过int最大值，前面i已经加过一次了，这里直接加加，                if ((i = nextSetBit(i)) < 0) break;//从i+1开始，下一个为1的位置在哪里，                int endOfRun = nextClearBit(i);//这里的i是还没有加进去的1的位置，                System.out.println("endOfRun="+endOfRun);//从还没有加进去的i的位置开始，0的位置。                System.out.println("i2="+i);                do {                     b.append(", ").append(i); //把这个i放入string里面，然后下面在加加，                    System.out.println("b="+b);//中间全是1都加进去到b，                }while (++i != endOfRun);//跳出时候i是0的位置endOfRun，所以出去后要加1，                            }        }        b.append('}');         return b.toString();    }    /**     * Returns a stream of indices for which this BitSet      * contains a bit in the set state. The indices are returned     * in order, from lowest to highest. The size of the stream     * is the number of bits in the set state, equal to the value     * returned by the {
    @link #cardinality()} method.     *     * 
      
The bit set must remain constant during the execution of the     * terminal stream operation.  Otherwise, the result of the terminal     * stream operation is undefined.     */    public IntStream stream() {        class BitSetIterator implements PrimitiveIterator.OfInt {            int next = nextSetBit(0);//从0开始的第一个1的位置，            @Override            public boolean hasNext() {                return next != -1;            }            @Override            public int nextInt() {                if (next != -1) {                    int ret = next;                    next = nextSetBit(next+1);//下一个1的位置                    return ret;                } else {                    throw new NoSuchElementException();                }            }        }        return StreamSupport.intStream(                //spliterator返回IntIteratorSpliterator分组器                () -> Spliterators.spliterator(new BitSetIterator(), cardinality(),Spliterator.ORDERED | Spliterator.DISTINCT | Spliterator.SORTED),                Spliterator.SIZED | Spliterator.SUBSIZED |Spliterator.ORDERED | Spliterator.DISTINCT | Spliterator.SORTED,false);    }}