## 引言

• n &（n-1）能够消灭n中最右侧的一个1。
• 右移：除以2， 左移：乘以2。
• 异或性质：交换律，0^a=a, a^a=0;

## 位运算的奇技淫巧

### 两数交换

y = x^y = (x^y)^y = x^(y^y) = x^0 = x。 x 的值成功赋给了 y。

x = x^y = (x^y)^x = (x^x)^y = 0^y = y。

## LeetCode习题 | 位运算之数学运算与位运算

### 29.Divide Two Integers

Divide two integers without using multiplication, division and mod operator.If it is overflow, return MAX_INT.

### 201.Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.For example, given the range [5, 7], you should return 4

### 371.Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -. Example:Given a = 1 and b = 2, return 3.

0^0 = 0；0^1 = 1；1^1 = 0

### 318.Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:
Given [“abcw”, “baz”, “foo”, “bar”, “xtfn”, “abcdef”]
Return 16
The two words can be “abcw”, “xtfn”.
Example 2:
Given [“a”, “ab”, “abc”, “d”, “cd”, “bcd”, “abcd”]
Return 4
The two words can be “ab”, “cd”.
Example 3:
Given [“a”, “aa”, “aaa”, “aaaa”]
Return 0
No such pair of words.

### 190.Reverse Bits

Reverse bits of a given 32 bits unsigned integer.For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

### 476.Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

## LeetCode习题 | 位运算之Single Number系列

### 136.Single Number

Given an array of integers, every element appears twice except for one. Find that single one.Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

### 137.Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

### 260.Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example: Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note: The order of the result is not important. So in the above example, [5, 3] is also correct. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

## LeetCode习题 | 位运算之Hamming weight系列

### 191.Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1’ bits it has (also known as the Hamming weight). For example, the 32-bit integer ’11’ has binary representation 00000000000000000000000000001011, so the function should return 3.

### 461.Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance.

Note: 0 ≤ x, y < 2^31.

Example: Input: x = 1, y = 4 Output: 2

Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑The above arrows point to positions where the corresponding bits are different.

### 477.Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example: Input: 4, 14, 2 Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). So the answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Note: Elements of the given array are in the range of 0 to 10^9. Length of the array will not exceed 10^4.