前言
经常会在代码中看到用二进制实现一些标志位的运算,简单总结一下二进制的一些概念。了解 使用二进制的原因。
二进制
比特和字节
先了解一下比特。
计算机中最小的存储单位是二进制位(binary digit),也叫比特, bit 只能够存储 0 或 1。由 8 bit 串联组成的称为字节(byte)。
也就是常说的 1 byte = 8 bit
。
1 个字节可以代表 256 种不同的可能(28)
10101010 | 11111111 |
二进制与十进制的互相转换。
关于二进制和十进制互相转换的方法,这个 如何快速学会二进制? 知乎回答解释的很清楚了。这里贴一下原图。
十进制转换为二进制,记得最后的余数要倒序排列,才是结果,比如上图中 23 = 10111
至于二进制到十进制的转换相对来说说就比较简单了。我们知道十进制中
-
123 的含义是 1×100 + 2×10 +3×1 = 123.
-
1024 的含义是 1×1000 + 0x100 +2×10 + 4×1 = 1024 这中间的 1000,100,10,1 就是每一位的权重。对于二进制也有类似的概念
-
111 = 4×1 + 2×1 + 1×1 = 7
-
1010 = 8×1 + 4×0 + 2×1 + 1×0 = 10
幂 | 二进制 | 十进制 |
---|---|---|
~ | 00000000 | 0 |
0 | 00000001 | 1 |
1 | 00000010 | 2 |
2 | 00000100 | 4 |
3 | 00001000 | 8 |
4 | 00010000 | 16 |
5 | 00100000 | 32 |
6 | 01000000 | 64 |
7 | 10000000 | 128 |
从表中我们也可以看到 1byte 8位二进制数可以表达 0~255 的值,也就是说 8 位二进制代表着 256 种可能性。
二进制正负数的表示
上面我们说,8 位二进制可以代表 256 种可能性,这是在非负整数的情况下,正常情况下还有负数。
在计算机 0 和 1 的世界中,没有 ‘-‘ 号,意味着它没法直接表示一个负数,我们如果想表示一个负数,只能在程序中去体现:比如声明成有符号的数据类型signed int(一般简写为int),这个类型既可以表示负整数也可以表示正整数。这就意味着:在内存中有一段二进制数据,你可以把它当成正整数也可以负数,甚至浮点数。
为了更好的表示正数和负数,计算机规定:有符号数据的最高位是1则表示负数,为0则表示正数。而具体可以分为原码,反码,补码三种表示法
- 原码表示法
最高位为1表示负数,剩余数据的表示与正整数相同。比如01010表示正数10,11010表示负整数-10。这种表示方法最符合我们正常人的思维方式。
- 反码表示法
最高位为1表示负数,剩余的数据按照正整数的值按位取反,即:最高位1,然后对剩下的1010按位取反,得到0101,然后组合起来:10101。
以上两种表达方式式有点瑕疵:0的表示都有两种,原码表示法中10000(负)和00000(正)都表示0,反码表示法中,11111(负)和000000(正)都表示0(这里先假设数据只有5bit,如果是类型则是32个1),这样会浪费一个字节,而且也不利于计算。(注意无论是什么表示,正数的表达都是一样的)
- 补码表示法
最高位表示负数,剩余数据按照正整数的值按位取反,再加1,这同时也是反码转补码的方法。
二进制数 | 原码 | 反码 | 补码 | 十进制数 |
---|---|---|---|---|
1000 0000 | 1000 0000 | 1111 1111 | 0000 0000 | 0/-0 |
0000 0001 | 0000 0001 | 0000 0001 | 0000 0001 | 1 |
1000 0001 | 1000 0001 | 1111 1110 | 1111 1111 | -1 |
1111 1111 | 1111 1111 | 1000 0000 | 1000 0001 | -127 |
0111 1111 | 0111 0111 | 0111 1111 | 0111 1111 | 127 |
-128 的补码是 1000 0000 . 当然,八位二进制数,能表达的最大整数是 127,因此,这是一条特例。至于具体的细节可以参考原码、反码、补码的产生、应用以及优缺点有哪些?
一条运算规律:对非负数的二进制进行取反、然后+1,便可得其负数的二进制表示
所以 8 位二进制用来表示有符号的数,可以表达的的范围是 -128~~127,也就是 -(2)7~27 -1
所以补码表示法中,所有能表示负数的个数要比正整数多一个,因为正整数中有一个0000 0000被当做0了呀。
我们知道在 Java 中,int 类型的数据有 4 个字节保存,也就是 32 位。 因此,范围就是 -(2)31~231 -1 的值。
看完了二进制的表示与转换,我们再看看看二进制的运算,这里主要说逻辑运算。
二进制的运算
二进制只有 0 和 1 表示 false 与 true。 对应的逻辑运算
- 与 运算符为 &
input | input | out |
---|---|---|
0 | 0 | 0 |
1 | 0 | 0 |
0 | 1 | 0 |
1 | 1 | 1 |
- 或 运算符为 |
input | input | out |
---|---|---|
0 | 0 | 0 |
1 | 0 | 1 |
0 | 1 | 1 |
1 | 1 | 1 |
- 非 运算符为 ~
input | out |
---|---|
1 | 0 |
0 | 1 |
- 异或 运算符为 ^
input | input | out |
---|---|---|
0 | 0 | 0 |
1 | 0 | 1 |
0 | 1 | 1 |
1 | 1 | 0 |
关于异或运算,我们可以总结出规律
1. 0 与 A (任意值)异或的结果为 A
2. 任何数与自己异或的结果为 0
用二进制位表示 boolean 值
在java中,一个字节,也就是 8 位,而布尔值在 Java 中至少占用一个字节(关于布尔值具体占几个字节,不在此处讨论),如果用户有 7 个属性,如是否为汉族、是否为男性等,如果全用布尔值来表示,就是 7 个字节。也可以用一个字节来表示,用 1 和 0 代表是和否。用1个字节替代 7 个字节来表示信息,空间节省 80% 以上。
8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
---|---|---|---|---|---|---|---|
1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
用二进制位表示 boolean 标志位,我们需要关心三件事,即读取某一位的值,在某一位如何正确的写入 0 或 1 。
读值
怎么读取某个位是 0 还是 1 ?
以第三位为例,即4的二进制00000100,利用与运算,可以知道某个位是否被 enable 了。
00001001//9的二进制
& 00000100//4的二进制
= 00000000//0的二进制
即 00001001 & 00000100 != 00000100 可判定,第三位 enable = false
00001101//13的二进制
& 00000100//4的二进制
= 00000100//4的二进制
即 00001101 & 00000100 == 00000100 可判定,第三位 enable = true
写 1
怎么在不影响其他位的情况下,把某个位设为1?
这里会利用到或运算,我们还是以第三位为例子
//当第三位没有 enable 时
00001001//9的二进制
| 00000100//4的二进制
= 00001101//13的二进制
//当第三位 enable 时,设置前后,值应该是不变的
00001101//13的二进制
| 00000100//4的二进制
= 00001101//13的二进制
写 0
怎么在不影响其他位的情况下,把某个位设为0?
这里会利用与、取反运算,我们仍以第三位为例子: 4的二进制 00000100 取反得到 11111011
//当第三位没有被置起时
00001101//13的二进制
& 11111011//4的二进制取反
= 00001001
通用实现
以上二进制位的读写可总结为实现
public class BitUtils {
public static void main(String[] args) {
int flag = 127;
System.out.println(check(flag,1));
flag = setBit(flag, 1, false);
System.out.println(check(flag, 1));
flag = setBit(flag, 8, true);
System.out.println(check(flag,8));
flag = setBit(flag, 5, false);
System.out.println(check(flag,5));
}
public static boolean check(int flag, int bit) {
System.out.println("BitUtils: flag: " + Integer.toBinaryString(flag) + ", bit is " + bit);
return (flag & bit) == bit;
}
public static int setBit(int flag, int bit, boolean value) {
int result;
if (value) {
result = flag | bit;
} else {
result = flag & (~bit);
}
System.out.println("BitUtils: flag: " + Integer.toBinaryString(result));
return result;
}
}
BitUtils: flag: 1111111, bit is 1
true
BitUtils: flag: 1111110
BitUtils: flag: 1111110, bit is 1
false
BitUtils: flag: 1111110
BitUtils: flag: 1111110, bit is 8
true
BitUtils: flag: 1111010
BitUtils: flag: 1111010, bit is 5
false
可以看到结果和预期是完全符合的。
在 Android 中的使用
在 Android 中关于二进制位的使用,最熟悉的莫过于令人头疼的 MeasureSpec 了(关于 MeasureSpec 和 View 相关的内容不再此展开,此处只讨论其二进制位的使用)
MeasureSpec
public static class MeasureSpec {
private static final int MODE_SHIFT = 30;
private static final int MODE_MASK = 0x3 << MODE_SHIFT;
public static final int UNSPECIFIED = 0 << MODE_SHIFT;
public static final int EXACTLY = 1 << MODE_SHIFT;
public static final int AT_MOST = 2 << MODE_SHIFT;
public static int makeMeasureSpec(@IntRange(from = 0, to = (1 << MeasureSpec.MODE_SHIFT) - 1) int size,
@MeasureSpecMode int mode) {
if (sUseBrokenMakeMeasureSpec) {
return size + mode;
} else {
return (size & ~MODE_MASK) | (mode & MODE_MASK);
}
}
@MeasureSpecMode
public static int getMode(int measureSpec) {
//noinspection ResourceType
return (measureSpec & MODE_MASK);
}
public static int getSize(int measureSpec) {
return (measureSpec & ~MODE_MASK);
}
}
首先是 MODE_MASK, 它对 11 进行了左移 30 位的操作
Integer.toBinaryString(MODE_MASK) == "11000000000000000000000000000000"
即 32 位 int 的高两位为 1,其余均为 0。
那么其 getMode 和 getSize 的实现就很好理解了,就是利用与运算和非运算对相应的位进行屏蔽。
makeMeasureSpec 的实现也很好理解了, MODE_MASK 分别取最高为的值和剩余位的值,然后通过或运算再合起来。
一些细节
- Mode 的具体值
UNSPECIFIED = 0
EXACTLY = 1073741824
AT_MOST = -2147483648
- size 的范围
32 位高两位表示 mode ,那么剩下的 30 位用来表示 size,也就是说实际上 size = (0~230) 这么大的范围。但是在 makeMeasureSpec 方法中用 “`@IntRange“ 对 size 进行了限制, size 的最大值为
(1 << MODE_SHIFT) - 1 ---> 1073741823
Math.pow(2,30) ---> 1073741824
可以看到实际最大值比预期的最大值少了 1。
总结
在 Android 源码中使用,使用二进制位进行位运算节省内存的场景还要很多,比如 View 的 mPrivateFlags 等各类标示是否需要进行绘制、测量操作的位。
围绕二进制可以有很多话题可以展开讨论,比如二进制和物理内存的关系,和缓存的关系等,更多可以参考这篇二进制。