Java 常用的二进制操作

转载自：JAVA中常用的二进制位操作

补充：位运算符

在 Java 中，int 数据底层以补码形式存储。int 型变量使用 32bit 存储数据，其中最高位是符号位，0 表示正数，1 表示负数，可通过 Integer.toBinaryString() 转换为 bit 字符串，

// 若最高的几位为 0 则不输出这几位，从为 1 的那一位开始输出
System.out.println(Integer.toBinaryString(10)); 
System.out.println(Integer.toBinaryString(-10));

// 以上会输出（手工排版过，以下的输出均会被手工排版）：
                            1010
11111111111111111111111111110110

左移 << 符号的使用

例如：5 << 2 = 20

首先会将 5 转为 2 进制表示形式: 0000 0000 0000 0000 0000 0000 0000 0101  

然后左移 2 位后，低位补 0：     0000 0000 0000 0000 0000 0000 0001 0100  
换算成 10 进制为 20

右移 >> 运算符

例如：5 >> 2 = 1

还是先将 5 转为 2 进制表示形式：  0000 0000 0000 0000 0000 0000 0000 0101 
然后右移 2 位，高位补 0：        0000 0000 0000 0000 0000 0000 0000 0001
换算成十进制后是 1

无符号右移 >>> 运算符

例如：5 >>> 3

我们知道在 Java 中 int 类型占 32 位，可以表示一个正数，也可以表示一个负数。正数换算成二进制后的最高位为 0，负数的二进制最高为为 1。

对于 2 进制补码的加法运算，和平常的计算一样，而且符号位也参与运算，不过最后只保留 32位

-5 换算成二进制： 1111 1111 1111 1111 1111 1111 1111 1011
-5 右移3位：     1111 1111 1111 1111 1111 1111 1111 1111   // (用1进行补位，结果为-1)
-5 无符号右移3位: 0001 1111 1111 1111 1111 1111 1111 1111   // (用0进行补位,结果536870911 )

正数二进制中 1 的个数

//求解正数的二进制表示法中的 1 的位数
private static int countBit(int num){
    int count = 0;
    for(; num > 0; count++)
    {
        num &= (num - 1);
    }
    return count;
}

算法思路：每次 for 循环，都将 num 的二进制中最右边的 1 清除。

为什么 n &= (n – 1) 能清除最右边的1呢？

因为从二进制的角度讲，n 相当于在 n - 1 的最低位加上1。

举个例子：

8（1000）= 7（0111）+ 1（0001）

所以 8 & 7 = （1000）&（0111）= 0（0000），清除了 8 最右边的 1（其实就是最高位的 1，因为 8 的二进制中只有一个1）。

再比如：

7（0111）= 6（0110）+ 1（0001）

所以 7 & 6 = （0111）&（0110）= 6（0110），清除了 7 的二进制表示中最右边的 1（也就是最低位的 1）。

求中点的大小

int mid = L + ((R - L) >> 1); // 中点

等价于

int mid = (L + R) / 2;

为什么要使用第一种方法呢？因为 L + R 如果数特别大，可能会有溢出的情况，这样就会导致结果不正确

// 上面的 mid 为了溢出也可以这样写
int mid = L + (R - L) / 2; // 就是直接加上两数之间的差

// 对上面这种操作简化（图一乐），就成了下面这种右移操作
int mid = L + ((R - L) >> 1);

判断某个数的第 i 位是0 还是 1？

思路：

• 如果第 i 位 与 1 相与 结果为 1 表明第 i 位为 1；
• 如果为 0 表明第 i 位为 0

//获取 整数 num 的第 i 位的值
private static boolean getBit(int num, int i)
{
    return ((num & (1 << i)) != 0); //true 表示第i位为1,否则为0
}

1 左移 i 位后，得到一个数，这个数只有第 i 位为 1，其它位都为 0

快速找到右边第一位 1 的位置

例如快速找到这个 eor 右边第一位 1 的位置

// 快速的方法（~eor + 1 就是求补码）
int rightOne = eor & (~eor + 1);

// 等价于下面这种
int rightOne = 0;
while ((eor & rightOne) == 0)
    rightOne = rightOne << 1; //找到从右边开始第一个1的位置

将第 i 位设置为 1

思路：

• 第 i 位与 0 “或”，值不变。
• 第 i 位与 1 “或”，变成 1。

因此，我们的目标是 num 与 一个第 i 位值为 1，其它位的值都为 0 的数相 “或”

//将 整数 num 的第 i 位的值 置为 1
private static int getBit(int num, int i)
{
    return (num | (1 << i));
}

将第 i 位设置为 0

思路：

• 第 i 位和 0 “与”，第 i 位就变成了 0。
• 其它位 都与 1 “与”，其它位保持不变。

这样，就只把第 i 位清 0 了

//将 整数 num 的第 i 位的值 置为 1
private static int getBit(int num, int i)
{
   int mask = ~(1 << i); //111011
   return (num & (mask));
}

注：~ 按位取反运算符翻转操作数的每一位，即 0 变成 1，1 变成 0。

例如：A 的值为 60，~A 得到 -61，即 1100 0011

不用加减乘除做加法

补充知识：^：就是比较当前位置是否相同，相同返回 0，不相同返回 1

A = 0011 1100
B = 0000 1101

-----------------
A & B = 0000 1100
A | B = 0011 1101
A ^ B = 0011 0001
~A    = 1100 0011

1、两个数异或：相当于每一位相加，而不考虑进位； 2、两个数相与，并左移一位：相当于求得进位； 3、将上述两步的结果相加

