位运算基础知识
一：参考
[算法心得] http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogIEEE64Float
[运算符优先级] https://tool.oschina.net/commons?type=6
[位运算技巧] https://www.zhihu.com/question/38206659
[思考题解法] https://www.iteye.com/blog/yacare-1969931
二：概要
通过本文可以让我们温习下位运算、进制转换，为写出更精良的代码奠定理论基础。现在我们从一个题目说开去：
问：如何载预计有10亿个int的数据中，剔除其中重复的数据并排序输出?
分析：首先要进行排序、排重必须得把相关数据加载到内存中，那么要用哪种数据结构来存储呢?
10 0000 0000 = 10^9
int[10^9] 需要内存 10^9 * 4(B) => ((10^9 * 4)/1000 * 1000)(M) => 4000M => 4GB
对于普通32位最大理论内存为4G的PC来说，这个计算资源是无法实现需求的，那么有没有更好的解决方法呢？在此之前先做些知识点温故。
三：知识点回顾
1.java基本类型
| Data Type | Default Value | Default size | range | range value |
|---|---|---|---|---|
| boolean | false | 1 bit | ||
| char | ‘\u0000’ | 2 byte | ‘\u0000’~’\uFFFF’ | |
| byte | 0 | 1 byte | -2^7~2^7-1 | -128~127 |
| short | 0 | 2 byte | -2^15~2^15-1 | -32768~32767 |
| int | 0 | 4 byte | -2^31~2^31-1 | 0x80000000~0x7fffffff |
| long | 0L | 8 byte | -2^63~2^63-1 | |
| float | 0.0f | 4 byte | ||
| double | 0.0d | 8 byte |
2.进制
**二进制：**由0，1组成，运算规律是逢二进一，计算机只能识别二进制表示的数据；
**八进制：**由0、1、2、3、4、5、6、7组成，运算规律是逢八进一；用前导0区别，例如 012；
**十进制：**由0，1，2、3、4、5、6、7、8、9组成，运算规律是逢十进一；例如 12；
**十六进制：**由数字0～9以及字母A (10)，B (11)，C (12)，D (13)，E (14)，F (15)组成,大小写均可，运算规律是逢十六进一；例如 0XC；
2.1 十进制转二进制
除2取余倒排，每发生一次除必须要有一个余数，必须除倒商是0的时候，最后把所得的余数倒排。
2.2 二进制转十进制
按位乘权相加
2.3 十进制转八进制
10进制数转换成8进制的方法，和转换为2进制的方法类似，唯一变化：将图1中的基数由2变成8，然后依次计算。
2.4 八进制转十进制
可参考图2中二进制的计算过程: 进制数第1位的权值为8的0次方，第2位权值为8的1次方，第3位权值为8的2次方，依次计算，公式：第N位 * 8的N-1次方，结果再相加便是最后结果。
2.5 十进制转十六进制:
10进制数转换成16进制的方法，和转换为2进制的方法类似，唯一变化：将图1中的基数由2变成16，然后依次计算。
2.6 十六进制转十进制:
第0位的权值为16的0次方，第1位的权值为16的1次方，第2位的权值为16的2次方，依次计算，公式：第N位 * 16的N-1次方，结果再相加便是最后结果。
2.7 二进制与八进制的转换
1）二进制转八进制，3位二进制位压缩为1位，
2）八进制转二进制，1位展开为3位
3）可先转换为十进制在转换为二进制或者八进制
2.8 二进制与十六进制的转换
1）二进制转十六进制，4位二进制位压缩为1位，
2）十六进制转二进制，1位展开为4位
3）可先转换为十进制在转换为二进制或者十六进制
2.9 八进制与十六进制的转换
可先转换为十进制在转换为十六进制或者八进制
3.进制存储单位
在计算机的二进制数系统中，位简记为bit，也称为比特，是数据存储的最小单位，每个二进制数字0或1就是一个位(bit)，也就是一比特；也可以把二进制中的0和1看做开关中的“开”和“关”，1表示“开”，0表示“关”。
8 bit（位）= 1B，也就是一个字节（Byte），然而1KB却不等于1000B，下面是详细的计算规则：
1B（byte，字节）= 8 bit；
1KB（Kilobyte，千字节）= 1024B = 2^10 B；
1MB（Megabyte，兆字节，百万字节，简称“兆”）= 1024KB = 2^20 B；
1GB（Gigabyte，吉字节，十亿字节，又称“千兆”）= 1024MB = 2^30 B；
1TB（Terabyte，万亿字节，太字节）= 1024GB = 2^40 B；
1PB（Petabyte，千万亿字节，拍字节）= 1024TB = 2^50 B；
4.原码、反码和补码
在计算机内，有符号数（这里的符号指的是正负符号，有符号数指的就是正负数）有3种表示法：原码、反码和补码，所有数据的运算都是采用补码进行的：
1). 正数的原码，反码，补码都相同；
2). 负数的有些不同，详情如下：
**原码：**根据二进制定点表示法，二进制最高位为符号位，“0”表示正，“1”表示负，其余位表示数值的大小。
**反码：**负数的反码是对其原码逐位取反（0变1，1变0），但符号位除外。
**补码：**负数的补码是在其反码的末位加1（逢二进一）。
需要注意的是：求反码的时候，最高位（符号位）是不能被改变的， 正数的符号位是0，负数的符号位是1。
例子：分别求出5和-5的原码、反码和补码
5.位运算
位运算只能整型或者字符型，计算时将非二进制转成二进制后在进行按位运算，按位运算不产生进位、借位，最后在还原成十进制。
5.1 运算符
5.1.1 位运算符
| 运算符 | 描述 | 运算规则 |
|---|---|---|
| & | 按位与 | 两个位都为1时，结果才为11&1=1 1&0=0 0&1=0 0&0=0 |
| | | 按位或 | 两个位都为0时，结果才为01|1=1 1|0=1 0|1=1 0|0=0 |
| ^ | 按位异或 | 两个位相同为0，相异为11^1=0 1^0=1 0^1=1 0^0=0 |
| ~ | 按位取反 | 0变1，1变0,属于单目运算符 |
| « | 左移 | 各二进位全部左移若干位，高位丢弃，低位补0 |
| » | 右移 | 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移） |
| »> | 无符号右移 | 不考虑符号位右移 如：-2 »> 1 => 0101 |
5.1.2 复合赋值运算符
&= 例：a&=b 相当于 a=a&b
|= 例：a|=b 相当于 a=a|b
>>= 例：a>>=b 相当于 a=a>>b
<<= 例：a<<=b 相当于 a=a<<b
^= 例：a^=b 相当于 a=a^b
+= 例：a+=b 相当于 a=a+b
-= 例：a-=b 相当于 a=a-b
*= 例：a*=b 相当于 a=a*b
/= 例：a/=b 相当于 a=a/b
%= 例：a%=b 相当于 a=a%b
5.1.3 逻辑运算符
逻辑运算符有短路现象，&& 如果第一个数为0则会短路第2个结果为0，||如果第一个数非0短路第2个结果为1
| 运算符 | 含义 | 效 果 |
|---|---|---|
| && | 与 | 将两个表达式连接成一个。两个表达式必须都为 true，整个表达式才为 true |
| || | 或 | 将两个表达式连接成一个。必须有一个或两个表达式为 true，才能使整个表达式为 true。只要其中有一个为 true，那么另外一个就变得无关紧要 |
| ！ | 非 | 反转一个表达式的“真相”。它使一个表达式从 true 变成了 false，或者从 false 变成了 true |
5.2 按位运算
计算机中的数在内存中都是以二进制形式进行存储的，用位运算就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。
5.2.1 & 按位与运算
1 0 0 1 1
& 1 1 0 0 1
------------------------------
1 0 0 0 1
全1为1，有0为0，也叫按位乘
主要作用：
1）清零
如果想将一个单元清零，即使其全部二进制位为0，只要与一个各位都为零的数值相与，结果为零。
2）取一个数的指定位
比如取数 X=1010 1110 的低4位，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行按位与运算（X&Y=0000 1110）即可得到X的指定位。
3）判断奇偶
只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a是不是偶数。
5.2.2 | 按位或运算
1 0 0 1 1
| 1 1 0 0 1
------------------------------
1 1 0 1 1
有1为1，全0为0，也叫按位加。注意：负数按补码形式参加按位或运算。
主要作用：置1操作
5.2.3 ^ 按位异或运算
1 0 0 1 1
^ 1 1 0 0 1
-----------------------------
0 1 0 1 0
相异为1，相同为0
异或的几条性质:
- 1、交换律
- 2、结合律 (a^b)^c == a^(b^c)
- 3、对于任何数x，都有 x^x=0，x^0=x
- 4、自反性: a^b^b=a^0=a;
异或运算的用途：
1）翻转指定位
比如将数 X=1010 1110 的低4位进行翻转，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行异或运算（X^Y=1010 0001）即可得到。
2）与0相异或值不变
例如：1010 1110 ^ 0000 0000 = 1010 1110
3）交换两个数
void Swap(int &a, int &b){
if (a != b){
a ^= b;
b ^= a;
a ^= b;
}
}
5.2.4 ~ 按位取反运算
~ 1 0 0 1 1
-----------------------------
0 1 1 0 0
对于一个数按位取反得到的值为该数+1后在乘以-1
**技巧：(该数+1) * (-1) **
异或运算的用途：
1）使一个数的最低位为零
使a的最低位为0，可以表示为：a & ~1。~1的值为 1111 1111 1111 1110，再按"与"运算，最低位一定为0。因为" ~“运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。
5.2.5 « 按位左移运算
int a = 8;
a << 3;
移位前：0000 0000 0000 0000 0000 0000 0000 1000
移位后：0000 0000 0000 0000 0000 0000 0100 0000
主要作用：将二进制位按位依序左移n位
对于一个十进制数左移n位后得到的值为该数乘以2^n的积。
5.2.6 » 按位右移运算
向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位，如
unsigned int a = 8;
a >> 3;
移位前：0000 0000 0000 0000 0000 0000 0000 1000
移位后：0000 0000 0000 0000 0000 0000 0000 0001
int a = -8;
a >> 3;
移位前：1111 1111 1111 1111 1111 1111 1111 1000
移位前：1111 1111 1111 1111 1111 1111 1111 1111
主要作用：将二进制位按位依序右移n位
对于一个十进制数，若该数为负数 并且 不能被2^n整除，则得到的数为商加-1。
正数||(负数 && 能被2^n整除)则结果为=> 数/2^n (负数 && 不能被2^n整除)则结果为=>数/2^n+(-1)
5.3 位运算技巧
1、
a & a = a
a | a = a
a ^ a = 0
2、
a & 0 = 0
a | 0 = a
a ^ 0 = a
3、
a | ( a & b ) = a
a & ( a | b ) = a
4、交换值
a ^= b;
b ^= a;
a ^= b;
5、判断奇偶(取出最后一位)
a & 1 等价于 a % 2(结果等于,位运算效率高)
6、比较两值是否相等
a ^ b ==0
7、i+1位 置1
a |=1<<i
8、i+1位 置0
a &=~(1<<i)
9、取出i+1位(联系第5点)
a & (1<<i)
10、在对应i+1位，插入b的对应位；
a |=1<<i; （a的bit位置1）
a & (b & 1<<i) （与b的bit位相与）
11、删除最后的1；
a & (a-1)
12、负数
-a = ~a+1
13、仅保留最后一个1;
a&(-a)
14、得到全1
~0
15、保留最后i-1位；
a & ((1<<i)-1)
16、清零最后i-1位；
a & ~((1<<i)-1)
17、判断最高位是否为1
a<0
18、得到最高位的1；
a = a |(a>>1);
a = a |(a>>2);
a = a |(a>>4);
a = a |(a>>8);
a = a |(a>>16);
return (a+1)>>1;
四：问题解答
对于概要的问题，有没有更好的方式来解决呢，答案是肯定的。
计算机中最小的存储单位是bit，它的值只有两个0或1，假如刚好有10亿个int的数据，那么我们是否可以构造出10个bit,然后以我们想象中的方式从左到右平铺开来，然后把这10亿个int的数据从小到大一一对应到这些bit中，如果数值存在则标记为1，那么所需空间为10^9位，换算成10^9/8/1000/1000 约为125M，
由于两位bit可以表示4位数即2^2，那么对于4个byte能表示的数据量为2^32个(bit)，2^32 bit =2^32 / 2^3(byte) = 2^29 byte= 512M；int数据范围为【-2^31,2^31-1】即[-21,4748,3648 ~ 21,4748,3648-1]
那么把10亿个数据平铺开的效果如下：
那么可以得出
1.long bitIndex = 任意int数 + (1l « 31); 得出数字在理论bit数组中的位置
2.int byteIndex = bitIndex / 8; 得出数字在真实byte[]数组的位置
3.int innerByteIndex = bitIndex % 8; 得出数字在真实byte[byteIndex]中8个位置中的哪个位置
4.byteData[index] = (byte) (byteData[byteIndex ] | (1 < innerByteIndex)); 将定位到的innerByteIndex位置如果为0设置为1
那么可以得出
1.int bitIndex = 任意int数; 得出数字在理论bit数组中的位置
2.int byteIndex = bitIndex / 8; 得出数字在真实byte[]数组的位置
3.int innerByteIndex = bitIndex % 8; 得出数字在真实byte[byteIndex]中8个位置中的哪个位置
4.byteData[index] = (byte) (byteData[byteIndex ] | (1 < innerByteIndex)); 将定位到的innerByteIndex位置如果为0设置为1
以下为有符号int的场景测试代码
import java.util.Random;
public class BigDataSort {
//数据容量
private final int CAPACITY = 1 000 000 000;
// 定义一个byte数组缓存所有的数据
private byte[] byteData = new byte[1 << 29];
public static void main(String[] args) {
BigDataSort ms = new BigDataSort();
Random random = new Random();
for (int i = 0; i < CAPACITY; i++) {
int num = random.nextInt();
System.out.println("读取了第 " + (i + 1) + "\t个数: " + num);
ms.setNumBit(num);
}
ms.output();
}
/**
* 读取数据，并将对应数数据的 到对应的bit中，并返回byte数组
* @param num 读取的数据
*/
private void setNumBit(int num) {
//获取num数据对应bit数组（虚拟）的索引
long bitIndex = num + (1l << 31);
//bit数组（虚拟）在byte数组中的索引
int index = (int) (bitIndex / 8);
//bitIndex 在byte[]数组索引index 中的具体位置
int innerIndex = (int) (bitIndex % 8);
System.out.println("byte[" + index + "] 中的索引：" + innerIndex);
byteData[index] = (byte) (byteData[index] | (1 << innerIndex));
return;
}
/**
* 输出数组中的数据
*/
private void output() {
int count = 0;
for (int i = 0; i < byteData.length; i++) {
for (int j = 0; j < 8; j++) {
//判断是否对应的bit位为1则输出原始数据
if (!(((byteData[i]) & (1 << j)) == 0)) {
count++;
int number = (int) ((((long) i * 8 + j) - (1l << 31)));
System.out.println("取出的第 " + count + "\t个数: " + number);
}
}
}
}
}
五：java无符号处理
有符号数（signed）可以表示特定类型规定范围内的整数（包括负数），而无符号数只能表示非负数（0及正数）
java unsigned表示
// java 中没有 unsigned，所以为了实现 unsigned，需要使用比原本类型更大的类型，通过位运算获取其 unsigned 的值
// unsigned byte & short -> int，unsigned int -> long
private static int getUnsignedByte(byte b) {
return b & 0x0FF;
}
private static int getUnsignedShort(short data) {
return data & 0x0FFFF;
}
private static long getUnsignedInt(int data) {
// data & 0xFFFFFFFF 和 data & 0xFFFFFFFFL 结果是不同的，需要注意，有可能与 JDK 版本有关
return data & 0xFFFFFFFFL;
}
short、int 和 long 转 bytes
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
ByteOrder order = ByteOrder.LITTLE_ENDIAN;
// long
long l = 2147483648L;
byte[] bytes = ByteBuffer.allocate(8).order(order).putLong(l).array();
long data = ByteBuffer.wrap(bytes, 0, bytes.length).order(order).getLong();
// int
int i = 123456;
byte[] bytes = ByteBuffer.allocate(4).order(order).putInt(i).array();
int data = ByteBuffer.wrap(bytes, 0, bytes.length).order(order).getInt();
// short
short s = 32767;
byte[] bytes = ByteBuffer.allocate(2).order(order).putShort(s).array();
int data = ByteBuffer.wrap(bytes, 0, bytes.length).order(order).getShort();
String转Byte
import java.nio.charset.Charset;
Charset charset = Charset.forName("UTF-8");
String data = "abc";
byte[] bytes = data.getBytes(charset);
String newData = new String(bytes, 0, bytes.length, charset);