Java拾遗：014 - 二进制、进制转换及位运算

二进制

二进制是计算机中广泛采用的一种数制，由0和1组成，进位规则为“逢二进一”，如：0001表示十进制中的1，0010表示十进制中的2。二进制拥有大量非学有用的特性，详情参考：百度百科：二进制数。

在有符号整数中，最高位表示符号位，0表示正数、1表示负数。

在Java中整型（int）由4个字节（32位）表示，所以一个整型数字（以1024为例）用二进制表示为：

# 下面是一个32位的二进制数，等价于十进制的1024
00000000 00000000 00000100 00000000
# 其换算过程为（0乘以任何数都为0），这里^表示次幂（非按位异或）
0 * 2 ^ 0 + 0 * 2 ^ 1 + 0 * 2 ^ 2 + ... + 1 * 2 ^ 10 == 2 ^ 10 == 1024

原码、反码、补码

二进制运算涉及到原码、反码、补码，其中正数的原码、反码、补码都是一样的，而负数则不同。负数的反码为符号位不变，其它位取反（0变成1，1变成0），补码则为反码加一。0与正数一样，反码、补码都是其原码0。
而在计算机中，正数由原码（也可以理解为补码，补码原码是一样的）而负数由补码来形式来表示。
计算机中负数使用补码表示的原因可能是由于有符号整数表示范围造成成的。一个无符号字节表示整数范围为：[0, 255]刚好256个整数，而有符号的整数范围则是：[-128, 127]，如果是无符号整数可以用[00000000, 11111111]来表示这个范围，而在有符号的整数只能用[11111111, 01111111]但这只能表示到[-127, 127]，而无法表示-128。
可以推导一下，如果是-127，它的反码为：10000000，而它的补码则为：10000001，而比这个补码小一位的数字刚好是：10000000，也就变相表示了-128，但其对应的原码在计算机中无法表示，所以计算机中采用补码表示负数。
上述推断过程来自：http://blog.chinaunix.net/uid-26495963-id-3074603.html

二进制运算

二进制实现加法运算，比如在十进制中1 + 2 == 3，而用二进制计算为：

00000000 00000000 00000000 00000001
+
00000000 00000000 00000000 00000010
=
00000000 00000000 00000000 00000011 （十进制为3）

二进制减法，实际是将减法转换为正数与负数相加，实际仍是加法运算，如在十进制中1 - 2 == -1，用二进制计算为：

# 这里需要先找到1的补码，因为计算项中有负数（计算机中负数使用补码表示）：1 + (-2)
00000000 00000000 00000000 00000001
+ 
11111111 11111111 11111111 11111110  （原码：10000000 00000000 00000000 00000010，反码：11111111 11111111 11111111 11111101）
==
11111111 11111111 11111111 11111111
# 将计算结果（补码）转换为反码：11111111 11111111 11111111 11111110，
# 再转换为原码：10000000 00000000 00000000 00000001，
# 即十进制中的：-1

进制转换

所谓进制就是人们用来计数的方法，比如十进制，逢十进一；二进制，逢二进一，常用的还有八进制、十六进制。

进制转换本质

“数制”只是一套符号系统来表示指称“量”的多少，无论“数制”怎么变或者使用任意一种“数制”，其所表示“量”仍是一致的，这一点是进制转换的基础。任意一种进制的基本表示方法可以以如下形式表示（负进制不予考虑）：

n位的R进制中的数位排列是这样的：R^n-1 R^n-2 ... R^2 R^1 R^0

以十进制为例：1024 == 1 * 10^3 + 0 * 10^2 + 2 * 10^1 + 4 * 10^0 == 1000 + 0 + 20 + 4
而二进制则是一个道理：0000 1101 == 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0 == 8 + 4 + 0 + 1 == 13

短除法实现进制转换

关于进制转换一种十分常见的方法是“短除法”，按进制整除取余，将每次余数倒排即为转换后的进制表示结果，如：十进制整数17转换为二进制

