---
# System prepended metadata

title: Miscellaneous

---

# 1. Bitmask

ข้อมูลทุกชนิดในโปรแกรมคอมพิวเตอร์จะถูกเก็บในหน่วยความจำภายในเป็นลำดับของบิต (bit) ซึ่งหมายถึงตัวเลข 0 และ 1 บทนี้จะอธิบายถึงการแทนค่าจำนวนเต็ม (integer) ในรูปแบบบิต พร้อมแสดงตัวอย่างการใช้ตัวดำเนินการบิต (bit operations) ซึ่งจะพบว่าการจัดการและปรับแต่งข้อมูลในระดับบิตนี้มีประโยชน์อย่างมากในการเขียนโปรแกรมเชิงอัลกอริทึม

## 1.1 การแทนข้อมูลด้วยบิต (Bit Representation)
ในทางโปรแกรมมิ่ง จำนวนเต็ม (integer) ที่มีขนาด n บิต จะถูกจัดเก็บในรูปของตัวเลขฐานสอง (Binary Number) ซึ่งประกอบด้วยบิตจำนวน n บิต ตัวอย่างเช่น ประเภทข้อมูล int ในภาษา C++ มีขนาด 32 บิต หมายความว่าจำนวนเต็มประเภท int จะประกอบด้วยบิตทั้งหมด 32 บิต

ตัวอย่างเช่น ตัวเลข 43 ในประเภทข้อมูล int จะถูกเก็บในหน่วยความจำในรูปฐานสองดังนี้:

$$00000000000000000000000000101011$$

การนับตำแหน่งของบิต (index) จะนับจากขวาไปซ้าย (เริ่มต้นจากบิตที่ 0 ทางด้านขวาสุด) ถ้าหากต้องการเปลี่ยนข้อมูลที่อยู่ในรูปแบบบิต $b_kb_{k-1}...b_2b_1b_0$ ไปเป็นจำนวนเต็มฐานสิบ สามารถใช้สูตรดังต่อไปนี้:

$$b_k \cdot 2^k + \dots + b_2 \cdot 2^2 + b_1 \cdot 2^1 + b_0 \cdot 2^0$$

ตัวอย่างเช่น แปลงข้อมูลฐานสองของเลข 43:

$$00000000000000000000000000101011$$

เป็นเลขฐานสิบ จะได้เป็น:

$$(1 × 2^5) + (1 × 2^3) + (1 × 2^1) + (1 × 2^0) = 32 + 8 + 2 + 1 = 43$$

### 1.1.1 Signed Representation (แบบมีเครื่องหมาย)
การจัดเก็บข้อมูลแบบมีเครื่องหมาย จะสามารถเก็บทั้งตัวเลขบวกและตัวเลขลบ โดยจำนวนเต็มชนิดนี้มีช่วงของค่าที่เก็บได้ตั้งแต่ $−2 
^{n−1}$ ถึง $2^{n−1}−1$ ตัวอย่างเช่น ประเภทข้อมูล int ในภาษา C++ ที่มีขนาด 32 บิต จะสามารถเก็บจำนวนเต็มได้ตั้งแต่ $−2^{31}$ ถึง $2^{31}−1$

บิตแรกสุด (บิตทางซ้ายสุด) ของการจัดเก็บข้อมูลแบบมีเครื่องหมายจะบ่งบอกถึงเครื่องหมายของตัวเลข (ถ้าบิตแรกเป็น 0 หมายถึงตัวเลขไม่ติดลบ และถ้าบิตแรกเป็น 1 หมายถึงตัวเลขติดลบ) บิตที่เหลือ $n−1$ บิตจะแสดงค่าของตัวเลขนั้นๆ

การจัดเก็บจำนวนลบ จะใช้เทคนิคที่เรียกว่า Two's Complement (ส่วนเติมเต็มสอง) โดยวิธีการคำนวณตัวเลขตรงข้าม (เช่น -x จาก x) จะทำได้โดยกลับบิตทุกบิตของจำนวนที่มีอยู่ จากนั้นบวกด้วย 1

ตัวอย่างเช่น จำนวน -43 ในประเภทข้อมูล int จะแทนในรูปแบบบิตดังนี้:

