位运算以及位图

计算机中的数在内存中都是以二进制形式进行存储的，用位运算就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。

位操作符

与&

1 0 0 1 1 
1 1 0 0 1 
------------------------------
1 0 0 0 1

与运算 两个位都是 1 时，结果才为 1，否则为 0

或 |

1 0 0 1 1 
1 1 0 0 1 
------------------------------
1 1 0 1 1

或运算 两个位都是 0 时，结果才为 0，否则为 1

异或运算 ^

即无进位相加

1 0 0 1 1 
1 1 0 0 1 
-----------------------------
0 1 0 1 0

异或运算，两个位相同则为 0，不同则为 1

1. 0 ^ N = N, N ^ N = 0

2. 异或运算满足交换律与结合律

使用无进位相加理解上述两个性质非常容易

取反运算 ~

1 0 0 1 1 
-----------------------------
0 1 1 0 0

取反运算，0 则变为 1，1 则变为 0

左移运算 <<

int a = 8;
a << 3;
移位前：0000 0000 0000 0000 0000 0000 0000 1000
移位后：0000 0000 0000 0000 0000 0000 0100 0000

左移运算，向左进行移位操作，高位丢弃，低位补 0

• 对一个数进行左移一次相当于 * 2

• 左移n次，相当于* (2 ^ n)

右移运算 >>

unsigned int a = 8;
a >> 3;
移位前：0000 0000 0000 0000 0000 0000 0000 1000
移位后：0000 0000 0000 0000 0000 0000 0000 0001

右移运算，向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位

• 对一个数右移一次相当于 / 2

• 右移n次，相当于 / (2 ^ n)

无符号右移运算 >>>

unsigned int a = -1;
a >>> 1;
移位前：0000 0000 0000 0000 0000 0000 0000 1000
移位后：0000 0000 0000 0000 0000 0000 0000 0001

无符号右移运算，向右进行移位操作，高位补 0

负数的表示

计算机32位int值，如果是无符号整型，可以表示的数字范围位0 ~ 2^32-1，如果是有符号整型，可表示的数字范围为-2^31 ~ 2^31-1，包含0，他们都共可以表示 2 ^ 32个数字。

无符号整型将所有32位都作为值存储，而有符号整型则将最高位作为符号位，当符号位为0代表该数字为非负数（可能为0以及正数），如果符号位数字为1，代表该数字为负数，比如在Java中：

print(Integer.MAX_VALUE); // 01111111111111111111111111111111  int最大值 正值
print(Integer.MIN_VALUE); // 10000000000000000000000000000000  int最小值 负值
print(1);  // 00000000000000000000000000000001
print(-1); // 11111111111111111111111111111111

负数二进制表示的计算：

假设负数 -1：
最高位也就是符号位为1，也就是 100....00
后面的31位表示数字值，对绝对值使用取反加一计算：
原值 => 100....01 
取反 => 111....10
加一 => 111....11  这个值就是 -1 的二进制表示

----------

假设负数位 Integer最小值也就是 -2^31
最高位也就是符号位为1，也就是 100....00
后面的31位表示数字值，对绝对值使用取反加一计算：
原值 => 1100....000 注意，这里溢出一位
取反 => 1011....111
加一 => 1111....111
结果 => 1111....11 溢出的一位直接去除，这个值就是 -2^31的二进制表示

取反加一就是二进制的补码。

为什么负数要使用二进制补码的形式？

参考：https://blog.csdn.net/leonliu06/article/details/78685197

总结：一种巧妙地设计，也是一种规定，为了提高二进制计算的效率

常见的位运算问题

32位int转换为二进制字符串

/**
 * 打印数字的二进制表现字符串
 */
public static void print(int num) {
  for (int i = 31; i >= 0; i--) {
    System.out.print((num & (1 << i)) == 0 ? "0": "1");
  }
  System.out.println();
}

说明：便利32位int的每一位，将每位的状态打印。比如，第一位与 100....00相与，可得到该数第一位的状态；第二位与0100...0相与，可得到第二位的状态，一直到第最后一位，从 31 到 0。

交换数字（异或）

a ^= b;
b ^= a;
a ^= b;

原理：

int a = x;
int b = y;
a ^= b;  // a = x ^ y;
b ^= a;  // b = y ^ x ^ y;   b = x;
a ^= b;  // a = x ^ y ^ x;   a = y;

