Bit Manipulation

题型

XOR:

可以求单身狗，因为a ^ a = 0，所以给定一个数组，如果所有的数的freq都是偶数，只有一个数是奇数。那么最后XOR的结果就是这个单身狗。

XOR和AND配合还可以求sum。因为通过XOR做的是不进位加法，我们可以得到不带carry的加法结果。但是还需要把carry加回去，这时我们做的就是AND运算，记住我们要把AND的结果左移1位才可以得到carry，然后递归求解即可，知道carry == 0退出递归。

题目

XOR + AND

• Leetcode 371. Sum of Two Integers

AND with mark bit 1 to get every bit

• Leetcode 393. UTF-8 Validation
• Leetcode 191. Number of 1 Bits (总共有三种方法去得到一个number的parity，分别是bit shift, erase lowest set bit, array based cache)

除法（用乘法和减法来做）

• Leetcode 29. Divide Two Integers