$$11111111111111111111111111010101
$$ 


### 1.1.2 Unsigned Representation (แบบไม่มีเครื่องหมาย)
การจัดเก็บข้อมูลแบบไม่มีเครื่องหมาย จะสามารถเก็บได้เฉพาะตัวเลขที่ไม่ติดลบ แต่ช่วงค่าที่เก็บได้จะกว้างขึ้น คือจะสามารถเก็บตัวเลขได้ตั้งแต่ 0 ถึง $2^n-1$ เช่น ประเภทข้อมูล unsigned int ในภาษา C++ ที่มีขนาด 32 บิต จะเก็บได้ตั้งแต่ $0$ ถึง $2^{32}-1$

### 1.1.3 ความสัมพันธ์ระหว่าง Signed และ Unsigned
เลขจำนวนเต็มที่ติดลบ $-x$ ใน signed representation จะมีค่าเท่ากับ $2^n-x$ ใน unsigned representation ตัวอย่างเช่น โค้ดด้านล่างแสดงให้เห็นความสัมพันธ์นี้:

```cpp
int x = -43;
unsigned int y = x;
cout << x << "\n"; // แสดง -43
cout << y << "\n"; // แสดง 4294967253 (2^32 - 43)
```

### 1.1.4 Overflow (การล้นของข้อมูล)

ถ้าตัวเลขที่ถูกจัดเก็บมีค่ามากกว่าค่าสูงสุดที่กำหนดไว้ จะเกิดเหตุการณ์ที่เรียกว่า Overflow

- สำหรับข้อมูลชนิดมีเครื่องหมาย (signed representation) เมื่อเกินค่าบน $2^{n−1}−1$ ตัวเลขต่อไปจะวนกลับมาเริ่มที่ค่าล่างสุดคือ $−2^{n−1}$
 
- สำหรับข้อมูลชนิดไม่มีเครื่องหมาย (unsigned representation) เมื่อเกินค่าสูงสุด $2^n−1$ จะวนกลับมาเริ่มต้นที่ $0$

ตัวอย่างการเกิด Overflow ใน C++:
```cpp
int x = 2147483647; // ค่าสูงสุดของ int คือ 2^31 - 1
cout << x << "\n";  // 2147483647
x++;                // เพิ่มค่าขึ้นไปอีก 1
cout << x << "\n";  // -2147483648 (วนกลับไปที่ค่าต่ำสุด -2^31)
```

เมื่อเพิ่มตัวเลขจากค่าสูงสุดไปอีกหนึ่ง หน่วยความจำที่เก็บจำนวนเต็มจะวนกลับไปเริ่มต้นที่ตัวเลขต่ำสุด ซึ่งเป็นลักษณะเฉพาะของข้อมูลชนิด signed integer ที่ใช้ two’s complement ในการจัดเก็บ

## 1.2 การดำเนินการกับบิต (Bit Operations)

### 1.2.1 การดำเนินการ AND
การดำเนินการ AND $x\&y$ จะให้ผลลัพธ์เป็นตัวเลขที่มีบิต 1 ในตำแหน่งที่ทั้ง x และ y มีบิต 1 ตัวอย่างเช่น $22\&26=18$ เนื่องจาก
$$
\begin{array}{r@{\quad}l}
10110 & (22) \\
\&\;11010 & (26) \\
\hline
=\;10010 & (18)
\end{array}
$$

### 1.2.2 การดำเนินการ OR
การดำเนินการ OR $x∣y$ จะให้ผลลัพธ์เป็นตัวเลขที่มีบิต 1 ในตำแหน่งที่อย่างน้อยหนึ่งใน $x$ หรือ $y$ มีบิต 1 ตัวอย่างเช่น $22∣26=30$ เนื่องจาก
$$
\begin{array}{r@{\quad}l}
10110 & (22) \\
\&\;11010 & (26) \\
\hline
=\;11110 & (30)
\end{array}
$$

### 1.2.3 การดำเนินการ XOR 
การดำเนินการ $x⊕y$ จะให้ผลลัพธ์เป็นตัวเลขที่มีบิต 1 ในตำแหน่งที่มีเพียงหนึ่งใน $x$ และ $𝑦$ มีบิต 1 ตัวอย่างเช่น $22⊕26=12$ เนื่องจาก
$$
\begin{array}{r@{\quad}l}
10110 & (22) \\
\&\;11010 & (26) \\
\hline
=\;01100 & (12)
\end{array}
$$

