布林代數

邏輯運算

& 位元與運算(AND)

位元與運算符將兩個數字的每個位元進行比較。如果兩個位元都為1，則結果為1；否則為0。

$$F(x,y)=x\cdot y$$

A	B	A & B
0	0	0
0	1	0
1	0	0
1	1	1

例如： 5 & 3 = 1 (二進制：0101 & 0011 = 0001)

範例

a = 5
b = 3
c = a & b
print(c) # 1

| 位元或運算(OR)

位元或運算符將兩個數字的每個位元進行比較。如果至少一個位元為1，則結果為1；否則為0。

$$F(x,y)=x+y$$

A	B	A | B
0	0	0
0	1	1
1	0	1
1	1	1

例如： 5 | 3 = 7 (二進制：0101 | 0011 = 0111)

範例

a = 5
b = 3
c = a | b
print(c) # 7

^ 位元異或運算(XOR)

位元異或運算符將兩個數字的每個位元進行比較。如果兩個位元不同，則結果為1；否則為0。

$$F(x,y)=x\oplus y$$

A	B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

例如： 5 ^ 3 = 6 (二進制：0101 ^ 0011 = 0110)

範例

a = 5
b = 3
c = a ^ b
print(c) # 6

~ 位元反轉運算(NOT)

位元反轉運算符將數字的每個位元進行反轉。0變成1，1變成0。

A	~A
0	1
1	0

例如： ~5 = -6 (二進制：~0101 = 1010，補碼表示法)

範例

a = 5
c = ~a
print(c) # -6

布林代數定律

名稱	AND	OR
交換律 (Commutative Law)	$AB=BA$	$AB=BA$
結合律 (Associative Law)	$(AB)C=A(BC)$	$(AB)C=A(BC)$
分配律 (Distributive Law)	$A(BC)=(AB)(AC)$	$A(BC)=(AB)(AC)$
同一律 (Identity Law)	$A1=A$	$A0=A$
補數律 (Complement Law)	$A{A}^{\prime }=0$	$A+A^{\prime }=1$
德摩根定律 (De Morgan's Laws)	$(AB{)}^{\prime }=A^{\prime }+B^{\prime }$	$(A+B{)}^{\prime }=A^{\prime }{B}^{\prime }$

範例

布林函數的化解

吸收律 (Absorption Law)

範例1

$x+x\cdot y=x$

證明:

x + xy = $x\cdot 1+x\cdot y$

= $x\cdot (1+y)$

= $x\cdot 1$

= $x$

範例2

$x+x^{\prime }y=x+y$

證明:

$x+x^{\prime }y=x\cdot 1+x^{\prime }\cdot y$

$=x\cdot (1+y)+x^{\prime }\cdot y$

$=x+xy+x^{\prime }\cdot y$

$=x+1\cdot y$

$=x+y$

<< 左移運算(Left Shift)

左移運算符將所有位元向左移動指定的位數，右側補0。

A	A << 1
0	0
1	2
2	4
3	6
4	8
5	10

例如： 5 << 1 = 10 (二進制：0101 << 1 = 1010)

範例

a = 5
c = a << 1
print(c) # 10

>> 右移運算(Right Shift)

右移運算符將所有位元向右移動指定的位數，左側補符號位。

A	A >> 1
0	0
1	0
2	1
3	1
4	2
5	2

例如： 5 >> 1 = 2 (二進制：0101 >> 1 = 0010)

範例

a = 5
c = a >> 1
print(c) # 2

牛刀小試

• Leetcode 476.