三分鐘熟悉進制轉換與位運算

2021 年 2 月 24 日
筆記
二進制, 位運算, 進制轉換

進制和位運算簡介

進制也叫進位制，是一種記數方法，也稱進位計數法，利用這種記數法可以使用有限的數字符號來表示所有的數值。

一種進制中可以使用的數字符號的數目稱為這種進位制的基數，若一個進制的基數為 N，則可稱之為 N 進制，即表示數值時滿 N 進一。

在生活中最常用的是十進制，使用 10 個阿拉伯數字 0 到 9 進行記數。而在電子計算機領域，內部使用的是二進制，電路的狀態通過 0 和 1 表示來實現記數。八進制和十六進制計算機領域也較為常用，尤其十六進制。

位運算則是在程序中對二進制數的一元和二元運算操作。

在 JDK 以及框架源碼中都存在進制轉換和位運算的身影，作為開發人員應該熟悉基本的進制轉換和位運算（最起碼得能看懂吧）。

進制轉換

例如，十進數的 13，二進制的 1101，他們表示相同的數值，只是不同的表現形式而已，那麼不同進制之間如何相互轉換呢？

十進制轉換 N 進制，可以通過「短除法」求餘數然後倒序得到轉換結果，一個十進制數轉換為 N 進制就除以 N，例如：

將十進制數 123 轉換為二進制。

結果：1111011

將十進制數 123 轉換為十六進制。

結果：7b

N 進制轉為十進制可以通過「按位權展開法」來轉換，即在 N 進制中，每個位置的數字乘以進制的基數為底的所處位置序號(從 0 開始)為指數的整數次冪，然後相加。例如：

將二進制數 1111011 轉換為十進制。

1 * 2^6 + 1 * 2^5 + 1 * 2^4 + 1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0
= 1 * 64 + 1 * 32 + 1 * 16 + 1 * 8 + 0 * 4 + 1 * 2 + 1 * 1
= 123

將十六進制數 7b 轉換為十進制

7 * 16^1 + b * 16^0
= 7 * 16 + 11 * 1
= 123

二進制與十六進制互轉

四位二進制數表示的範圍是 0 – 15，用四位二進制數可以表示十六進制的一位數，反之亦然。即二進制轉十六進制可以通過四(位)合一(位)，十六進制轉二進制可以通過一(位)拆四(位)來轉換。例如：
二進制 1111011 轉換為十六進制，0111(7) – 1011(b) 即轉換結果為7b。
十六進制 7b 轉為二進制，7(0111) – b(十進制 11，二進制 1011) 即轉換結果為 1111011。

二進制與八進制互轉

三位二進制數表示的範圍是 0 – 7，用三位二進制數可以表示八進制的一位數，反之亦然。即二進制轉八進制可以通過三(位)合一(位)，八進制轉二進制可以通過一(位)拆三(位)來轉換。例如：
二進制 1111011 轉換為八進制，001(1) – 111(7) – 011(3) 即轉換結果為173。
八進制 173 轉為二進制，1(001) – 7(111) – 3(011) 即轉換結果為 1111011。

負數的二進制

前面介紹的都是正數的二進制轉換，那麼負數的二進制如何表示和轉換的？

首先，我們先了解一下原碼、反碼、補碼，一個數在計算機中的二進制表示形式叫做這個數的機器數，機器數的最高位稱為符號位，正數符號位為 0，負數符號位為 1，而符號位之外部分稱為機器數的真值(表示真正的數值部分)，原碼、反碼、補碼是機器數的表示方法。

原碼： 原碼的表示方法，最高位是符號位，其餘部分表示數值(真值)。正數符號位為 0，負數符號位為 1，0 的符號位可以為 0 或 1(+0 和 -0)。

例如，我們用 8 位二進制表示一個數，則 +11 的原碼為 00001011，-11 的原碼就是 10001011。

在數學中 1 + (-1) = 0，如果使用原碼直接參与數學運算，00000001 + 10000001 = 10000010(換算成十進制為 -2)，顯然不對。所以原碼的符號位不能直接參与運算，必須和其他位分開，這就增加了硬件的開銷和複雜性。為了便於 ALU (算術邏輯單元，實現多組算術運算和邏輯運算的組合邏輯電路)的設計，又發展出反碼、補碼。

反碼： 反碼的表示方法，正數的反碼等於其原碼，而負數的反碼通過保留其符號位，將其原碼的數值位(真值)取反。

例如，同樣用 8 位二進制表示一個數，11 = 00001011(原碼) = 00001011(反碼)，
-11 = 10001011(原碼) = 11110100(反碼)。

雖然，反碼可以消除原碼存在的計算問題，由於反碼存在多餘的負零等問題，此方式並未被廣泛應用。

補碼： 補碼的表示方式，正數和 0 的補碼等於其原碼，且補碼的 0 只有一個表示方式，不分 +0 和 -0。負數是將他的反碼加 1 得到補碼。

例如，11 = 00001011(原碼) = 00001011(反碼) = 00001011(補碼)，-11 = 10001011(原碼) = 11110100(反碼) = 11110101(補碼)。

一種簡單方式算出補碼

負數的補碼一般情況下通過負數的原碼得到反碼，在將反碼加 1 獲得補碼。這裡有一種簡單的計算補碼方法。