注意：

public static void swap(int[] arr, int i, int j) {
  arr[i] ^= arr[j];
  arr[j] ^= arr[i];
  arr[i] ^= arr[j];
}
swap(arr, 0, 1); // 正确
swap(arr, 0, 0); // 错误，arr[i] 与 arr[j] 会都变为0，这是因为arr[i] 与 arr[j] 共用一块内存，如下
// arr[i] ^= arr[j]; // arr[i] = x ^ x;     arr[i] = 0;
// arr[j] ^= arr[i]; // arr[j] = 0 ^ 0;     arr[j] = 0; 
// arr[i] ^= arr[j]; // arr[i] = 0 ^ 0;     arr[i] = 0;

判断奇偶数

if(0 == (a & 1)) {
 //偶数
}

正负切换（补码）

int reversal(int a) {
  return ~a + 1;
}

绝对值

int abs(int a) {
  int i = a >> 31; // 获取符号位
  return i == 0 ? a : (~a + 1); // 符号位为0=>正数不变返回，符号位为1=>负数取反加一返回
}

高低位交换

34520的二进制表示：
10000110 11011000

将其高8位与低8位进行交换，得到一个新的二进制数：
11011000 10000110
其十进制为55430

unsigned short a = 34520;
a = (a >> 8) | (a << 8);
// 1. a >> 8 得到高8位  00000000 10000110
// 2. a << 8 得到低8位  11011000 00000000
// 3. (a >> 8) | (a << 8) 得到 11011000 10000110

统计二进制中 1 的个数

/**
 * 统计二进制数中1的个数
 */
public static int count(int num) {
  int count = 0;
  for (int i = 31; i >= 0; i--) {
    count += (num & (1 << i)) == 0 ? 0 : 1;
  }
  return count;
}

统计二进制1的个数可以分别获取每个二进制位数，然后再统计其1的个数，此方法效率比较低。这里介绍另外一种高效的方法，同样以 34520 为例，我们计算其 a &= (a-1)的结果：

• 第一次：计算前：1000 0110 1101 1000 计算后：1000 0110 1101 0000

• 第二次：计算前：1000 0110 1101 0000 计算后：1000 0110 1100 0000

• 第二次：计算前：1000 0110 1100 0000 计算后：1000 0110 1000 0000 我们发现，没计算一次二进制中就少了一个 1，则我们可以通过下面方法去统计：

count = 0  
while(a){  
  a = a & (a - 1);  
  count++;  
}  

位运算实现加减乘除

计算机底层都是使用位运算实现加减乘除。

加法

a = 46; => 0010 1110
b = 20; => 0001 0100

// 使用异或获取无进位相加的结果
a ^ b   => 0011 1010  => 58
// 由上面可知，进位信息位于第三位
// 可以使用先&获取同为1的位置，再左移获取进位信息
a & b   => 0000 0100
a & b << 1 => 0000 1000  => 8
// 加法和就等于 无进位相加和 + 进位
58 + 8 = 66

// 继续使用上述方式计算 58 + 8
a = 58; => 0011 1010
b = 8;  => 0000 1000
a ^ b;  => 0011 0010 => 50
a & b;  => 0000 1000
a & b << 1 => 0001 0000 => 16

// 继续使用上述计算方式计算 50 + 16 
a = 50; => 0011 0010
b = 16; => 0001 0000
a ^ b;  => 0010 0010; => 34
a & b;  => 0001 0000;
a & b << 1; => 0010 0000; => 32

//继续使用上述计算方式计算 34 + 32
a = 34; => 0010 0010;
b = 32; => 0010 0000;
a ^ b;  => 0000 0010;  => 2
a & b;  => 0010 0000; 
a & b << 1; => 0100 0000; =>  64

// 继续使用上述计算方式计算 64 + 2
a = 64; => 0100 0000;
b = 2;  => 0000 0010;
a ^ b;  => 0100 0010; => 66
a & b;  => 0000 0000;
没有进位，那么此时a ^ b 的结果就是该加法的结果。

java实现：

public static int add(int a, int b) {
  int sum = a;
  while (b != 0) {
    sum = a ^ b;
    b = (a & b) << 1;
    a = sum;
  }
  return sum;
}

减法

