# 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/¬