### 1.2.4 การดำเนินการ NOT 
การดำเนินการ NOT $∼x$ จะให้ผลลัพธ์เป็นตัวเลขที่ทุกบิตของ $x$ ถูกกลับค่า (invert) สูตร $∼x=−x−1$ จะถูกนำมาใช้ เช่น 
$∼29=−30$ ผลของการดำเนินการ NOT ในระดับบิตขึ้นอยู่กับความยาวของการแทนค่าบิต เนื่องจากการดำเนินการนี้จะกลับค่าทุกบิต
ตัวอย่าง ถ้าหากตัวเลขเป็นจำนวนเต็มชนิด 32 บิต ผลลัพธ์จะเป็นดังนี้: 
$$
\begin{array}{r@{\quad}l}
x=29  & 00000000000000000000000000011101 \\
~x=-30 & 11111111111111111111111111100010
\end{array}
$$

### 1.2.5 การเลื่อนบิต (Bit Shifts)
การเลื่อนบิตทางซ้าย $x≪k$ จะเติมบิต 0 จำนวน k บิตลงไปที่ด้านขวาของตัวเลขและการเลื่อนบิตทางขวา $x≫k$ จะลบบิต k ตัวสุดท้ายออกจากตัวเลข
ตัวอย่างเช่น 
$14≪2=56$ เพราะ 14 เป็น 1110 และ 56 เป็น 111000
$49≫3=6$ เพราะ 49 เป็น 110001 และ 6 เป็น 110
โดยการเลื่อนบิตทางซ้าย $x≪k$ เทียบเท่ากับการคูณ 
x ด้วย $2^k$ และการเลื่อนบิตทางขวา $x≫k$ เทียบเท่ากับการหาร x ด้วย $2^k$ โดยปัดเศษลงเป็นจำนวนเต็ม

## 1.3 การแทนเซตด้วย Bitmask

ทุก ๆ ชุดย่อย (subset) ของเซต ${0,1,2,…,n−1}$ สามารถแทนได้ด้วยจำนวนเต็มที่มี $n$ บิต โดยที่บิตที่มีค่า 1 จะบอกว่าองค์ประกอบนั้นอยู่ในชุดหรือไม่ วิธีการนี้เป็นวิธีที่มีประสิทธิภาพในการแทนชุด เนื่องจากแต่ละองค์ประกอบใช้เพียงบิตเดียวของหน่วยความจำ และสามารถดำเนินการกับชุดต่าง ๆ ได้ด้วยการใช้การดำเนินการระดับบิต

ตัวอย่างเช่น เนื่องจาก int ในภาษา C++ เป็นชนิดข้อมูลที่มีขนาด 32 บิต จึงสามารถแทนชุดย่อยของเซต ${0,1,2,…,31}$ ได้
การแทนชุด ${1,3,4,8}$ ด้วย bitmask คือ:
$$00000000000000000000000100011010$$
ซึ่งสอดคล้องกับจำนวนเต็มที่ได้จากการคำนวณ:
$2^8+2^4+2^3+2^1=256+16+8+2=282$

### 1.3.1 การกระทำทางเซต Set Operation

**1. การตั้งค่าบิต**
การตั้งค่าบิต (Setting a Bit) หมายถึงการเปลี่ยนค่าบิตจาก 0 เป็น 1 โดยใช้ตัวดำเนินการ OR (|) ร่วมกับการเลื่อนบิต (<<) 
โดยสูตรที่ใช้คือ: `integer | (1 <<bit_position_to_be_set)`
ตัวอย่าง: ตั้งค่าบิตที่ตำแหน่งที่ 5 ในตัวเลข 11
```cpp
int x = 11;  // 11 ในไบนารี: 1011
// ตั้งค่าบิตที่ตำแหน่งที่ 5
x = x | (1 << 5);
cout << "Result after setting the fifth bit: " << x;
// Result after setting the fifth bit: 43
```

