# **程式筆記(binary)**
:::info
:information_source: 日期 : 2023/02/22
:::
**:thumbsup:基礎**
**運算符**
|
```python
# or
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1
```
&
```python
# and
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
```
^
```python
# XOR
# 相異為True 相同為False
0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 1 = 0
```
XOR特性
```python
0 ^ a = a
a ^ a = 0
b ^ a = a ^ b
```
or v.s. |
```python
or和|的差別
a = True
b = False
result = a or b # result 為 True
a = 1
b = 0
result = 1 or 0 # result 為 True
a = 3 # 11
b = 5 # 101
result = a | b # result 為 7，111
```
---
**技巧**
位移
```python
>> : 數字 // 2
<< : 數字 * 2
15 >> 1 = 7
15 >> 2 = 3
15 << 1 = 30
15 << 2 = 60
```
& 1
```python
8 = 1000, 1000 >> 1 = 100
9 = 1001, 1001 >> 1 = 100
故可以用 & 1 檢查最右邊那位
15 & 1 = 1 # 1111 & 0001 = 0001
8 & 1 = 0 # 1000 & 0001 = 0000
```
bit
```python
總共32數字
2^31, 2^30, ..., 2^1, 2^0
```
```
23 (16+4+2+1)
| 2^4 | 2^3 | 2^2 | 2^1 | 2^0 |
| --- | --- | --- | --- | --- |
| 1 | 0 | 1 | 1 | 1 |
```
bin
```python
# 十進制轉二進制
x = 11
bin(x) # 0b1011
binary_value = bin(x)[2:] # "1011"
```
int(b, 2)
```python
b = "1011"
decimal_value = int(b, 2) # 11
```
```python
4 = 100
5 = 101
...
8 = 1000
9 = 1001
...
```
---
**其他**
```
負數 : binary第一個數字必為1
正轉負 :
3 : 0011
取補 : 1100
加1 : 1101
-3 : 1101
```
byte = 2^3 bit，為大部分計算機架構中的定址單位 (Byte addressing)
**:thumbsup:題解(AND)**
如果去找1的話，基本上都是用and運算式
* Number of 1 Bits 計算1的數量(單個)
```python
class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
while n:
res += n & 1
n = n >> 1
return res
```
* Counting Bits 計算1的數量(多個)
```python
9 // 2 = 4 = 100
9 % 2 = 1
9 = 1001
```
```python
class Solution:
def countBits(self, n: int) -> List[int]:
dp = [0] * (n + 1)
for i in range(n + 1):
dp[i] = dp[i // 2] + (i & 1)
return dp
```
* Reverse Bits 倒反32bit的整數數字
```
總共32數字
2^31, 2^30, ..., 2^1, 2^0
```
```python
(判斷0或1) * (數字該放的位子)
(n & 1) * (2 ** (31 - i))
```
```python
class Solution:
def reverseBits(self, n: int) -> int:
res = 0
i = 0
while i <= 31:
digit = n & 1
res += digit * (2 ** (31 - i))
n = n >> 1
i += 1
return res
```
* binary相加
同理十進位相加
```python
class Solution:
def addBinary(self, a: str, b: str) -> str:
carry = 0
a = int(a)
b = int(b)
res = ""
if not a and not b: # both are zero
return "0"
while a or b or carry:
temp1 = a & 1
temp2 = b & 1
total = temp1 + temp2 + carry
res += str(total % 2)
carry = total // 2
a = a // 10
b = b // 10
return res[::-1]
```
**:thumbsup:題解(XOR)**
同同為0
* Single Number 找出非成對的數字
用XOR特性
```python
class Solution:
def singleNumber(self, nums: List[int]) -> int:
res = 0
for n in nums:
res = res ^ n
return res
```
* 找出消失的數字
```python
class Solution:
def missingNumber(self, nums: List[int]) -> int:
res = len(nums)
for i in range(len(nums)):
res = res ^ nums[i]
res = res ^ i
return res
```
* Sum of Two Integers(兩整數相加)
因為python可以接受比 -2 **31 ~ 2 **31-1 還要大的數字，所以我們需要先用一個mask把數字屏蔽到32個bits以下，這個mask為0xffffffff，也就是0b1111111111111111111111111111111共有32個1
```python
while b != 0:
carry = (a & b) << 1
rest = (a ^ b)
a, b = rest & mask, carry & mask
```
在python中，負數有除了後面的32位代表數字本身，前面會有無限個1
* 如何判斷負數? mask為0xffffffff，十進位為4294967294，除以2恰好為分界，正數與負數的範圍 -2147483648 ~ 2147483648
```python
-3在32bits時是
(...0000000)11111111111111111111111111111101
XOR with mask, aka flip rightmost 32 bits
(...0000000)00000000000000000000000000000010
NOT, aka flipping all bits
(...1111111)1111111111111111111111111111101
合起來就變成 ~(a ^ mask)，亦即須要先和mask做xor，再用not翻轉
```
---
**:thumbsup:進制們**
1. 十進制 (Decimal, Dec) : 我們看得懂的數字
2. 二進制 (Binary) : 計算機 (電腦) 硬體中，指令是以一連串『高』與『低』的電子訊號來保持，以『0b』做為前綴
* 計算機的資料，是以二進位數 (Binary Digit) 來保存，稱之位元 (bit)，二進位的單一個位數 (digit) 即是計算機的最基本單位。
3. 八進制 (Octal, Oct) : 逢8進位
4. 十六進制 (Hexadecimal, Hex) : 資訊領域用的最頻繁的進制，以『0X』做為前綴
* (ex: 0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F、10、11、12、13、14、15、16、17、18、19、1A、1B、1C、1D、1E、1F、20…)(A~F 可為大小寫)
---
by. NotFalse技術客
###### tags: `binary` `note` `code`
Sign in with Wallet
Connect another wallet