---
# System prepended metadata

title: '**程式筆記(binary)**'
tags: [code, note, binary]

---

# **程式筆記(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
```
![image](https://hackmd.io/_uploads/Hk7Ga5o2T.png =30%x)


```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相加

同理十進位相加
![image](https://hackmd.io/_uploads/S11FK83eJe.png =50%x)

```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
```

* 找出消失的數字
![image](https://hackmd.io/_uploads/HkyHxdneyx.png =60%x)

```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`