**2. การล้างค่าบิต**
การล้างค่าบิต (Clearing a Bit) หมายถึงการตั้งค่าบิตจาก 1 เป็น 0 โดยไม่เปลี่ยนแปลงบิตอื่น ๆ ใช้ตัวดำเนินการ AND (&) ร่วมกับ NOT (~) 
ดังนี้: `integer & ~(1 <<bit_position_to_clear)`
ตัวอย่าง: ล้างค่าบิตที่ตำแหน่งที่ 3 ในตัวเลข 11
```cpp
int x = 11;  // 11 ในไบนารี: 1011
// ล้างค่าบิตที่ตำแหน่งที่ 3
x = x & ~(1 << 3);
cout << "Result after clearing the 3rd bit: " << x;
//Result after clearing the 3rd bit: 3
```

**3. การสลับค่าบิต**
การสลับค่าบิต (Toggling a Bit) หมายถึงการเปลี่ยนค่าบิตจาก 0 เป็น 1 หรือจาก 1 เป็น 0 โดยใช้ตัวดำเนินการ XOR (^) ร่วมกับการเลื่อนบิต (<<)
สูตรคือ: `integer ^ (1 << bit_position_to_toggle)`
ตัวอย่าง: สลับค่าบิตที่ตำแหน่งที่ 0 ในตัวเลข 11
```cpp
int x = 11;  // 11 ในไบนารี: 1011
// สลับค่าบิตที่ตำแหน่งที่ 0
x = x ^ (1 << 0);
cout << "Result after toggling the zeroth bit: " << x;
//Result after toggling the zeroth bit: 10
```
**4. การตรวจสอค่าบิต**
การตรวจสอบว่าบิตที่ตำแหน่งที่กำหนดมีค่าเป็น 1 หรือไม่ สามารถทำได้โดยใช้ตัวดำเนินการ AND (&) ร่วมกับการเลื่อนบิต (<<)
สูตรคือ: `integer & (1 << bit_position_to_check)`
ตัวอย่าง: ตรวจสอบว่าบิตที่ตำแหน่งที่ 3 ในตัวเลข 11 มีค่าเป็น 1 หรือไม่
```cpp
int x = 11;  // 11 ในไบนารี: 1011
if (x & (1 << 3)) {
    cout << "Third bit is set\n";
}
else {
    cout << "Third bit is not set\n";
}
//Third bit is set
```

### 1.3.2 การนำไปใช้ในโปรแกรม
ต่อไปนี้เป็นตัวอย่างโค้ดภาษา C++ ที่ประกาศตัวแปรชนิด `int x` ซึ่งสามารถเก็บชุดย่อยของเซต ${0,1,2,…,31}$ ได้ จากนั้นเพิ่มองค์ประกอบ 1, 3, 4 และ 8 ลงในชุด และพิมพ์ขนาด (จำนวนองค์ประกอบในชุด) ด้วยฟังก์ชัน __builtin_popcount:
```cpp
int x = 0;
x |= (1 << 1); // เพิ่มองค์ประกอบ 1
x |= (1 << 3); // เพิ่มองค์ประกอบ 3
x |= (1 << 4); // เพิ่มองค์ประกอบ 4
x |= (1 << 8); // เพิ่มองค์ประกอบ 8
cout << __builtin_popcount(x) << "\n"; // ผลลัพธ์: 4
```
จากนั้น โค้ดด้านล่างนี้จะแสดงองค์ประกอบทั้งหมดในชุดที่เก็บอยู่ใน `x`:
```cpp
for (int i = 0; i < 32; i++) {
    if (x & (1 << i))
        cout << i << " ";
}
// ผลลัพธ์: 1 3 4 8
```

Bitmasking เป็นเทคนิคที่มีประสิทธิภาพสำหรับการจัดการและแก้ไขข้อมูลในระดับบิต ด้วยการใช้ตัวดำเนินการทางบิต (AND, OR, XOR, NOT, Bit Shifts) คุณสามารถดำเนินการต่าง ๆ เช่น การตั้งค่าบิต, การล้างค่าบิต, การสลับบิต และการตรวจสอบบิตได้อย่างรวดเร็วและมีประสิทธิภาพ ซึ่งเป็นประโยชน์มากในงานที่ต้องการประสิทธิภาพสูงและการประหยัดหน่วยความจำในโปรแกรมมิ่ง