// 减法就是 a + (-b)， 一个数的相反数可以用 ~b + 1来表示
public static int minus(int a, int b) {
  return add(a, add(~b, 1));
}

乘法

乘法的实现方式是乘法的竖式表达程序化：

  23
x 12
----
  46
 23
----
 276
 
二进制表现相同：
    10111
x    1100
-----------
    00000
   00000
  10111
 10111
-----------
100010100   =>  276

程序化：

// 乘法
public static int multi(int a, int b) {
  int bi;
  int result = 0;
  int count = 0;
  while (count < 32) {
    bi = b & (1 << count);
    if (bi != 0) {
      result = add(result, a << count);
    }
    count++;
  }
  return result;
}

// 乘法更简单的实现
// b每次向右侧移动一位，即可取到某位的状态
public static int multi2(int a, int b) {
  int res = 0;
  while (b != 0) {
    if ((b & 1) != 0) {
      res = add(res, a);
    }
    a <<= 1;
    b >>>= 1;
  }
  return res;
}

除法

举例说明
41 / 3
3 * 2 ^ 0 = 3 < 41
3 * 2 ^ 1 = 6 < 41
3 * 2 ^ 2 = 12 < 41
3 * 2 ^ 3 = 24 < 41
3 * 2 ^ 4 = 48 > 41 

商=2^3
对余数继续除：
41 - 24 = 17
17 / 3 
3 * 2 ^ 0 = 3  < 17 
3* 2 ^ 1 = 6 < 17
3 * 2 ^ 2 = 12 < 17 
3 * 2 ^ 3 = 24 > 17 

商 =  2^3 + 2^2
对余数继续除
17 - 12 = 5 
3 * 2 ^ 0 = 3 < 5
3 * 2 ^ 1 = 6 > 5

商 = 2^3 + 2^2 + 2^0 
5 - 3 = 2
2 < 3 不继续除

所以，41 / 3 = 2^3 + 2^2 + 2^0 = 13

使用除2的方式是因为2可以使用位运算替代。这种方式实际就是不断的减去被除数，并计算被减的次数。

Java代码实现如下：

控制某一位

假设有二进制数1011 0110：

1. 控制这个二进制数的最高位变为0：

    1011 0110
   &0111 1111
    0011 0110

2. 控制这个二进制数的最低位变为1：

    1011 0110
   |0000 0001
    1011 0111

java实现：

/**
 * 设置二进制数的某一位
 * @param num 二进制数
 * @param pos 位置
 * @param flag true => 1， false => 0
 */
public static int set(int num, int pos, boolean flag) throws IllegalArgumentException{
    if (pos < 0 || pos > 31) {
        throw new IllegalArgumentException();
    }
    if (flag) {
        num |= (1 << pos);
        return num;
    }
    
    num &= ~ (1 << pos);
    return num;
}

位图的实现

Java:

static class BitMap {
  // 1个long类型可以存储64位
  // 使用一个long类型数组存储bit位图
  private final long[] bits;

  // 根据max确定数组的长度
  // 如果 max 属于 0 ~ 63 则数组长度为1
  // 如果 max 属于 0 ~ 127 则数组长度为2
  public BitMap(int max) {
    if (max < 0) throw new IllegalArgumentException();
    bits = new long[(max + 64) >> 6]; // 等同于 (size + 64) / 64
  }

  // 将某个位置置为1，位置索引从0开始
  public void add(int num) {
    // 1. 确定num位置属于数组的第几个整数元素： 0/64=0, 64/64=1, 127/64=1, 128/64=2
    //    故元素位置= num / 64 也就是  num >> 6
    // 2. 确定num位于已确定的整型元素的第几位： 0%64=0, 1%64=1, 127%64=63, 128%64=0
    //    故num位置位于整型元素的第  num%64位。num%64 等同于 num&63：
    //    num%64等同于只保留二进制的最后6位，前面的位数全部去除，所以 num & 63 = num % 64
    // 3. 将指定位置1，使用 |，比如将第2位置1 
    //    0000 | 0100 = 0100
    //    0100 => 1 << (num & 63)
    // 故结果如下：
    bits[num >> 6] |= (1L << (num & 63));
  }

