Java随笔记 - 实现一个自定义的BitMap

àì夳堔傛蜴生んèń 2022-12-29 04:46 202阅读 0赞

###  Java随笔记 - 实现一个自定义的BitMap ###

#### preview ####

*  对于刷OJ的人来说，卡内存的题一定不陌生，而面对这种题，往往会考虑bit数组能不能派上用场。对于这道题[剑指 Offer 03. 数组中重复的数字][Offer 03.]，我就尝试了使用bit数组来打标记，运行效果略微优于书上提供的解法。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pfX01heA_size_16_color_FFFFFF_t_70_pic_center]

#### BitMap ####

*  对于[数组中重复的数字][Offer 03.]这道题我是简单的定义了个byte数组进行了大致的实现，后来想说可以自己简单封装一个BitMap类，代码如下：
    
        package bitmap;
        
        import java.util.Arrays;
        
        /** * @author jiangnanmax * @email jiangnanmax@gmail.com * @description BitMap * @date 2020/12/10 **/
        
        public class BitMap { 
        
            private byte[] slots;
            private int size;
            private int slotCnt;
            private static final int STEPS_PER_SLOT = 3;
            private static final int BITS_PER_SLOT = 1 << STEPS_PER_SLOT;
            private static final int REMAINDER_TAG = 0x07;
        
            public BitMap(int size) { 
                if (size < 0) { 
                    throw new IllegalArgumentException("The init size cannot be negative.");
                }
                this.size = size;
                initSlots(size);
            }
        
            private void initSlots(int size) { 
                slotCnt = slotIndex(size - 1) + 1;
                slots = new byte[slotCnt];
            }
        
            private static int slotIndex(int bitIndex) { 
                return bitIndex >> STEPS_PER_SLOT;
            }
        
            private static int indexInSlot(int bitIndex) { 
                return bitIndex & REMAINDER_TAG;
            }
        
            public boolean valueAt(int offset) { 
                if (offset < 0 || offset > this.size) { 
                    throw new IllegalArgumentException("Index out of bound.");
                }
                return (slots[slotIndex(offset)] & (1 << indexInSlot(offset))) != 0;
            }
        
            public void setValue(int offset, boolean value) { 
                if (offset < 0 || offset > this.size) { 
                    throw new IllegalArgumentException("Index out of bound.");
                }
                if (value) { 
                    slots[slotIndex(offset)] |= (1 << indexInSlot(offset));
                } else { 
                    slots[slotIndex(offset)] &= ~(1 << indexInSlot(offset));
                }
            }
        
            public void and(BitMap other) { 
                if (this.size != other.size) { 
                    throw new IllegalArgumentException("Must have same size");
                }
                for (int i = 0; i < slotCnt; i++) { 
                    this.slots[i] &= other.slots[i];
                }
            }
        
            public void or(BitMap other) { 
                if (this.size != other.size) { 
                    throw new IllegalArgumentException("Must have same size");
                }
                for (int i = 0; i < slotCnt; i++) { 
                    this.slots[i] |= other.slots[i];
                }
            }
        
            public void xor(BitMap other) { 
                if (this.size != other.size) { 
                    throw new IllegalArgumentException("Must have same size");
                }
                for (int i = 0; i < slotCnt; i++) { 
                    this.slots[i] ^= other.slots[i];
                }
            }
        
            public int size() { 
                return this.size;
            }
        
            public void clear() { 
                Arrays.fill(slots, (byte) 0);
            }
        
            @Override
            public boolean equals(Object o) { 
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                BitMap bitMap = (BitMap) o;
                return size == bitMap.size && Arrays.equals(slots, bitMap.slots);
            }
        
            @Override
            public String toString() { 
                return "BitMap{" +
                        "slots=" + Arrays.toString(slots) +
                        ", size=" + size +
                        '}';
            }
        }

[Offer 03.]: https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pfX01heA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/f76f143e94bb4551811e6c59ea0cc217.png