【LeetCode】bit operation

还没写完
我个人认为，以面试来说不太会考位元运算的题目，
因为要在短时间内测出面试者的实力，有其他更好的选择，例如前面基本的资料结构。
但是位元运算对於比较低阶的语言，例如 assembly 或是 C，还是挺重要的。

Common operators

^ xor
& bitwise and
| bitwise or
~ bitwise not
<< 左移
>> 右移

这里介绍一个省空间的方法

直觉上会想用 set 存，
这样判断新元素是否存在可以达到时间 O(1)，但空间需要 O(N)。

而存在不存在这是个二元问题，
此时若用一个 bit array 来做标记，
也就是 0 代表存在，1 代表不存在，
index 则为要标记的英数字。（想办法 mapping）

flags = [1, 0, 0, 1, 1]

再将 bit array encode 成整数

flags = 0b11001(2进位)= 25(10进位)

此时就能将原先需要 N 个整数来标示，现在只需要 1 个整数了。

方法	Time	Space	例子
set	O(1)	O(N)	exist = {1, 4, 5}
bit array	O(1) 把目标设法 mapping 到 index	O(N)	exist = [1, 0, 0, 1, 1]
integer	O(1)	O(1)	exist = 0b11001

确认 num 是否存在 -> 第 i bit（右至左）是否为 1
1 << (num - 1) 产生只有 i bit 为 1 的数字
if flags & (1 << (num - 1)):
if flags & (1 << (num - 1)) == 1: 会错的因为 == 优先

标记 num 存在 -> 第 i bit（右至左）设为 1
flags |= (1 << (num - 1))

题目可以做看看
36. Valid Sudoku

n ^ n = 0
n ^ 0 = n
136. Single Number