# 当整除结果为0时计算结束
17 / 2 == 8，余1
8 / 2 == 4，余0
4 / 2 == 2，余0
2 / 2 == 1， 余0
1 / 2 == 0，余1
# 余数倒排即为（前面补0）：00010001
# 00010001 == 1 * 2^4 + 1 == 16 + 1 == 17

下面是一段使用Java实现的进制转换代码

        // 以十进制数字 1024 为例，测试进制间转换
        int number = 1024;

        // 使用短除法转换为二进制，短除法转换时除数为进制值，这里是二进制，所以是2
        // 当整数被除尽后，余数倒排序即为转换后的二进制数字，因为要倒排，这里采用栈结构存储余数
        Stack<Integer> stack = new Stack<>();
        int m = number;
        while (m != 0) {
            // 整除后的余数
            stack.push(m % 2);
            // 整除后的结果
            m /= 2;
        }
        // 将数据取出，组成二进制序列
        // 10000000000
        while (!stack.isEmpty()) {
            System.out.print(stack.pop());
        }
        System.out.println();
        // 测试结果是否正确(后面的项全是0，所以省略了)
        assertEquals(number, 1 * (int) (Math.pow(2, 10)));

十进制转换为八进制、十六进制的方法是一样的，但需要注意的是十六进制中[10-16]由英文字母[a-f]表示，所以自定义实现进制转换时需要特殊处理。而其它进制间转换通常先转换为十进制，再转换为目标进制，所以转换过程是一致的。

Java进制转换API

在Java中，JDK默认提供了一系列进制转换方法

        // Integer提供的进制转换方法
        // 十进制转换二进制
        assertEquals("10000000000", Integer.toBinaryString(1024));
        // 十进制转换八进制
        assertEquals("2000", Integer.toOctalString(1024));
        // 十进制转换十六进制
        assertEquals("400", Integer.toHexString(1024));
        assertEquals("40c", Integer.toHexString(1036));

        // 其它进制转换为十进制
        assertEquals(1024, Integer.parseInt("10000000000", 2));
        assertEquals(1024, Integer.parseInt("2000", 8));
        assertEquals(1024, Integer.parseInt("400", 16));

        // 字符串格式化使用占位符进行进制转换
        // 1024, 2000, 400，没有二进制格式化方法
        System.out.println(String.format("%d, %o, %x", 1024, 1024, 1024, 1024));
        // 1024, 02000, 0x400
        System.out.println(String.format("%d, %#o, %#x", 1024, 1024, 1024, 1024));

位运算及位运算符

程序中所有数据最终都是以二进制存储的，而位运算则是针对二进制直接进行计算的一种方法，通常性能会非常高（目前CPU对加法做了优化，可以达到二进制运算的性能，但乘法仍差一些）。
Java中提供了一组位运算符，分别是：按位与&、按位或|、按位异或^、按位取反~、左移<<、右移>>以及无符号右移>>>，下面分别演示其用法及效果。

按位与 &

仅当两个操作数都是1时，输出结果才为1，否则为0

        // 比较数二进制长度不等时前面补0对齐
        // 12 -> 1100
        //  5 -> 0101
        // 12 & 5 = 0100 0 4
        assertEquals(4, 12 & 5);
        // 使用二进制写法测试
        assertEquals(0b0100, 0b1100 & 0b0101);

按位或 |

仅当两个操作数都是0时，输出结果才为0，否则为1

        assertEquals(13, 12 | 5);
        assertEquals(0b1101, 0b1100 | 0b0101);

按位异或 ^

仅当两个操作数不同时，输出结果才为1，否则为0

        assertEquals(9, 12 ^ 5);
        assertEquals(0b1001, 0b1100 ^ 0b0101);

按位取反 ~

