# 使用位操作進行空間優化 > 原文： [https://www.geeksforgeeks.org/space-optimization-using-bit-manipulations/](https://www.geeksforgeeks.org/space-optimization-using-bit-manipulations/) 在很多情況下，我們使用整數值作為數組中的索引來查看是否存在，我們可以使用位操作來優化此類問題中的空間。 讓我們以下面的問題為例。 給定兩個數字 a 和 b，請使用小于 O（| b – a |）的空間標記 a 和 b 之間 2 和 5 的倍數，并輸出每個倍數。 **注意**：我們必須將**的倍數標記為**，即將（鍵，值）對保存在內存中，以便每個鍵的值都為 1 或 0，表示 2 或 2 的倍數 5 或沒有。 **示例**：**** ``` Input : 2 10 Output : 2 4 5 6 8 10 Input: 60 95 Output: 60 62 64 65 66 68 70 72 74 75 76 78 80 82 84 85 86 88 90 92 94 95 ``` **方法 1（簡單）**： 將數組中的索引從 a 散列到 b，并將每個索引標記為 1 或 0。 空間復雜度：O（max（a，b） ）  **方法 2（勝于簡單）**： 通過將 a 轉換為第 0 個索引并將 b 轉換為第（b-a）個索引來節省內存。 空間復雜度：O（| b-a |）。  只需哈希| b – a | 數組的位置為 0 和 1。 ## C++ ```cpp // CPP program to mark numbers as multiple of 2 or 5 #include <bits/stdc++.h> using namespace std; // Driver code int main() { ????int a = 2, b = 10; ????int size = abs(b - a) + 1; ????int* array = new int[size]; ????// Iterate through a to b, If it is a multiple ????// of 2 or 5 Mark index in array as 1 ????for (int i = a; i <= b; i++) ????????if (i % 2 == 0 || i % 5 == 0) ????????????array[i - a] = 1; ????cout << "MULTIPLES of 2 and 5:\n"; ????for (int i = a; i <= b; i++) ????????if (array[i - a] == 1) ????????????cout << i << " "; ????return 0; } ``` ## Java ```java // Java program to mark numbers as? // multiple of 2 or 5 import java.lang.*; class GFG { ????// Driver code ????public static void main(String[] args) ????{ ????????int a = 2, b = 10; ????????int size = Math.abs(b - a) + 1; ????????int array[] = new int[size]; ????????// Iterate through a to b, If? ????????// it is a multiple of 2 or 5? ????????// Mark index in array as 1 ????????for (int i = a; i <= b; i++) ????????????if (i % 2 == 0 || i % 5 == 0) ????????????????array[i - a] = 1; ????????System.out.println("MULTIPLES of 2" ??????????????????????????????+ " and 5:"); ????????for (int i = a; i <= b; i++) ????????????if (array[i - a] == 1) ????????????????System.out.printf(i + " "); ????} } // This code is contributed by // Smitha Dinesh Semwal ``` ## Python 3 ``` # Python 3 program to mark numbers # as multiple of 2 or 5 import math # Driver code a = 2 b = 10 size = abs(b - a) + 1 array = [0] * size # Iterate through a to b,? # If it is a multiple of 2? # or 5 Mark index in array as 1 for i in range(a, b + 1): ????if (i % 2 == 0 or i % 5 == 0): ????????????array[i - a] = 1 print("MULTIPLES of 2 and 5:") for i in range(a, b + 1): ????if (array[i - a] == 1): ????????????print(i, end=" ") # This code is contributed by # Smitha Dinesh Semwal ``` ## C# ```cs // C# program to mark numbers as? // multiple of 2 or 5 using System; class GFG { ????// Driver code ????static public void Main () ????{ ????????int a = 2, b = 10; ????????int size = Math.Abs(b - a) + 1; ????????int[] array = new int[size]; ????????// Iterate through a to b, If? ????????// it is a multiple of 2 or 5? ????????// Mark index in array as 1 ????????for (int i = a; i <= b; i++) ????????????if (i % 2 == 0 || i % 5 == 0) ????????????????array[i - a] = 1; ????????Console.WriteLine("MULTIPLES of 2" + ??????????????????????????" and 5:"); ????????for (int i = a; i <= b; i++) ????????????if (array[i - a] == 1) ????????????????Console.Write(i + " "); ????} } // This code is contributed by Ajit. ``` ## PHP ```php <?php // PHP program to mark? // numbers as multiple? // of 2 or 5 // Driver Code $a = 2; $b = 10; $size = abs($b - $a) + 1; $array = array_fill(0, $size, 0); // Iterate through a to b,? // If it is a multiple of // 2 or 5 Mark index in // array as 1 for ($i = $a; $i <= $b; $i++) ????if ($i % 2 == 0 || $i % 5 == 0) ????????$array[$i - $a] = 1; echo "MULTIPLES of 2 and 5:\n"; for ($i = $a; $i <= $b; $i++) ????if ($array[$i - $a] == 1) ????????echo $i . " "; // This code is contributed by mits. ?> ``` **輸出**： ``` MULTIPLES of 2 and 5: 2 4 5 6 8 10 ``` **方法 3（使用位操作）**： 這是一個優化的空間，它使用位操作技術，該技術可以應用于在數組中映射二進制值的問題。 64 位編譯器中 int 變量的大小為 4 個字節。 1 個字節由內存中的 8 位位置表示。 因此，內存中的一個整數由 32 位位置（4 字節）表示，這 32 位位置可以使用，而不僅僅是一個索引來哈希二進制值。  ## C++ ``` // CPP code to for marking multiples #include <bits/stdc++.h> using namespace std; // index >> 5 corresponds to dividing index by 32 // index & 31 corresponds to modulo operation of? // index by 32 // Function to check value of bit position whether? // it is zero or one bool checkbit(int array[], int index) { ????return array[index >> 5] & (1 << (index & 31)); } // Sets value of bit for corresponding index void setbit(int array[], int index) { ????array[index >> 5] |= (1 << (index & 31)); } /* Driver program to test above functions*/ int main() { ????int a = 2, b = 10; ????int size = abs(b - a); ????// Size that will be used is actual_size/32 ????// ceil is used to initialize the array with ????// positive number ????size = ceil(size / 32); ????// Array is dynamically initialized as ????// we are calculating size at run time ????int* array = new int[size]; ????// Iterate through every index from a to b and ????// call setbit() if it is a multiple of 2 or 5 ????for (int i = a; i <= b; i++) ????????if (i % 2 == 0 || i % 5 == 0) ????????????setbit(array, i - a); ????cout << "MULTIPLES of 2 and 5:\n"; ????for (int i = a; i <= b; i++) ????????if (checkbit(array, i - a)) ????????????cout << i << " "; ????return 0; } ``` ## Java ```java // Java code to for marking multiples import java.io.*; import java.util.*; class GFG? { ????// index >> 5 corresponds to dividing index by 32? ????// index & 31 corresponds to modulo operation of? ????// index by 32? ????// Function to check value of bit position whether? ????// it is zero or one? ????static boolean checkbit(int array[], int index)? ????{? ????????????int val = array[index >> 5] & (1 << (index & 31)); ????????????if (val == 0) ????????????????return false; ????????????return true;? ????}? ????// Sets value of bit for corresponding index? ????static void setbit(int array[], int index)? ????{? ????????????array[index >> 5] |= (1 << (index & 31));? ????} ????// Driver code ????public static void main(String args[]) ????{ ????????????int a = 2, b = 10;? ????????????int size = Math.abs(b-a); ????????????// Size that will be used is actual_size/32? ????????????// ceil is used to initialize the array with? ????????????// positive number ????????????size = (int)Math.ceil((double)size / 32); ????????????// Array is dynamically initialized as? ????????????// we are calculating size at run time? ????????????int[] array = new int[size]; ????????????// Iterate through every index from a to b and? ????????????// call setbit() if it is a multiple of 2 or 5? ????????????for (int i = a; i <= b; i++)? ????????????????if (i % 2 == 0 || i % 5 == 0)? ????????????????????setbit(array, i - a); ????????????System.out.println("MULTIPLES of 2 and 5:"); ????????????for (int i = a; i <= b; i++)? ????????????????if (checkbit(array, i - a))? ????????????????????System.out.print(i + " ");? ????} } // This code is contributed by rachana soma ``` ## C# ``` // C# code to for marking multiples using System; class GFG? { ????// index >> 5 corresponds to dividing index by 32? ????// index & 31 corresponds to modulo operation of? ????// index by 32? ????// Function to check value of bit position?? ????// whether it is zero or one? ????static bool checkbit(int []array, int index)? ????{? ????????int val = array[index >> 5] &? ?????????????????(1 << (index & 31)); ????????if (val == 0) ????????????return false; ????????return true;? ????}? ????// Sets value of bit for corresponding index? ????static void setbit(int []array, int index)? ????{? ????????????array[index >> 5] |= (1 << (index & 31));? ????} ????// Driver code ????public static void Main(String []args) ????{ ????????int a = 2, b = 10;? ????????int size = Math.Abs(b-a); ????????// Size that will be used is actual_size/32? ????????// ceil is used to initialize the array with? ????????// positive number ????????size = (int)Math.Ceiling((double)size / 32); ????????// Array is dynamically initialized as? ????????// we are calculating size at run time? ????????int[] array = new int[size]; ????????// Iterate through every index from a to b and? ????????// call setbit() if it is a multiple of 2 or 5? ????????for (int i = a; i <= b; i++)? ????????????if (i % 2 == 0 || i % 5 == 0)? ????????????????setbit(array, i - a); ????????Console.WriteLine("MULTIPLES of 2 and 5:"); ????????for (int i = a; i <= b; i++)? ????????????if (checkbit(array, i - a))? ????????????????Console.Write(i + " ");? ????} } // This code is contributed by 29AjayKumar ``` **輸出**： ``` MULTIPLES of 2 and 5: 2 4 5 6 8 10 ``` * * * * * *