將對應的正數原碼從最低比特位向高比特位查找。
若該比特位為 0，補碼對應比特位填 0，繼續向高比特位查找。
若找到第一個為 1 的比特位，將補碼對應比特位填 1。
然後，將其餘未轉換的比特位全部取反。

例如：計算 -20 的補碼。

計算機為什麼使用補碼

為了簡化 ALU 設計，減法轉換為加法來計算，例如，1 – 1 可以轉換為 1 + (-1) = 00000001 + 11111111 = 100000000 (由於加數和被加數都是 8 位，因此運算結果也限制在 8 位，前面溢出的比特位 1 忽略，所以結果為 00000000 = 0)，即一個數加上另一個數的補碼來表示。

這樣只要有加法電路即可完成各種有號數加減法，對於乘除法，乘法在計算機中其實就是不斷的做加法，除法就是相減，本質也是加法，所以四則運算的基礎都是由加法而來，電路設計得到了很大簡化。補碼解決了原碼和反碼出現的問題，因此計算機中數值使用補碼方式來計算和存儲的。

Java 內置的進制轉換 API

JDK 的 Integer 和 Long 類提供了常用的進制相互轉換方法。

進制轉換	java.lang.Integer	java.lang.Long
10進制 → 2進制	toBinaryString(int i)	toBinaryString(long i)
10進制 → 8進制	toOctalString(int i)	toOctalString(long i)
10進制 → 16進制	toHexString(int i)	toHexString(long i)
10進制 → n 進制	toString(int i, int radix)	toString(long i, int radix)
n 進制 → 10進制	valueOf(String s, int radix) parseInt(String s, int radix)	valueOf(String s, int radix) parseLong(String s, int radix)

System.out.println(Integer.toBinaryString(13)); // 十轉二，結果為 1101
System.out.println(Integer.toOctalString(13));  // 十轉八，結果為 15
System.out.println(Integer.toHexString(13));    // 十轉十六，結果為 d
System.out.println(Integer.toString(13, 5));    // 十轉五，結果為 23
System.out.println(Integer.valueOf("23", 5));   // 五轉十，結果為 13

位數補齊

如 int 類型數據長度是 32 位，輸出時前面的「0」會被省略，想補齊可以使用 commons-lang3-*.jar 的 StringUtils 工具類對輸出的字符串位數補齊。示例：

String fullStr = StringUtils.leftPad("1010", 32, "0"); // 對二進制 1010 位數補齊
System.out.println(fullStr); // 輸出結果：00000000000000000000000000001010

Java 中進制前綴

Java 對二進制、八進制、十六進制提供了字面量前綴的表現形式，可以直接使用這幾種進制形式計算或賦值，例如：

// 都表示十進制的 10
int i1 = 10; 	 // 十進制，沒有前綴
int i2 = 0b1010; // 二進制，前綴   0b(Java 7 或更高版本)
int i3 = 012; 	 // 八進制，前綴   0
int i4 = 0xA; 	 // 十六進制，前綴 0x

System.out.println(i2 + 1);
System.out.println(i3 + 1);
System.out.println(i4 + 1);

位運算

位運算是在程序中對二進制數的一元和二元運算操作，其運算符有 & ，| ，~ ，^ ，<<， >>， >>> ，接下來我們來逐個說明：

& (按位與)

按位「與」操作處理兩個長度相同的二進制數，兩個相應的二進位都為 1，該位的結果值才為 1，否則為 0。
如圖：10 & 3 (int 類型長度 32 位，下圖補位的 0 已被省略)。

| (按位或)

按位「或」操作處理兩個長度相同的二進制數，兩個相應的二進位只要有一個為 1，該位的結果值就為 1。
例如：10 | 3 (int 類型長度 32 位，下圖補位的 0 已被省略)。

~ (按位非)

該操作符是一元運算符，對一個二進制數的每一位執行邏輯反操作，使相應的位 1 變為 0，0變為 1。
例如：~ 3

^ (按位異或)

按位「異或」操作處理兩個等長的二進制數，如果某對應位值不同則結果值為 1，否則為 0。
例如：10 ^ 3 (int 類型長度 32 位，下圖補位的 0 已被省略)。

<< (左移)

向左進行移位操作，高位丟棄，移位後空缺的低位補 0。
例如：10 << 2

>> (右移)

向右移位，移位後空缺高位補 0，若為負數，高補 1。
例如：10 >> 2 和 -10 >> 2

>>> (無符號右移)

向右移位，無論正負，高位空缺部分補 0。
例如：10 >>> 2 和 -10 >>> 2

應用示例

m * 2^n 或 m / 2^n

System.out.println(2 << 1); // 2 * 2^1 = 4 ，相當於乘以 2^1
System.out.println(3 >> 1); // 3 / 2^1 = 1 , 相當於除以 2^1 向下取整

奇數偶數判斷

if(m & 1 == 1) {
    System.out.println("奇數");
} else {
    System.out.println("偶數");
}

隨機概率

// lr = 隨機數;
if ((lr & 0x3) == 0) {
    // 有 1/4 的概率執行該代碼塊
}

本文連接：//www.cnblogs.com/newobjectcc/p/14438707.html

參考：
維基百科 – //zh.wikipedia.org

Tags: 二進制位運算進制轉換