这是一个单目运算符，用于将全部数字取反：0为1，1为0。将一个二进制数按位取反，等效于-1减去该数，如：~12 == -13

        // 注意，上面都是简写的形式，前面的0未写出来，但取反时要写全，否则结果是错的，int类型是32位
        // 下面目标数字实际是：0000000000000000000000000001100，按位取反：11111111111111111111111111110011
        // 注意二进制左边第一位是0，表示无符号整数（为1表示负数，即有符号整数），要使用Integer.parseUnsignedInt()方法转换
        assertEquals(0b11111111111111111111111111110011, ~0b1100);
        // ~12 == -1 - 12 == -13
        assertEquals(-13, ~12);
        // ~-12 == -1 - (-12) == -1 + 12 == 11
        assertEquals(11, ~-12);

左移 <<

把一个数的全部位都向左移动指定位数。其实际效果为：左移n位就是乘以2的n次方

        // 12 -> 1100：1100 << 0 == 1100 == 12 == 12 * 2 ^ 0
        assertEquals(24, 12 << 1);
        // 12 -> 1100：1100 << 1 == 11000 == 24 == 12 * 2 ^ 1
        assertEquals(24, 12 << 1);
        // 12 -> 1100：1100 << 2 == 110000 == 48 == 12 * 2 ^ 2
        assertEquals(48, 12 << 2);
        // 12 -> 1100：1100 << 3 == 1100000 == 96 == 12 * 2 ^ 3
        assertEquals(96, 12 << 3);

右移 >>

把一个数的全部位都向右移动指定位。其实际效果为：右移n位就是除以2的n次方结果取整

        // 1100 >> 1 == 0110 == 6
        assertEquals(6, 12 >> 1);
        // 1100 >> 2 == 0011 == 3
        assertEquals(3, 12 >> 2);
        // 1100 >> 3 == 0001 == 1
        assertEquals(1, 12 >> 3);
        // 1100 >> 4 == 0000 == 0
        assertEquals(0, 12 >> 4);

        // 100000 >> 5 == 000001 == 1
        assertEquals(1, 32 >> 5);
        assertEquals(2, 32 >> 4);
        assertEquals(4, 32 >> 3);
        assertEquals(8, 32 >> 2);
        assertEquals(16, 32 >> 1);
        assertEquals(32, 32 >> 0);

无符号右移 >>>

与右移类似，但是符号位仍用原值填充

        // 00000000000000000000000000001100 >>> 1 == 00000000000000000000000000000110
        // => 110 == 6
        assertEquals(12, 12 >>> 0);
        assertEquals(6, 12 >>> 1);
        assertEquals(3, 12 >>> 2);
        assertEquals(1, 12 >>> 3);
        assertEquals(0, 12 >>> 4);
        assertEquals(0, 12 >>> 5);

        // 11111111111111111111111111110100 >>> 1 == 01111111111111111111111111111010
        assertEquals(-12, -12 >>> 0);
        assertEquals(2147483642, -12 >>> 1);
        assertEquals(1073741821, -12 >>> 2);
        assertEquals(536870910, -12 >>> 3);


        // 标志位使用原标志位填充，所以还是1
        // 11111111111111111111111111110100 >> 1 == 11111111111111111111111111111010
        assertEquals(-6, -12 >> 1);
        // 10111111111111111111111111110100 >> 1 == 11011111111111111111111111111010
        assertEquals(-536870918, -1073741836 >> 1);
        assertEquals(-1073741836, 0b10111111111111111111111111110100);
        assertEquals(-536870918, 0b11011111111111111111111111111010);

结语

二进制及进制转换作为编程的基础知识，每个技术人员都应该掌握并熟练应用，尤其是位运算能极大提升程序性能，高级程序员更应精通此道（笔者实际也不擅长，所以这里属于补课）。
本篇内容原本是放后面再写的，但在研究HashMap源码过程中发现大量使用了位运算，所以不得不提前整理出来。