所以：

public int Add(int num1,int num2) {
    while( num2 != 0 ) {
        int sum = num1 ^ num2; // 取得相加各位的值
        int carray = (num1 & num2) << 1; // 取得进位的值
        num1 = sum;
        num2 = carray;
    }
    return num1;
}

原理：

首先看十进制是如何做的： 5+7=12，三步走

第一步：相加各位的值，不算进位，得到 2。
第二步：计算进位值，得到 10。 如果这一步的进位值为 0，那么第一步得到的值就是最终结果。
第三步：重复上述两步，只是相加的值变成上述两步的得到的结果 2 和 10，得到 12。

同样我们可以用三步走的方式计算二进制值相加： 5-101，7-111 

第一步：相加各位的值，不算进位，得到 010。（二进制每位相加就相当于各位做异或操作，101 ^ 111）
第二步：计算进位值，得到 1010。（相当于各位做与操作得到 101，再向左移一位得到 1010，(101 & 111) << 1）
第三步：重复上述两步， 各位相加 010^1010=1000，进位值为 100 = (010 & 1010) << 1。
继续重复上述两步：1000^100 = 1100，进位值为 0，跳出循环，1100 为最终结果。

异或 ^ 运算

^：就是比较当前位置是否相同，相同返回 0，不相同返回 1

A = 0011 1100
B = 0000 1101

A ^ B = 0011 0001

^ 有两个性质：

1. 0 ^ N = N 和 N ^ N = 0
2. 异或运算满足交换律和结合律

交换律
a ^ b = b ^ a

结合律
a ^ b ^ c = a ^ (b ^ c)

所以可以利用 ^ 来直接交换两数的值，这样可以避免开辟一个临时空间

a = a ^ b;
b = a ^ b;
a = a ^ b;
// 等价于，下面这样交换 a b 的值
temp = a;
a = b;
b = temp;

是什么原理呢？

// 为了方便，这里令：
a = 甲;
b = 乙;

//1、a = 甲 ^ 乙       b = 乙
a = a ^ b; 
//2、a = 甲 ^ 乙       b = 甲 ^ 乙 ^ 乙
// 因为 N ^ N = 0 的性质，加上结合律，所以这里 b 就直接等于 甲
b = a ^ b;
//3、a = 甲 ^ 乙 ^ 甲  b = 甲 
// 同理，这里 a 就等于 乙 了
a = a ^ b; 

所以交换 arr 的 i 和 j 位置上的值，可以这样写

public static void swap(int[] arr,int i,int j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

但是这种写法有个问题，就是要避免交换的两块值是指向同一块 内存区域 的

// 下面这样的值虽然相同，但是两块内存还是不一样的
int a = 10;
int b = 10;

// 但是像数组交换这种，就要避免 i 位置等于 j 位置，不然它会被抹成零
public static void swap(int[] arr,int i,int j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

例题：查找出现奇数次的数

给定一个正数数组，其中所有数字出现偶数次，只有一个数字出现奇数次。 我们需要使用最小的时间复杂度和空间来查找特殊数字（该数字在数组中出现奇数次）。

这种时候就可以使用异或运算 ^

// 创建一个变量
int eor = 0;
// 遍历这个数组，令它从头异或到尾
for(int cur : arr) {
    eor ^= cur;
}

// 最后剩下的那个数就是目标数
target = eor;

就是利用了 0 ^ N = N 和 N ^ N = 0

找两个奇数次的数

把上面那道题进阶一下，整型数组中其他数都出现偶数次，有两个奇数次的数，找出这两个数

原理同上，首先申请变量 eor，初始化为 0，去异或数组中每一个元素，eor 最终的结果就是两个出现奇数次的数的异或，记为 a ^ b。

此时我们要做的就是，先单独求出一个 a 或 b，然后就可以根据 eor ^ a（或者 eor ^ b）求出另一个结果。怎么做呢？

1、因为 eor = a ^ b，所以 eor 的二进制表达中为 1 的位置就是 a 与 b 二进制表达中不同的位置。

2、所以 只需找到 eor 上最右边第一个出现 1 的位置（这个位置其实可以随便找，因为最终目的只是需要把 a 与 b 分组而已，也可以找从左开始数的第一个 1，但是求右边的第一个 1 可以使用补码 & 原码的方式快速求得）

3、再次遍历数组的时候，就判断这个位置上是否为 1，基此把他们划分成两部分，这样每一部分只有 a 或者 b 其中一个了，再次拿到 eor 去异或操作求可以快速找到其中一个值了，至于其它的数根本不用管，因为他们本身是偶数次的，所以会把自己异或没了

如下代码：

// 创建一个变量
int eor = 0;
// 遍历这个数组，令它从头异或到尾
for (int cur : arr) {
    eor ^= cur;
}
// ~eor 表示它的每一位取反
// ~eor + 1 就是求补码
// 所以这种 & 补码的操作其实就是快速的找到从右边开始第一个 1 的位置
int rightOne = eor & (~eor + 1);
// 它等价于下面这种求法
// int rightOne = 0;
// while ((eor & rightOne) == 0)
//     rightOne = rightOne << 1; //找到从右边开始第一个1的位置
// 可以打印一下
System.out.println(Integer.toBinaryString(eor));
System.out.println(Integer.toBinaryString(~eor + 1));
System.out.println(Integer.toBinaryString(rightOne));

int e2 = 0;
for (int j : arr) {
    if ((j & rightOne) != 0) {
        e2 ^= j;
    }
}

target1 = e2;
target2 = e2 ^ eor;