基础知识

对于位运算，大家都很熟悉，基本的位操作有与(&)、或(|)、非(~)、异或(^)等等。在面试中经常会出现位运算相关的题，所以我就做了简单的整理，参考了很多写的很好的博客及书籍,在此一并谢过。

现在简单说一下，移位运算。

左移运算：x << n。将x左移n位，将x最左边的n位丢弃，在右边补n个0。

右移运算：x >> n。将x右移n位，这需要区分x是有符号数还是无符号数。在x是无符号数时，只需将x的最右边的n位丢弃，在左边补上n个0。在x是有符号数时，又分为x是正数还是负数。正数时，同无符号数的处理相同；负数时，将将x的最右边的n位丢弃，在左边补上n个1。

逻辑右移

1、计算一个数的二进制中1的个数

通过与初始值为1的标志位进行与运算，判断最低位是否为1；然后将标志位左移，判断次低位是否为1；一直这样计算，直到将每一位都判断完毕。

int countOf1(int num){
    int count = 0;
    unsigned int flag = 1;
    while(flag){
        if(num & flag){
            count++;
        }
        flag = flag << 1;
    }
    return count;
}

还有一种方法，一个整数减一，可以得到该整数的最右边的1变为0，这个1右边的0变为1。对这个整数和整数减一进行与运算，将该整数的最右边的1变为0，其余位保持不变。直到该整数变为0，进行的与运算的次数即为整数中1的个数。

x & (x-1) 用于小区x最后一位的1
x = 1100
x - 1 = 1011
x & (x -1) = 1000

int countOf1_2(int num){
    int count = 0;
    while(num)  {
        num = num & (num - 1);
        count++;
    }
    return count;
}

2、判断一个数是否是2的n次方

一个数是2的n次方，则这个数的最高位是1，其余位为0。根据上一题的第二种解法可以很容易得到解决方案。将这个整数与整数减一进行与运算，如果得到的结果为零，可证明该数为2的n次方。

/**
 判断一个数是否为2的n次方（一个数为2的n次方，则最高位为1，其余位为0）
**/
bool is2Power(int num){
    bool flag = true;
    num = num & (num - 1); //计算num和num - 1的与的结果
    if(num) { //如果结果为0，则不是2的n次方
        flag = false;
    }
    return flag;
}

3、整数n经过多少步可以变为整数m

n和m的异或结果可以得知两数不同位的个数，再调用计算一个数中1的个数的方法，即可得到结果。

/*
 求解n变化为m，需要进行的操作步数
*/
int countChange(int n,int m){
    n = n ^ m; //求n和m的异或,再计算结果中1的个数
    return countOf1_2(n);
}

4、获得最大的int值

/*
 获取最大的int
 得到结果：2147483647
*/
int getMaxInt(){
    return (1 << 31) - 1;
}

/*
 使用g++编译，出现warning: left shift count is negative
*/
int getMaxInt_2(){
    return (1 << -1) - 1;
}

int getMaxInt_3(){
    return ~(1 << 31);
}

/*
 在不了解int的长度情况下使用
*/
int getMaxInt_4(){
    return ((unsigned int) -1) >> 1; 
}

5、获得最小的int值

/*
 求最小int
 得到结果：-2147483648
*/
int getMinInt(){
    return 1 << 31;
}

/*
 同样在g++下编译，出现warning: left shift count is negative
*/
int getMinInt_2(){
    return 1 << -1;
}

6、获得最大的long

/*
 求最大long
 得到结果：9223372036854775807
*/
long getMaxLong(){
    return ((unsigned long) -1) >> 1;
}

7、判断一个数的奇偶性

判断奇偶性，实质是判断最后一位是否是1.

/*
 判断一个数的奇偶性.返回1，为奇数;返回0，为偶数
*/
bool isOdd(int num)
{
    return num & 1 == 1;
}

8、交换两个数(不借助第三变量)

不用第三个变量交换两个数的方法也有几种，例如a = a + b; b = a - b; a = a - b。下面这种方法可以实现的基础是一个数m与另一个数n异或，再与n异或，得到的结果是m.

