Skip to content

位元運算

二進制

int 是32位元有號整數，2147483647(最大值)表示如下

編號 32(符號位) 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
二進制數字 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

第32位為0，因為它代表符號。所以int可以儲存的數字上限為2^31-1

既然講到符號位，那就來講講。

符號

已經知道2147483647(最大值)二進制表示法，那負數如何表示呢？
在此之前我們需要先知道如何正負數轉換

我們先操作如何將5變成-5，以8位元為例

一、5的二進制

編號 8(符號位) 7 6 5 4 3 2 1
二進制數字 0 0 0 0 0 1 0 1

二、取反所有位元(~運算) (現在數字是-6

編號 8(符號位) 7 6 5 4 3 2 1
二進制數字 1 1 1 1 1 0 1 0

三、加1 (現在數字是-5

編號 8(符號位) 7 6 5 4 3 2 1
二進制數字 1 1 1 1 1 0 1 1

簡單來說
要把正整數n變成負數
就是計算「 \(\sim n + 1 = m\) 」

那麼要把負整數m變成正數
就是計算「 \(\sim (m - 1) = n\) 」

可以寫為

\[
\sim n + 1 = m
\]

移項之後會變成

\[
\sim (m - 1) = n
\]

這樣就完成了5變成-5

為甚麼要這樣做呢？
因為減法運算會需要「借位」，「借位」是個非常麻煩的東西

假設我們要計算「5 - 3」
如果我們他換成「5 + (-3)」就會方便很多

利用「符號位」就能達到效果

我們來看看 5 - 3 和 3 - 5 如何運作

步驟一：把 5 - 3 換成 5 + (-3)
也就是把 3 換成 -3
也就是把 3 取補數變為 -3

~(3) = -4
00000011 → 11111100   // ~3 = -4

(-4) + 1 = -3
11111100 + 1 = 11111101  // (-4) + 1 = -3

步驟二：執行加法運算

5 + (-3)
  00000101  (5 的二進位)
+ 11111101  (-3 的二進位補碼)
------------
 100000010  (含溢位)
------------
  00000010  (結果)

所以 5 - 3 在位元運算會得到00000010也就是 2

步驟一：把 3 - 5 換成 3 + (-5)
也就是把 5 換成 -5
也就是把 5 取補數變為 -5

~(5) = -6
00000101 → 11111010  // ~5 = -6

(-4) + 1 = -3
11111010 + 1 = 11111011  // (-6)+1 = -5

步驟二：執行加法運算

3 + (-5)
  00000011  (3 的二進位)
+ 11111011  (-5 的補碼)
------------
  11111110  (結果)

所以 3 - 5 在位元運算會得到11111110也就是 -2

其實在大數運算時也可以使用「補數」的方式計算。

位元溢出（overflow）

我們在做加減法時，電腦是使用位元運算
當我們要做5+1時(以8位元的話)，電腦就是把00000101 + 00000001
就會變成00000102，也就是00000110，變成6

那如果我們遇到 -1 + 1 = 0 時電腦會如何處裡呢？以8位元為例

一、 -1 的二進制

編號 8(符號位) 7 6 5 4 3 2 1
二進制數字 1 1 1 1 1 1 1 1

二、 -1+1(進位)

編號 9(虛構) 8(符號位) 7 6 5 4 3 2 1
二進制數字 1 0 0 0 0 0 0 0 0

三、溢出的並不會儲存，便直接刪除變成0

編號 8(符號位) 7 6 5 4 3 2 1
二進制數字 0 0 0 0 0 0 0 0

這是基本的溢出處理方式，那為甚麼超過 int 上限 2147483647 會稱為位元溢出（overflow）呢？

我們都知道int n=2147483647，若 +1 換變成-2147483648
我們來看看過程

一、 2147483647 的二進制

編號 32(符號位) 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
二進制數字 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

二、 2147483647+1

編號 32(符號位) 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
二進制數字 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

可以發現他的符號位變成1了，「溢出」了數字位，變成 -2147483648 ，所以稱為位元溢出（overflow），無法得到預想中的 2147483648

位元基本操作

一個位元

~(反)

造反

將數字的每一位進行取反操作，0變為1，1變為0。

int a = 5; // 0101
int result = ~a; // 1010 -> -6 (因為有符號位元，這裡顯示的是補碼)

<<(左移)

全部左移

將數字的二進位表示形式中的所有位向左移動指定的位數，右側補0。這相當於數字乘以2的指定次方。

int a = 5; // 0101
int result = a << 1; // 1010 -> 10

>>(右移)

全部右移

將數字的二進位表示形式中的所有位向右移動指定的位數，左側根據數字是否有符號進行補位。這相當於數字除以2的指定次方。

int a = 5; // 0101
int result = a >> 1; // 0010 -> 2

兩個位元

&(與)

都true才true

將兩個數字的二進位表示形式中的每一位進行「與」運算，只有當兩個對應位都是1時，結果才為1，否則為0。

int a = 5; // 0101
int b = 3; // 0011
int result = a & b; // 0001 -> 1

|(或)

其一true就true

將兩個數字的二進位表示形式中的每一位進行「或」運算，只要兩個對應位中有一個是1，結果就為1。

int a = 5; // 0101
int b = 3; // 0011
int result = a | b; // 0111 -> 7

^(異或)

兩個不同才是true

將兩個數字的二進位表示形式中的每一位進行「異或」運算，當兩個對應位不同時，結果為1，相同時結果為0。

int a = 5; // 0101
int b = 3; // 0011
int result = a ^ b; // 0110 -> 6

GPT：
為什麼叫做 "exclusive OR"（互斥或）？
因為它的邏輯規則是這樣：
* 當兩個輸入「不同」時，結果為 1。
* 當兩個輸入「相同」時，結果為 0。
所以它是一種「排他性（exclusive）」的「或」邏輯，只有其中一個為真時才為真。

A B A OR B A XOR B
0 0 0 0
0 1 1 1
1 0 1 1
1 1 1 0 ← 差異在這裡！

注意事項：<<(左移)

先看到以下程式碼

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n=1<<31;
    cout<<n;
}

輸出
-2147483648

這時會有個疑問，為何會溢位呢？

因為「long long n=1<<31;」裡面的「1」資料型態為int

正確寫法：

一、

#include <bits/stdc++.h>
using namespace std;int main(){
    long long n=((long long)1)<<35;
    cout<<n;
}

二、

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n=1;
    n=n<<35;
    cout<<n;
}

輸出：
34359738368

把位元當作陣列的操作

From 2024 IONC

// 查詢第i個元素是否在集合s中
bool inSet(int i, int s) { return (s >> i) & 1; }

// 將第i個元素加入集合中
void ins(int i, int &s) { s |= (1 << i); }

// 將第i個元素移除集合
void rm(int i, int &s) { s &= ~(1 << i); }

// 取兩集合s1, s2交集
int inter(int s1, int s2) { return s1 & s2; }

// 取兩集合s1, s2聯集
int uni(int s1, int s2) { return s1 | s2; }

// 取集合s的補集
int comp(int s) { return ~s; }