  public void delete(int num) {
    // 1. 确定num位置属于数组的第几个整数元素: num >> 6
    // 2. 确定num位于已确定的整型元素的第几位: num % 64 => num & 63
    // 3. 将指定位置0，使用&，比如将第二位置0
    //    1111 & 1011 = 1011
    //    1011 => ~0100
    // 故结果如下
    bits[num >> 6] &= ~(1L << (num & 63));
  }

  public boolean contains(int num) {
    // 1010 & 0100 => 0000 说明第二位是0，否则第二位是1
    return (bits[num >> 6] & (1L << (num & 63))) != 0;
  }
}

面试题

异或

一个数组中有一个数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这个数字？

// 给定数组 [4, 1, 3, 3, 2, 1, 3, 1, 2, 3, 2, 1, 4]
// 其中 1共有4个，2共有3个，3共有4个，4共有2个
// 找到个数为奇数的数字，也就是2
// 使用异或
public static void main(String[] args) {
  int[] arr = {4, 1, 3, 3, 2, 1, 3, 1, 2, 3, 2, 1, 4};
  int t = 0;
  for (int i = 0; i < arr.length; i++) {
    t ^= arr[i];
  }
  System.out.println(t); // 2
}

原理：

1. 满足交换律，所以 4, 1, 3, 3, 2, 1, 3, 1, 2, 3, 2, 1, 4即为：1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4

2. 相同的数字异或为0， 所以上述数字偶数个的都会被异或为0，奇数个的最中会剩余一个数字

---

怎么将一个int类型的数，提取出他二进制最右侧的1来？

public static void main(String[] args) {
  int N = 200;
  System.out.println(Integer.toBinaryString(N)); // 11001000

  // 提取最右侧的1，使用公式：N & ((~N) + 1)
  int result = N & ((~N) + 1);
  System.out.println(Integer.toBinaryString(result)); // 1000
}

推算过程：

原数 .... 0000 0000 1100 1000
取反 .... 1111 1111 0011 0111
加一 .... 1111 1111 0011 1000
相与 .... 0000 0000 0000 1000

---

一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数？

// 假设两个奇数为 a 和 b
// eor = 将数组中所有元素相互异或
// eor = a ^ b != 0
// 因为eor != 0，故eor 在至少有一个位置上一定有1，所以 a 和 b 在这些位置上的 0 与 1 的状态一定不一致
// 取eor出最右侧的1，与数组的所有元素相与，可以得出该位置为1的所有元素，其中一定含有 a 或者 b
// 将这些元素再次相互异或，可以得到 a 或者 b， 根据 eor = a ^ b; a = eor ^ b; 故而得到 a 和 b
// 代码如下：
// 假设两个奇数为 a 和 b
// eor = 将数组中所有元素相互异或
// eor = a ^ b != 0
// 因为eor != 0，故eor 在至少有一个位置上一定有1，所以 a 和 b 在这些位置上的 0 与 1 的状态一定不一致
// 取eor出最右侧的1，与数组的所有元素相与，可以得出该位置为1的所有元素，其中一定含有 a 或者 b
// 将这些元素再次相互异或，可以得到 a 或者 b， 根据 eor = a ^ b; a = eor ^ b; 故而得到 a 和 b
// 代码如下：
public static void printOddNum2(int[] arr) {
    int eor = 0;
    for (int i = 0; i < arr.length; i++) {
        eor ^= arr[i];
    }
    int rightOne = eor & (~eor + 1);
    int aOrB = 0;
    for (int i = 0; i < arr.length; i++) {
        if ((arr[i] ^ rightOne) == 0) {
            aOrB ^= arr[i];
        }
    }
    System.out.println(aOrB + "  " + (eor ^ aOrB));
}

---

找到数字N的二进制的含有1的数量？

// 以rightOne作为判断条件
public static int bit1Count(int n) {
   int count = 0;
   int rightOne;
   while (true) {
     // 找到最右侧的1
     rightOne = n & (~n + 1);
     if (rightOne == 0) {
       return count;
     }
     count ++;
     // 抹掉最右侧的1
     n ^= rightOne;
   }
 }

// 以n数字作为判断条件
public static int bit1Count2(int n) {
  int count = 0;
  int rightOne;
  while (n != 0) {
    // 找到最右侧的1
    rightOne = n & (~n + 1);
    count ++;
    n ^= rightOne;
  }
  return count;
}