位元運算（Bitwise Operations）

 位元運算（Bitwise Operations）用於對數字的二進位表示進行操作。這些操作通常用於底層計算、性能優化和特殊用途，比如在圖像處理、網路編碼、數據壓縮等應用中。以下是 Python 中常用的位元運算符號及其用途：

1. 位元運算符

運算符	名稱	用法	說明
&	位元 AND	a & b	對應位元都為 1 才為 1
|	位元 OR	a | b	只要有一個位元為 1 就為 1
^	位元 XOR	a ^ b	對應位元不同才為 1
~	位元 NOT	~a	位元取反，0 變成 1，1 變成 0
<<	左移位	a << n	將位元往左移 n 位（相當於乘以 2^n）
>>	右移位	a >> n	將位元往右移 n 位（相當於整除 2^n）

2. 位元運算的基本概念

假設我們有兩個整數：

a = 5      # 二進位為 0101
b = 3      # 二進位為 0011

位元 AND：&

• a & b 會比較每一對應的位元，只有當兩者都是 1 時結果才是 1，否則為 0。

a & b = 0101 & 0011 = 0001   # 結果為 1

位元 OR：|

• a | b 會比較每一對應的位元，只要其中一個位元為 1，結果就是 1。

a | b = 0101 | 0011 = 0111   # 結果為 7

位元 XOR：^

• a ^ b 會比較每一對應的位元，若位元不同結果為 1，相同則為 0。

a ^ b = 0101 ^ 0011 = 0110   # 結果為 6

位元 NOT：~

• ~a 會將 a 的位元取反：所有的 0 變成 1，1 變成 0。
• 需要注意的是，Python 使用二補數表示法，~a 會等於 -(a+1)。

~a = ~0101 = 1010  # 結果為 -6（在 Python 中 ~5 等於 -6）

左移位：<<

• a << n 將 a 的位元往左移 n 位，相當於 a * (2**n)。

a << 1 = 0101 << 1 = 1010    # 結果為 10，相當於 5 * 2 = 10
a << 2 = 0101 << 2 = 10100   # 結果為 20，相當於 5 * 4 = 20

右移位：>>

• a >> n 將 a 的位元往右移 n 位，相當於 a // (2**n)。

a >> 1 = 0101 >> 1 = 0010    # 結果為 2，相當於 5 // 2 = 2
a >> 2 = 0101 >> 2 = 0001    # 結果為 1，相當於 5 // 4 = 1

3. 常見的位元運算應用

(1) 檢查數字是否為奇數或偶數

• 使用 & 運算符可以快速檢查數字是否為奇數或偶數。

n = 7
if n & 1:
    print("奇數")
else:
    print("偶數")

(2) 交換變數值（不使用額外變數）

• 使用 XOR 可以交換兩個變數的值，而不需要額外的變數。

a = 5
b = 3
a = a ^ b  # a = 6
b = a ^ b  # b = 5
a = a ^ b  # a = 3
print(a, b)  # 結果為 a = 3, b = 5

(3) 計算 2 的冪次

• 使用左移位 << 可以快速計算 2 的冪次。

print(1 << 3)  # 2^3 = 8
print(1 << 4)  # 2^4 = 16

(4) 快速乘以或除以 2 的冪

• 左移 << 相當於乘以 2 的 n 次方；右移 >> 相當於除以 2 的 n 次方。

x = 5
print(x << 1)  # 10，相當於 5 * 2
print(x >> 1)  # 2，相當於 5 // 2

(5) 設定、清除和切換位元

• 設定位元：將某一位設為 1，例如將第 k 位設為 1：x = x | (1 << k)
• 清除位元：將某一位設為 0，例如將第 k 位清除：x = x & ~(1 << k)
• 切換位元：將某一位取反，例如將第 k 位取反：x = x ^ (1 << k)

利用位元運算來生成子集合

 a = list('abcd')

n = len(a)

sss = []

# 透過位元運算來生成子集合

for i in range(2**n):

    ss = []

    for j in range(n):

        # 檢查 i 的第 j 位是否為 1，如果為 1 則將 a[j] 加入子集合

        if i & (1 << j):

            ss.append(a[j])

    sss.append(ss)

# 輸出所有子集合

print("所有子集合為:")

for ss in sss:

    print(ss)

列出最長遞增子序列（LIS）

 要在程式中列出實際的最長遞增子序列（LIS），可以在計算每個位置的 LIS 長度時，記錄下最長子序列的路徑。

# 輸入的陣列
a = [10, 20, 30, 5, 15, 25]
n = len(a)

# 初始化每個位置的最長遞增子序列長度為1
lis_lengths = [1] * n

# 初始化每個位置的前驅索引，用來追蹤最長子序列的路徑
previous_index = [-1] * n

