[TOC]
基础概念
位
- 也称比特，记为bit(binary digit的缩写)或小写b
- 这是最小的信息单位，是用0或1来表示的1个二进制数位
字节
- 记为Byte或大写B，这是计算机的最小存储单元
- PC机中由8个二进制位构成一个字节，从最小的00000000到最大的11111111，即一个字节可有256个值。
- 一个字节也可以表示由8个二进制位构成的其它信息。
- 一个字节可存放一个半角英文字符的编码( ASCII码)。
- 两个字节可存放一个汉字编码。1个汉字至少需要两个字节或两个字符来表示。这里所说的字符是指ASCII码字符，即半角下的英文字母、数字或其它符号。
字
- 记为word或小写w，是计算机信息交换、加工、存储的基本单元。
- 用二进制代码表示，一个字由一个字节或若干字节构成(不同机器的字长不同)。
- 它可以代表数据代码、字符代码、 操作码和地址码或它们的组合。计算机的“字”用来表示数据或信息长度。
单位转换
K (KiloBytes，千) 字节 1KB = 1024 byte =2^10 byte
M（MegaBytes，兆）字节 1MB = 1024 K =2^20 byte
G（GigaBytes，吉）字节 1GB = 1024 M =2^30 byte
T（TeraBytes，太）字节 1TB = 1024 G =2^40 byte
P（PetaBytes，拍）字节 1PB = 1024 T =2^50 byte
数字的表示
计算机数字有原码、反码、补码三种存储格式，通常都是补码。
- 正数的补码和原码相同
- 正数的原码、反码、补码都相同
- 负数的补码
- 符号位为1
- 其余各位是对原码取反
- 然后整个数加1
比如:
+7的补码: 0000 0111
-7的补码
1(000 0111) //符号位为1
1111 1000 //对原码取反
1111 1001 //加1
注意，以下所示的
基本规则中的0和1表示的都是二进制位。
与(&)
基本规则
同时为1得1,否则为0
0 & 0 == 0
0 & 1 == 0
1 & 0 == 0
1 & 1 == 1
常用技巧
- 用0 "遮盖" 掉不需要的位
- x & 0 == 0
或(|)
基本规则
同时为零得0,否则为1
0 | 0 == 0
0 | 1 == 1
1 | 0 == 1
1 | 1 == 1
非(~)
基本规则
按位取反，0变1,1变0
异或(^)
基本规则
相同得0,不同得1
0 ^ 0 == 0
0 ^ 1 == 1
1 ^ 0 == 1
1 ^ 1 == 0
常用技巧
- 开关位
1 ^ 1 == 0
1 ^ 1 ^ 1 == 1
1 ^ 1 ^ 1 ^ 1 == 0
1 ^ 1 ^ 1 ^ 1 ^ 1 == 1
1 ^ 1 ^ 1 ^ 1 ^ 1 ^ 1 == 0
x ^ y ^ y == x
-
x ^ x == 0
- x可以是任意整数
- 所以可用来比较两个数否是相等
移位
左移
基本规则
- 左移后空出来的低位补零
- 最高位由于挪动可能导致0/1更替使得数字符号位发生改变
- 左移一位相当于乘2
例子
6 << 2 == 24
00000000 00000000 00000000 00000110 (6)
00000000 00000000 00000000 00011000 (6 << 2)
常用技巧
对于正数和负数,在数字没有溢出的前提下:
- m<<1:左移1位相当于m乘以2的1次方,即乘以2.
- m<<n:左移n位相当于m乘以2的n次方.
右移
基本规则
- 右移后的高位
- 正数补0
- 负数补1
- 移动的时候考虑符号位,所以又称带符号右移
- 正数右移一位相当于除以2
例子
6 >> 2 == 1
00000000 00000000 00000000 00000110 (6)
00000000 00000000 00000000 00000001 (6 >> 2)
-3 >> 1 == -2
11111111 11111111 11111111 11111101 (-3-----补码)
11111111 11111111 11111111 11111110 (-2-----补码)
常用技巧
m >> n:即相当于m除以2的n次方
- 得到的为整数时,即为结果
- 得到的为小数时
- 如果m为正数,得到的商会舍弃小数位
- 如果m为负数,舍弃小数部分，然后把整数部分加+1得到位移后的值
无符号右移
和右移的区别是:无论正负数，都在高位补0
例子:
-3 >>> 1 ==2147483646
11111111 11111111 11111111 11111101(-3-----补码)
01111111 11111111 11111111 11111110(右移1位高位补0而不是1)
应用
正负数切换
由原码反码补码的知识很容易得到如下结论:
~x + 1 == -x
求绝对值
- 正数===>符号位为0===>zishen
- 负数===>符号位为1===>相反数
问题就在如何获取符号位了：
x >> (size-1) ==========> 最左边的符号位,size为数字总的位长度,java的int为32个bit
public int abs(int x) {
return x >> (Integer.SIZE - 1) == 0 ? x : ~x + 1;
}
判断奇偶数
通常我们判断一个数是奇数还是偶数都是用取模运算,但是这个效率有点底下了。
本人在一次面试的时候就遇到面试题让我写出最快的判断奇数偶数的方法。
计算机里最快的无非是位运算了。
(x & 1) == 1 则x是奇数
(x & 1) == 0 则x是偶数
原理:
奇数偶数的奇偶,关键就看最后一位了.
所以考虑只保留最后一位,其余的位都和0相与而“遮盖”掉.
例如:
00011010 (26)
00000001 (1)
-------------
00000000 (0)===>偶数
00011001 (25)
00000001 (1)
------------
00000001 (1)===>奇数
大小写转换
对于同一个字母而言，其对应的ASCII码的差值的绝对值刚好是32。
所以,我们常规的转换也就是对其对应的ASCII码加上或者减去32,即可得到其对应的大写或者小写字母了。
恰好这个差值32是2^5==0b100000==0x20,或许当初ASCII定制的时候就考虑到这点了吧。
// 这里的c和C代表a-zA-Z中的任意一个字符。
c ^ 0x20 == C
C ^ 0x20 == c
例如:
'a'====>97====>01100001
'A'====>65====>01000001
32====>00100000
就差倒数第六位的1====>0b100000===>0x20。
原理
大小和小写字母的ASCII码之间就差倒数第六位的1或0
所以转换大小写只需考虑将倒数第六位取反即可。其余位不变。
所以可以用异或的特性来做开关位切换倒数第六位的0或者1。
交换两个数
平常我们的做法就是找第三个数作为临时的交换空间，有一次遇到了有人用这个方式交换的。
int a = 9;
int b = 10;
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println(a); //10
System.out.println(b); //9
十进制整数转为二进制字符串
尽量不适用任何内置库函数和内置类，只使用最基本的操作完成整数到二进制字符串的转换。
// i>=0 && i<Integer.SIZE
// 1. 倒数第i位后跟i个0
//比如i为3时可能为1000(倒数第三位为1)或0000(倒数第三位为0)
x & (1<<i)
// 2.倒数第i位
(x & (1<<i)) >> i
public String toBinaryString(int x) {
char bts[] = new char[Integer.SIZE];
//或者可以将循环倒过来处理
for (int i = 0; i < Integer.SIZE; i++) {
bts[Integer.SIZE - 1 - i] = (x & (1 << i)) >> i == 0 ? '0' : '1';
}
return new String(bts);
}