## ตัวอย่างโจทย์
- https://leetcode.com/problems/can-i-win/description/
- https://leetcode.com/problems/shortest-path-to-get-all-keys/description/

# 2. Sliding Window Algorithm

เทคนิค Sliding Window เป็นวิธีการที่นิยมอย่างมากในการแข่งขันเขียนโปรแกรม เพื่อเพิ่มประสิทธ์ภาพในการแก้โจทย์ปัญหาที่เกี่ยวข้องกับอาร์เรย์หรือสตริง โดยเฉพาะอย่างยิ่งเมื่อมีการตรวจสอบช่วงย่อย (subarray หรือ substring) ที่ต่อเนื่องกัน วิธีนี้สามารถช่วยลดความซับซ้อนด้านเวลา (time complexity) จากเดิม $O(N^2)$ ให้กลายเป็น $O(N)$ ในหลายกรณี

## 2.1 Sliding Window แบบคงที่ (Fixed-size Sliding Window)
ใช้ในกรณีที่ขนาดของ window ถูกกำหนดไว้ชัดเจนตั้งแต่แรก

ตัวอย่างโจทย์: หาผลรวมสูงสุดของ subarray ที่มีขนาด $k$
ให้อาร์เรย์ของจำนวนเต็มและจำนวนเต็ม $k$ หาผลรวมสูงสุดของ subarray ต่อเนื่องที่มีขนาด $k$

วิธีการเบื้องต้น (Brute Force) - ความซับซ้อน $O(NK)$

```cpp=
int maxSumBruteForce(vector<int>& nums, int k) {
    int maxSum = INT_MIN;
    for (int i = 0; i <= nums.size() - k; i++) {
        int sum = 0;
        for (int j = i; j < i + k; j++) {
            sum += nums[j];
        }
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}
```
ใช้ Sliding Window - ความซับซ้อน $O(N)$

```cpp=
int maxSumSlidingWindow(vector<int>& nums, int k) {
    int maxSum = 0, windowSum = 0;
    
    // คำนวณผลรวมของ window แรก
    for (int i = 0; i < k; i++)
        windowSum += nums[i];

    maxSum = windowSum;

    // เลื่อน window ไปเรื่อยๆ
    for (int i = k; i < nums.size(); i++) {
        windowSum += nums[i] - nums[i - k];  // เพิ่มค่าตัวใหม่ ลบค่าตัวเก่า
        maxSum = max(maxSum, windowSum);
    }
    return maxSum;
}
```

## 2.2 Sliding Window แบบปรับเปลี่ยนขนาดได้ (Variable-size Sliding Window)
ใช้ในกรณีที่ขนาดของ window สามารถปรับเปลี่ยนได้
ตัวอย่างโจทย์: หาขนาดของ subarray ที่เล็กที่สุดที่มีผลรวม $≥S$
ให้อาร์เรย์ของจำนวนเต็มบวกและตัวเลข $𝑆$ หาขนาดของช่วง subarray ที่เล็กที่สุดที่มีผลรวมอย่างน้อย $S$

วิธี Brute Force - ความซับซ้อน $O(N^2)$:
```cpp!
int minSubArrayLenBruteForce(int S, vector<int>& nums) {
    int n = nums.size();
    int minLen = INT_MAX;

    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];

            if (sum >= S) {
                minLen = min(minLen, j - i + 1);
                break; // เจอผลรวมเกินหรือเท่ากับ S แล้ว ออกจากลูปย่อย
            }
        }
    }

    return (minLen == INT_MAX) ? 0 : minLen;
}
```

วิธี Sliding Window - ความซับซ้อน $O(N)$
```cpp=
int minSubArrayLen(int S, vector<int>& nums) {
    int left = 0, sum = 0, minLen = INT_MAX;

    for (int right = 0; right < nums.size(); right++) {
        sum += nums[right];

        while (sum >= S) {
            minLen = min(minLen, right - left + 1);
            sum -= nums[left++];
        }
    }

    return (minLen == INT_MAX) ? 0 : minLen;
}
```
**ข้อสังเกต - ควรใช้ Sliding Window เมื่อใด?**
- โจทย์ที่ต้องตรวจสอบ subarray หรือ substring ทั้งหมด
- ช่วงข้อมูลที่ต้องการตรวจสอบมีลักษณะ ต่อเนื่องกัน
- สามารถอัปเดตค่าได้อย่างมีประสิทธิภาพ เมื่อเลื่อนตำแหน่งของ window