# 計算每個位置的最長遞增子序列長度並記錄路徑
for i in range(1, n):
    for j in range(0, i):
        if a[i] > a[j] and lis_lengths[i] < lis_lengths[j] + 1:
            lis_lengths[i] = lis_lengths[j] + 1
            previous_index[i] = j  # 記錄位置 j 作為 i 的前驅

# 找出最長遞增子序列的長度及其結尾索引
max_length = max(lis_lengths)
max_index = lis_lengths.index(max_length)

# 追蹤回去找到最長遞增子序列
lis_sequence = []
while max_index != -1:
    lis_sequence.append(a[max_index])
    max_index = previous_index[max_index]

# 由於是從後往前追蹤，所以需要反轉序列
lis_sequence.reverse()

# 輸出結果
print("最長遞增子序列的長度是:", max_length)
print("最長遞增子序列為:", lis_sequence)

程式碼說明

1. 變數初始化：

   • lis_lengths：用來儲存以每個位置為結尾的最長遞增子序列長度，初始值設為 1。
   • previous_index：用來記錄每個元素在 LIS 中的前驅索引，初始值設為 -1。

2. 計算最長遞增子序列長度和前驅索引：

   • 使用兩層迴圈更新 lis_lengths 和 previous_index。
   • 當 a[i] > a[j] 且可以延長 LIS 時，更新 lis_lengths[i] 並將 previous_index[i] 設為 j，表示 a[j] 是 a[i] 的前驅。

3. 找到最長 LIS：

   • 使用 max(lis_lengths) 找到 LIS 的長度，並用 lis_lengths.index(max_length) 找到 LIS 的結尾索引 max_index。

4. 回溯找出 LIS：

   • 使用 previous_index 從 max_index 回溯，逐步找到 LIS 中的元素，並存入 lis_sequence。
   • 回溯結束後，反轉 lis_sequence 得到正確順序的 LIS。

執行結果

如果使用範例陣列 a = [10, 20, 30, 5, 15, 25]，執行結果會是：

最長遞增子序列的長度是: 3
最長遞增子序列為: [10, 20, 30] 或 [5, 15, 25]（取決於程式的路徑選擇）

這樣的程式碼可以輸出 LIS 的長度以及實際的最長遞增子序列。

好的，讓我們逐步追踪這段程式碼的執行過程，看看如何找到最長遞增子序列。

初始變數

1. 輸入陣列：a = [10, 20, 30, 5, 15, 25]
2. 長度：n = 6
3. 最長遞增子序列長度陣列：lis_lengths = [1, 1, 1, 1, 1, 1]，每個元素都初始化為 1，表示每個元素本身都是一個長度為 1 的子序列。
4. 前驅索引陣列：previous_index = [-1, -1, -1, -1, -1, -1]，初始化為 -1，表示每個元素的前驅尚未確定。

追踪過程

我們會對每一對元素 (a[j], a[i]) 進行比較，並根據條件更新 lis_lengths 和 previous_index。

1. i = 1

   • a[1] = 20
   • 比較 a[0] < a[1] (10 < 20)，條件成立。
   • 更新 lis_lengths[1] = lis_lengths[0] + 1 = 2
   • 更新 previous_index[1] = 0，表示 a[0] 是 a[1] 的前驅。
   • 狀態更新：
     • lis_lengths = [1, 2, 1, 1, 1, 1]
     • previous_index = [-1, 0, -1, -1, -1, -1]

2. i = 2

   • a[2] = 30
   • 比較 a[0] < a[2] (10 < 30)，條件成立。
   • 更新 lis_lengths[2] = lis_lengths[0] + 1 = 2
   • 更新 previous_index[2] = 0，表示 a[0] 是 a[2] 的前驅。
   • 比較 a[1] < a[2] (20 < 30)，條件成立。
   • 更新 lis_lengths[2] = lis_lengths[1] + 1 = 3
   • 更新 previous_index[2] = 1，表示 a[1] 是 a[2] 的前驅。
   • 狀態更新：
     • lis_lengths = [1, 2, 3, 1, 1, 1]
     • previous_index = [-1, 0, 1, -1, -1, -1]

3. i = 3

   • a[3] = 5
   • 比較 a[0] < a[3] (10 < 5)，條件不成立。
   • 比較 a[1] < a[3] (20 < 5)，條件不成立。
   • 比較 a[2] < a[3] (30 < 5)，條件不成立。
   • 狀態保持不變：
     • lis_lengths = [1, 2, 3, 1, 1, 1]
     • previous_index = [-1, 0, 1, -1, -1, -1]

