[go] Bitset implementation + detailed explanation
Intuition\n\nYou can think of a set of ints as an array of bits.\n\nTo add an int n to the set, we set the bit at position n to 1.\nTo remove an int n from the 
# Intuition\n\nYou can think of a set of ints as an array of bits.\n\nTo add an int `n` to the set, we set the bit at position `n` to 1.\nTo remove an int `n` from the set, we set the nth bit to 0.\n\nA byte is a set of 8 bits, which means that to represent a set of 1M int we need 100000 / 8 = 125k bytes.\n\nTo visualise, suppose we only consider ints from 0 to 10.\nThis is our set:\n\n```\n 0 1 2 3 4 5 6 7   8 9 10   <--- n\n[0 0 0 0 0 0 0 0 | 0 0 0]\n ----------------\n  1 byte = 8 bits\n```\n\nTo add the number `3` to our set, we have to first identify which byte holds the bit corresponding to 3.\nThats done by doing `3 / 8 = 0`. <-`3` is found in the first byte.\nThen, within that byte, we need to identify which bit to set.\nThat\'s done by using modulo: `3 % 8 = 3`.\n\nThus we need to set bit 3 of byte 0 to 1.\nUsing bits manipulations, that\'s done by `OR`-ring the 3rd bit:\n\n```go\nv |= 1 << bit\n```\n\nOnce that\'s understood, removing and checking for existence are implemented using the other bitwise operations.\n\n\n# Complexity\n- Time complexity:\nO(1)\n\n- Space complexity:\n125KB O(1)\n\nThis is wasteful in terms of space. We can dynamically allocate the array if the number to add to the set is larger than the current byte array size but it complicates the code a little bit and incurs an extra cost when expanding the array.\n\n# Code\n```\ntype MyHashSet struct {\n    set [125001]byte\n}\n\n\nfunc Constructor() MyHashSet {\n    return MyHashSet{}\n}\n\n\nfunc (this *MyHashSet) Add(key int)  {\n    // find the byte to store the key\n    byt := key / 8\n    bit := key % 8\n    this.set[byt] |= 1 << bit\n}\n\n\nfunc (this *MyHashSet) Remove(key int)  {\n    byt := key / 8\n    bit := key % 8\n    this.set[byt] &= ^(1 << bit)\n}\n\n\nfunc (this *MyHashSet) Contains(key int) bool {\n    byt := key / 8\n    bit := key % 8\n    v := this.set[byt]\n    return v & (1 << bit) != 0\n}\n\n\n/**\n * Your MyHashSet object will be instantiated and called as such:\n * obj := Constructor();\n * obj.Add(key);\n * obj.Remove(key);\n * param_3 := obj.Contains(key);\n */\n```
['Go']