## ตัวอย่างโจทย์
- https://leetcode.com/problems/minimum-size-subarray-sum/description/
- https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

# 3. Sweep Line Algorithm
อัลกอริทึม Sweep Line หรือบางครั้งเรียกว่า Line Sweep เป็นเทคนิคยอดนิยมที่ใช้ในการแก้ปัญหาเชิงเรขาคณิตและปัญหาที่เกี่ยวข้องกับช่วงเวลา (interval) ในการแข่งขันเขียนโปรแกรม มีแนวคิดหลักคือการกวาด (Sweep) เส้นตรงจินตนาการผ่านเหตุการณ์ (event) หรือจุดต่างๆ บนระนาบหรือแกนจำนวน ซึ่งโดยทั่วไปจะเรียงลำดับไว้ล่วงหน้าตามแกน X หรือเวลา

**ขั้นตอนพื้นฐานของ Sweep Line Algorithm**
1. ระบุเหตุการณ์ (events): แต่ละ event ต้องกำหนดว่าคือการเริ่มต้นหรือสิ้นสุดของช่วง (interval) หรือเหตุการณ์อื่นๆ (เช่น จุดตัดของเส้น)
2. เรียงลำดับเหตุการณ์: เรียง event ทั้งหมดตามพิกัดหรือตามเวลา (ส่วนมากใช้แกน X)
3. กวาดเส้นตรงจากซ้ายไปขวา: กวาดผ่านเหตุการณ์ที่เรียงไว้ทีละ event เก็บข้อมูลที่จำเป็นด้วยโครงสร้างข้อมูล เช่น set, priority queue, multiset
4. ประมวลผลแต่ละเหตุการณ์: เมื่อเจอ event ใหม่ ให้ปรับปรุงข้อมูล (เพิ่ม/ลบ/อัปเดต) และคำนวณผลลัพธ์ที่ต้องการทันที

ตัวอย่าง: หาจำนวนช่วงเวลาที่ซ้อนทับกันมากที่สุด
มีช่วงเวลาหลายช่วงในรูปแบบ `(start,end)` ให้คำนวณหาจำนวนช่วงที่ทับซ้อนกันมากที่สุดในเวลาเดียวกัน

ตัวอย่างข้อมูล:
`[1, 3], [2, 5], [4, 6]`

ผลลัพธ์คือ 2 (ช่วง [2,3] และ [4,5] มีช่วงเวลาที่ซ้อนกันมากที่สุด 2 ช่วงพร้อมกัน)

ตัวอย่างโปรแกรม
```cpp=
#include <bits/stdc++.h>
using namespace std;

int maxOverlap(vector<pair<int, int>> intervals) {
    vector<pair<int, int>> events;

    for(auto interval : intervals) {
        events.push_back({interval.first, 1});   // เริ่มต้นช่วง
        events.push_back({interval.second, -1}); // สิ้นสุดช่วง
    }

    sort(events.begin(), events.end());  // เรียงตามเวลา

    int currentOverlap = 0, maxOverlap = 0;
    for (auto event : events) {
        currentOverlap += event.second;
        maxOverlap = max(maxOverlap, currentOverlap);
    }

    return maxOverlap;
}
```

ความซับซ้อนของ Sweep Line:
Time complexity: $O(n\log n)$ จากการเรียงลำดับเหตุการณ์
Space complexity: $O(n)$ จากการพิจารณาคู่ลำดับ

## ตัวอย่างโจทย์
- https://leetcode.com/problems/meeting-rooms-ii/
- https://leetcode.com/problems/merge-intervals/

# อ้างอิง
- https://cses.fi/book/book.pdf
- https://github.com/tchomphoochan/toi14-tutorial/tree/master
- https://visualgo.net/en
- https://programming.in.th/¬
