1、进制基础
2、二进制运算
2.1、与运算：&
2.1.1、两位全为1，结果才为 1
0&0=0 0&1=0 1&0=0 1&1=1
51&5 = 1 即:
51 => 00000000 00000000 00000000 00110011
5 => 00000000 00000000 00000000 00000101
& ==> 00000000 00000000 00000000 00000001 (1)2.1.2、用法
- 清零：如果想将一个单元清零，即使其全部二进制为 0， 只要与一个各位都为 0 的数值相与，结果为 0；
- 取一个数中指定位置，如：x = 10101110， 取 x 的低四位，用 x & 00001111 = 00001110，即可得到
2.2、或运算：|
2.2.1、只要有一个为 1，结果就为 1
0|0 = 0 1|0 = 1 0|1 = 1 1|1 = 1
51|5 = 55 即:
51 => 00000000 00000000 00000000 00110011
5 => 00000000 00000000 00000000 00000101
| => 00000000 00000000 00000000 001101112.2.2、用法
常用来对一个数据的某些位置 1
如: x = 1010 0000 的低四位置 1， 用 x | 0000 1111 = 1010 11112.3、异或运算：^
2.3.1、两个相应位为"异"(值不同)，则该位结果为 1， 否则为 0
0^0 = 0 1^0 = 1 0^1 = 1 1^1 = 0；
51^5 = 54即:
51 => 00000000 00000000 00000000 00110011
5 => 00000000 00000000 00000000 00000101
^ => 00000000 00000000 00000000 001101102.3.2、用法
- 使特定位翻转，找一个数，对应 x 要翻转的各位，该数的对应位为 1，其余位为 0，此数与 x 对应的位"异或"即可如:x =10101110， 使 x 低四位翻转， 用 x ^ 0000 1111 = 1010 0001
- 与 0 相异或，保留原值如: x ^ 00000000 = 10101110
- 两个变量交换值:
- ①、借助第三个变量来实现: c = a， a = b， b = c；
- ②、利用加减法来实现: a = a + b， b = a - b， a = a-b；
- ③、用异或运算来实现，也是效率最高的: 原理:利用一个数异或本身等于 0 和 异或运算符合交换率 a = a ^ b； b = a ^b； a = a ^ b
2.4、取反运算：~
取反:对一个二进制数按位取反，即将 0 变为 1，1 变为 0
~1 = 0 ~0 = 1 2.5、左移：<<
将一个运算对象的各二进制位全部左移若干位(左边的二进制位丢弃，右边补 0)
2 << 2 = 8；
2 => 00000000 00000000 00000000 00000010
>>2 => 00000000 00000000 00000000 00001000
若左移时舍弃的高位不包含 1，则每左移一位，相当于该数乘以 2；
2 << 2 ==> 2 * 2 * 2(最快计算 2 的三次方)2.6、右移：>>
将一个数的各二进制位全部右移若干位，正数左补 0，负数左补 1；对于正数来说操作数每右移一位，相当于该数除以 2左补 1 或 0 看被移动的数是正数还是负数；
4 >> 2 ==> 1 ( 4 / 2 / 2)；
-14(11110010) >> 2 ==> -4(11111100)2.7、无符号右移：>>>
各个位向右移指定的位数，右移后左边空出的位使用 0 填充，移出右边的位被丢弃掉
-14 >> 2:
-14 => 11111111 11111111 11111111 11110010
>>2 => 00111111 11111111 11111111 11111100(1073741820) ；2.8、二进制四则运算
2.8.1、加法
0+0=0，0+1=1，1+0=1，1+1=10
- 当两个相加的二进制仅一位时，相加的结果为1；
- 如果两个二进制位全是0，相加的结果仍为0；
- 如果两个相加的进制位均为1，则结果为10，要向高位进1，也就是逢2进1规则在运算的过程中，两数要从最低位开始对齐
2.8.2、减法
1-1=0，1-0=1，0-0=0，0-1=-1 - 当两个相减的二进制位中同为0或1时，相减结果为0；
- 如果被减数的二进制位为1，而减数的二进制位为0，则相减的结果仍为1；
- 如果被减数的二进制位为0，而减数的二进制位为1，则需要向高位借1，但此时借1当2；
2.8.3、乘法
00=0，10=0，01=0，11=1 - 只有当两个相乘的二进制位都为1，相乘的结果才为1；
- 当两个相乘的二进制位只要有一位为0，则相乘的结果都为0；
- 1与任何数相乘的结果都是对应的被乘数；而0与任何数相乘结果都为0；
在乘法运算中，乘数的每一位都要与被乘数的每一位分别相乘，而不仅是对应位相乘
2.8.4、除法
当被除数大于除数时，商是“1”；当被除数小于除数时，不够除，商只能是“0”；
3、负数：以其正值的补码形式表示
3.1、原码一个整数按照绝对值大小转换成二进制成为原码
14 => 00000000 00000000 00000000 00001110 (14的原码)3.2、反码
将二进制按位取反，所得的二进制数称为原二进制数的反码
将 14 的每一位按位取反
00000000 00000000 00000000 00001110 => 14 原码
11111111 11111111 11111111 11110001 => 14 反码
两者互为反码3.3、补码：反码加1称为补码
正数的补码和原码相同；负数的补码是通过先把除符号位外其他各位取反，再在末位（最低位）加1得到；
11111111 11111111 11111111 11110001 + 1 =>
11111111 11111111 11111111 111100103.4、案例
-14 << 2
-14 => 11111111 11111111 11111111 11110010
<<2 => 11111111 11111111 11111111 11001000分析:只需要该补码的原码对应的正值，然后取相反数
- 补码减 1，得到反码 11000111
- 补码取反得到 原码，即该负数的正值 00111000
- 计算正值，为 56
- 取相反数
3.5、根据 1+~n = -n 可以快速，计算负数补码
-n = ~n+1 => -n-1 = ~n4、Java 二进制
4.1、Java 基本数据类型
- 整型:byte(8 bit)、short(16 bit)、int(32 bit)、long(64 bit)
- 浮点型： float(32 bit)、double(64 bit)；
- 布尔：true false (1 bit)字符：
- char(unicode字符 16 bit)
4.2、常用的数
0xff ==> 11111111
f ==> 11114.3、大小端
- 小端（little-endian）：低位字节排放在内存的低地址端即该值的起始地址，高位字节排放在内存的高地址端
- 大端（big-endian）：高位字节排放在内存的低地址端即该值的起始地址，低位字节排放在内存的高地址端
例子: 32bit宽的数 0x12345678 - 在 little-endian 模式下在 CPU 内存的存放方式:(假设内存起始地址 0x4000开始存放)
内存地址: 0x4000 0x4001 0x4002 0x4003
存放内容: 0x78 0x56 0x34 0x12在 big-endian 模式下存放如下:
内存地址: 0x4000 0x4001 0x4002 0x4003
存放内容: 0x12 0x34 0x56 0x78- 大端的优势就是易于阅读，小端便于cpu内部数据计算
4.4、数据类型转换为 字节
8143 (00000000 00000000 00011111 11001111) ==> byte[] b = [-49,31,0,0]; - 第一个（低端）字节：8143 >> 0 * 8 & 0xff = 11001111(207)，有符号为 -49
- 第二个（低端）字节：8143 >> 1 * 8 & 0xff = 00011111(31)
- 第三个（低端）字节：8143 >> 2 * 8 & 0xff = 00000000(0)
- 第四个（低端）字节：8143 >> 3 * 8 & 0xff = 00000000(0)
4.5、字符串与字节的相互转换
字符串 --> 字节：byte[] b = s.getBytes();
字节 --> 字符串：byte[] b = new byte[int]; new String(b) 或者 new String(b, encode)// encode 编码格式:
4.6、转换实例
public class CovertToRadix {
public static byte[] intToByte(int i){
byte[] arr = new byte[4];
/*
arr[0] = (byte)((int)((i >> 0 * 8) & 0xff));
arr[1] = (byte)((int)((i >> 1 * 8) & 0xff));
arr[2] = (byte)((int)((i >> 2 * 8) & 0xff));
arr[3] = (byte)((int)((i >> 3 * 8) & 0xff));
*/
for(int j=0;j<arr.length;j++){
arr[j] = (byte)((int)((i >> j * 8) & 0xff));
}
return arr;
}
public static int byteToInt(byte[] arr){
/*
int r0 = (int)((arr[0]& 0xff) << 0 * 8);
int r1 = (int)((arr[1]& 0xff) << 1 * 8);
int r2 = (int)((arr[2]& 0xff) << 2 * 8);
int r3 = (int)((arr[3]& 0xff) << 3 * 8);
*/
int result = 0;
for(int j=0;j<arr.length;j++){
result += (int)((arr[j]& 0xff) << j * 8);
}
return result;
}
}5、如何利用位运算
5.1、子网掩码
5.2、求平均值
int x = 32760; int y = 32762; 求 x，y 的平均值，要求空间复杂度 O(0)
public static int ave(int x， int y){
return (x&y) + ((x^y)>>1)；
}- 知识点: >>n 相当于除于2^n ，<<n 相当于乘于 2^n
- 把 x，y分别分成两个部分来看，两者相同的位分别拿出来:
x(111111111111000) = 111111111111000 + 000000000000000
y(111111111111010) = 111111111111000 + 000000000000010
相同部分我们叫做x1，y1，不同部分我们叫做x2，y2.那么现在(x+y)/2 =(x1+y1)/2 +(x2 + y2)/2 ，<br>
因为x1 == y1 ，所以(x1+y1)/2 == x1 ==y1，<br>
相同部分我们用与运算求出来 x1 = x & y ，不同部分的和我们用^ 求出来，然后除于 2(>>1)是不是我们想要的结果了呢<br>5.3、判断奇偶数
- a&1 = 0 偶数
- a&1 = 1 奇数
5.4、取 int 型变量 a 的第 k 位 (k=0，1，2…)
即 a>>k&1 (先右移k再与1)
5.5、幂问题 - 判断是否为 2 的幂：((x&(x-1))==0) && (x!=0);
- 如何判断一个无符号数是2的n次方-1:
private static boolean isPowerOfTwoLoseOne(int val) {
return (val & (val+1)) == 0；
}- 非2的幂次方转换为2的幂次方
- 求一个数离它最近的大于等于2的幂次方的数:
MAXIMUM_CAPACITY = Integer.MAX_VALUE；
private static final int tableSizeFor(int c) {
int n = c - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}- 如果求小于等于2的幂次方的数:
private static final int tableSizeFor(int n) {
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return n-(n>>1);
}- 使用位运算(&)来实现取模运算(%)：
X % 2^n = X & (2^n - 1)
2^n表示2的n次方，也就是说，一个数对2^n取模 == 一个数和(2^n - 1)做按位与运算 。
假设n为3，则2^3 = 8，表示成2进制就是1000。2^3 -1 = 7 ，即0111。
此时X & (2^3 - 1) 就相当于取X的2进制的最后三位数。
从2进制角度来看，X / 8相当于 X >> 3，即把X右移3位，此时得到了X / 8的商，而被移掉的部分(后三位)，则是X % 8，也就是余数5.6、计算绝对值
public static int abs(int x){
int y = x >> 31;
return (x^y) - y;
}- 取模运算转化成位运算 (在不产生溢出的情况下)：a % (2^n) 等价于 a & (2^n - 1)
- 乘法运算转化成位运算 (在不产生溢出的情况下)：a * (2^n) 等价于 a<< n
- 除法运算转化成位运算 (在不产生溢出的情况下)：a / (2^n) 等价于 a>> n，例: 12/8 == 12>>3
- a % 2 等价于 a & 1
if (x == a) x= b;
else x= a;
等价于 x= a ^ b ^ x;