4. i = 4

   • a[4] = 15
   • 比較 a[0] < a[4] (10 < 15)，條件成立。
   • 更新 lis_lengths[4] = lis_lengths[0] + 1 = 2
   • 更新 previous_index[4] = 0，表示 a[0] 是 a[4] 的前驅。
   • 比較 a[1] < a[4] (20 < 15)，條件不成立。
   • 比較 a[2] < a[4] (30 < 15)，條件不成立。
   • 比較 a[3] < a[4] (5 < 15)，條件成立。
   • 更新 lis_lengths[4] = lis_lengths[3] + 1 = 2（與 lis_lengths[4] 相等，因此保持不變）
   • 狀態更新：
     • lis_lengths = [1, 2, 3, 1, 2, 1]
     • previous_index = [-1, 0, 1, -1, 0, -1]

5. i = 5

   • a[5] = 25
   • 比較 a[0] < a[5] (10 < 25)，條件成立。
   • 更新 lis_lengths[5] = lis_lengths[0] + 1 = 2
   • 更新 previous_index[5] = 0，表示 a[0] 是 a[5] 的前驅。
   • 比較 a[1] < a[5] (20 < 25)，條件成立。
   • 更新 lis_lengths[5] = lis_lengths[1] + 1 = 3
   • 更新 previous_index[5] = 1，表示 a[1] 是 a[5] 的前驅。
   • 比較 a[2] < a[5] (30 < 25)，條件不成立。
   • 比較 a[3] < a[5] (5 < 25)，條件成立。
   • 比較 a[4] < a[5] (15 < 25)，條件成立。
   • 最終更新 lis_lengths[5] = lis_lengths[4] + 1 = 3（保持不變）
   • 狀態更新：
     • lis_lengths = [1, 2, 3, 1, 2, 3]
     • previous_index = [-1, 0, 1, -1, 0, 1]

找到最長 LIS 的長度與序列

1. LIS 長度：max(lis_lengths) = 3
2. LIS 結尾索引：max_index = lis_lengths.index(3) = 2（或 5）
3. 回溯求 LIS：
   • 從 max_index = 2 開始回溯 previous_index：
     • a[2] = 30，前驅 a[1] = 20，前驅 a[0] = 10。
   • LIS 結果為 [10, 20, 30]。

最終結果輸出

最長遞增子序列的長度是: 3
最長遞增子序列為: [10, 20, 30]

另一條序列是 [5, 15, 25]。

lis 簡例

 a = [10,20,30,5,15,25]

n = len(a)
lis_lengths = [1]*n

for i in range(1,n):
    for j in range(0,i):
        if a[i]>a[j] and lis_lengths[j]<lis_lengths[j]+1:
            lis_lengths[i] = lis_lengths[j]+1
print(max(lis_lengths))

程式碼說明

這段程式的目的是找出陣列 a 中的最長遞增子序列（LIS）的長度。它使用了一個動態規劃的方法，用 lis_lengths 陣列來記錄從每個元素開始的最長遞增子序列的長度。

初始變數

• a = [10, 20, 30, 5, 15, 25]
• n = len(a) = 6
• lis_lengths = [1, 1, 1, 1, 1, 1]：初始值為 1，因為每個元素本身就可以視為長度為 1 的遞增序列。

執行過程

程式使用雙重迴圈，依序比較每個元素與它之前的所有元素。若元素間能形成遞增序列且新的長度比之前記錄的長度長，則更新 lis_lengths 陣列中的值。以下是每個步驟的更新結果：

1. i = 1

   • a[1] = 20 和 a[0] = 10 可以形成遞增序列。
   • 更新 lis_lengths[1] 為 2。
   • lis_lengths 變為 [1, 2, 1, 1, 1, 1]

2. i = 2

   • a[2] = 30 分別與 a[0] = 10 和 a[1] = 20 可以形成遞增序列。
   • 更新 lis_lengths[2] 最終為 3。
   • lis_lengths 變為 [1, 2, 3, 1, 1, 1]

3. i = 3

   • a[3] = 5 沒有與前面的元素形成遞增序列。
   • lis_lengths 保持不變 [1, 2, 3, 1, 1, 1]

4. i = 4

   • a[4] = 15 與 a[0] = 10 可以形成遞增序列。
   • 更新 lis_lengths[4] 為 2。
   • lis_lengths 變為 [1, 2, 3, 1, 2, 1]

5. i = 5

   • a[5] = 25 與 a[0] = 10 和 a[1] = 20 形成遞增序列，最終更新 lis_lengths[5] 為 3。
   • lis_lengths 變為 [1, 2, 3, 1, 2, 3]

最終結果

• 最後 lis_lengths 陣列中的最大值即為最長遞增子序列的長度，max(lis_lengths) = 3。

• 因此，陣列 a = [10, 20, 30, 5, 15, 25] 中的最長遞增子序列長度為 3。