/*
    不适用临时变量，交换两个数
    a = a ^ b
    b = b ^ a
    a = a ^ b
*/
void mySwap(int* a,int* b){
    (*a) ^= (*b) ^= (*a) ^= (*b);
}

9、求一个数的绝对值

下面的方法实现的基础是将n右移31位，可以获得n的符号。

/*
 取绝对值
 n右移31位，可以获得n的符号。若n为正数，得到0；若n为负数，得到 -1
*/
int myAbs(int n){
    return (n ^ n >> 31) - (n >> 31);
}

10、求两个数的平均值

第一种方法较为普遍且简单，不多说了。第二种方法，需要知道的是，( m ^ n ) >> 1得到的结果是m和n其中一个数的有些位为1的值的一半，m & n得到的结果是m 和n都为1的那些位，两个结果相加得到m和n的平均数。

/*
 求m和n的平均数
*/
int getAverage(int m,int n){
    return (m + n) >> 1;
}

/*
 求m和n的平均数
 (m ^ n) >> 1 -> 获得m和n两个数中一个数的某些位为1的一半
 m & n -> 获得m和n两个数中都为1的某些位
*/
int getAverage_2(int m, int n){
    return ((m ^ n) >> 1) + (m & n);
}

11、求解倒数第m位相关问题

/*
    获取n的倒数第m位的值（从1开始计数）
*/
int getMthByTail(int n,int m){
    return (n >> (m - 1)) & 1;
}

/*
    将n的倒数第m位设为1
*/
int setMthByTail21(int n,int m){
    return n | (1 << (m - 1));
}

/*
    将n的倒数第m位设为0
*/
int setMthByTail20(int n,int m){
    return n & ~(1 << (m - 1));
}

12、使用二进制进行子集枚举

例：给定一个含不同整数的集合，返回其所有的子集。

输入：[0]
输出：
[
[],
[0]
]

输入：[1,2,3]
输出：
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

思路就是使用一个正整数二进制表示的第i位是1还是0，代表集合的第i个数 取或者不取。所以从0到2^n-1总共2n个证书，正好对应集合的2^n个子集。

S = {1,2,3}
N    bit    Combination
0    000  {}
1    001  {1}
2    010  {2}
3    011  {1,2}
4    100  {3}
5    101  {1,3}
6    110  {2,3}
7    111  {1,2,3}

