Python | bit manipulation | set()
it took me forever to understand it, until I found #\u5C71\u666F\u57CE\u4E00\u59D0 on youtube \n\n\nclass Solution:\n    def findMaximumXOR(self, nums: List[int
it took me forever to understand it, until I found #\u5C71\u666F\u57CE\u4E00\u59D0 on youtube \n\n```\nclass Solution:\n    def findMaximumXOR(self, nums: List[int]) -> int:\n        sol = 0\n        for i in reversed(range(32)):\n            prefixs = set([x >> i for x in nums])\n            sol <<= 1\n            candidate = sol + 1\n            for p in prefixs:\n                if candidate ^ p in prefixs:\n                    sol = candidate\n                    break\n        return sol\n```\n\nwith note:\n```\nclass Solution:\n    def findMaximumXOR(self, nums: List[int]) -> int:\n        sol = 0 \n        for i in reversed(range(32)): # XOR from left, border=2^32\n            prefixs = set([x >> i for x in nums]) # right shift (shrink) for i bits, keep left part\n            sol <<= 1 # left shift (expand 0 on right) for each stage \n            candidate = sol + 1 # expected value to find on set()\n            for p in prefixs:\n                if candidate ^ p in prefixs: # apply rule: a^b=c so a^c=b to search targets\n                    sol = candidate # update the largest solution we could obtain in current stage\n                    break\n        return sol\n```\n\n- Basic knowledge for this solution\n    1. Decimal vs Binary:\n\n    [3,  10,   5,   25,    2,   8]\n    [11, 110,  101, 11001, 10,  1000]\n\n    as 16, 8, 4, 2, 1 for either [1, 0]\n\n    2. Bitwise left shift:\n\n    ```\n    d<<i\n    1<<1 = 10\n    1<<2 = 100\n    1<<3 = 1000\n    <<: append 0 after d for i time\n    ```\n\n    3. Bitwise operators: XOR(^) and basic rule\n\n    ```\n    T F | sol\n    1 1 |  0\n    1 0 |  1\n    0 1 |  1\n    0 0 |  0\n\n    * no carry-over, so we could xor 2 numbers from left to right\n\n    example:\n    ask 5 ^ 25\n    = 101 ^ 11001\n    ==> 11001\n       ^00101\n        -----\n    \t= 1     # 1^0=1\n      = 11    # 1^0=1\n      = 111   # 1^0=1\n      = 1110  # 0^0=0\n      = 11100 # 1^1=0\n\n    and 11100 = 28\n    -----------------------\n    Rule:\n    if a^b=c, then a^c=b\n    we could apply it as classic 2sum question on set(), which will save more time & space\n\n    example:\n    we know 5^25=28\n    so 5^28=25 based on the rule\n    ```\n\n    4. Greedy algorithm\n\n    If we could scan binary values from left\u2192right and obtain most-left bit(most significant bit), it will guarantee we always stay on locally optimal choice on each stage\n\n    example from wiki:\n\t\t![image](https://assets.leetcode.com/users/images/e0bbbc27-fca7-485c-abef-a99b7a22d930_1619065381.3485532.png)\n\n\n    5. Set()\n    in classic 2sum question, we could avoid double for-loop for O(n^2) solution\n    by simply pass all value to set() then search set() return when target-current in set()\n\n    ------------------------\n**Default sample walk through**\n```\n\n    [11, 110,  101, 11001, 10,  1000]\n\n    since max length = 5\n\n    convert them to binary of length=5\n\n    00011\n\n    00110\n\n    00101\n\n    11001\n\n    00010\n\n    01000\n\n    only keep most index=0 from left\n\n    0|  0000\n\n    0|  0000\n\n    0|  0000\n\n    1|  0000\n\n    0|  0000\n\n    0|  0000\n\n    store to set() became\n\n    0|  0000\n\n    1|  0000\n\n    apply rule: a^b=c so a^c=b on here,\n\n    we want 10000, so we use 10000^prefix on set() to find if it exists on set()\n\n    if it exists, based on rule, it will guarantees we have 2 numbers on set() will return 10000 after XOR\n\n    then we update our max_result sol = 10000\n\n    index = 1, we only keep 2 digits from left, and we are looking for 11000\n\n    00|  000\n\n    01|  000\n\n    00|  000\n\n    11|  000\n\n    00|  000\n\n    01|  000\n\n    pass them to set()\n\n    00|  000\n\n    01|  000\n\n    11|  000\n\n    we use 11000^prefix from set(), turns out 11000^00000 = 11000, and it exists on set(), so update max_result sol = 11000\n\n    -if we can\'t find a match on set(), we simply end the current iteration, then looking for the next most significant bit...\n```
['Bit Manipulation', 'Ordered Set', 'Python']