/**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        
        if (nums == null) {
            return results;
        }
        
        if (nums.length == 0) {
            results.add(new ArrayList<Integer>());
            return results;
        }
        
        Arrays.sort(nums);
        helper(new ArrayList<Integer>(), nums, 0, results);
        return results;
    }

// 递归三要素
    // 1. 递归的定义：在 Nums 中找到所有以 subset 开头的的集合，并放到 results
    private void helper(ArrayList<Integer> subset,
                        int[] nums,
                        int startIndex,
                        List<List<Integer>> results) {
        // 2. 递归的拆解
        // deep copy
        // results.add(subset);
        results.add(new ArrayList<Integer>(subset));
        
        for (int i = startIndex; i < nums.length; i++) {
            // [1] -> [1,2]
            subset.add(nums[i]);
            // 寻找所有以 [1,2] 开头的集合，并扔到 results
            helper(subset, nums, i + 1, results);
            // [1,2] -> [1]  回溯
            subset.remove(subset.size() - 1);
        }
        
        // 3. 递归的出口
        // return;
    }

13、a ^ b ^ b = a

例1: 给出 2 * n + 1个数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。（n≤100）

• 思路
  因为只有一个数恰好出现一个，剩下的都出现过两次，所以只要将所有的数异或起来，就可以得到唯一的那个数。

public class Solution {
    public int singleNumber(int[] A) {
        if(A == null || A.length == 0) {
            return -1;
        }
        int rst = 0;
        for (int i = 0; i < A.length; i++) {
            rst ^= A[i];
        }
        return rst;
    }
}

例2: 给出3*n + 1 个非负整数，除其中一个数字之外其他每个数字均出现三次，找到这个数字。

输入: [1,1,2,3,3,3,2,2,4,1]
输出: 4

• 思路
  因为数是出现三次的，也就是说，对于每一个二进制位，如果只出现一次的数在该二进制位为1，那么这个二进制位在全部数字中出现次数无法被3整除。 膜3运算只有三种状态：00,01,10，因此我们可以使用两个位来表示当前位%3，对于每一位，我们让Two，One表示当前位的状态，B表示输入数字的对应位，Two+和One+表示输出状态。

public class Solution {
    public int singleNumberII(int[] A) {
        if (A == null || A.length == 0) {
            return -1;
        }
        int result=0;
        int[] bits=new int[32];
        for (int i = 0; i < 32; i++) {
            for(int j = 0; j < A.length; j++) {
                bits[i] += A[j] >> i & 1;
                bits[i] %= 3;
            }

            result |= (bits[i] << i);
        }
        return result;
    }
}

例3: 给出2*n + 2个的数字，除其中两个数字之外其他每个数字均出现两次，找到这两个数字。

• 思路
  假设两个落单数字是 A、B
  2*n + 2 个数字异或，会得到两个仅出现一次的数字的异或结果：xor = A^B。
  其中我们取出xor中任何一位1，这里取最低位的1。
  这个1一定是A和B中对应位上一个是1一个是0。
  所以可以将所有数字分成两类，一类是该位是1的，一类是该位是0的。
  分别异或起来就得到A和B了。两类数一定都是奇数个，多出来的一个分别就是A、B。

样例 1:
输入: [1,2,2,3,4,4,5,3]
输出: [1,5]

public class Solution {
    public List<Integer> singleNumberIII(int[] A) {
        int xor = 0;
        for (int i = 0; i < A.length; i++) {
            xor ^= A[i];
        }
        
        int lastBit = xor - (xor & (xor - 1));
        // int lastBit = xor & (-xor); // 两句一样的作用，只保留xor的最后一个1。
        int group0 = 0, group1 = 0;
        for (int i = 0; i < A.length; i++) {
            if ((lastBit & A[i]) == 0) {
                group0 ^= A[i];
            } else {
                group1 ^= A[i];
            }
        }
        
        ArrayList<Integer> result = new ArrayList<Integer>();
        result.add(group0);
        result.add(group1);
        return result;
    }
}

13、不用加号求和

给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符

主要利用异或运算来完成，异或运算有一个别名叫做：不进位加法。
那么a ^ b就是a和b相加之后，该进位的地方不进位的结果，相信这一点大家没有疑问，但是需要注意的是，这个加法是在二进制下完成的加法。
然后下面考虑哪些地方要进位？

什么地方需要进位呢？ 自然是a和b里都是1的地方

a & b就是a和b里都是1的那些位置，那么这些位置左边都应该有一个进位1，a & b << 1 就是进位的数值(a & b的结果所有左移一位)。

那么我们把不进位的结果和进位的结果加起来，就是实际中a + b的和。

a + b = (a ^ b) + (a & b << 1)

令
a' = a ^ b, b' = (a & b) << 1 => a + b = (a ^ b) + (a & b << 1) = a' + b'

然后反复迭代，这个过程是在二进制下模拟加法的运算过程，进位不可能一直持续，所以b最终会变为0，也就是没有需要进位的了，因此重复做上述操作就可以
最终求得a + b的值

class Solution {
    public int aplusb(int a, int b) {
        while (b != 0) {
            int _a = a ^ b;
            int _b = (a & b) << 1;
            a = _a;
            b = _b;
        }
        return a;
    }
};

14、取一个除数是2的正整数次方数的余数

有时候要做一些取余（模）的运算，而除数恰好是2的次方数常量（因为做程序时，经常会把一些会重复运算的关键数值取成2、4、8等），可用如下方法：
取i除以4的余数，用：num=i&3
取i除以8的余数，用：num=i&7
取i除以16的余数，用：num=i&15

15、实现对一个数字做除法后再取整（除数是2的正整数次方数）

有时候算坐标，有时候算索引之类，方法如下：
比如，把number除以4的结果取整，一般写成int(number/4)
用位运算，写成number>>2即可.
运算效率会高得多！