在很多情况下，我们使用整数值作为数组中的索引来查看是否存在，我们可以在此类问题中使用位操作来优化空间。 让我们以下面的问题为例。 给定两个数字，比如a和b，使用小于O（|b–a |）的空间标记a和b之间2和5的倍数，并输出每个倍数。
null
注： 我们必须 做记号 倍数，即在内存中保存（键、值）对，使每个键的值为1或0，分别表示为2或5的倍数，或不表示为2或5的倍数。
例如：
Input : 2 10Output : 2 4 5 6 8 10Input: 60 95Output: 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（最大（a，b））
![图片[1]-使用位空间优化操作-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_Array1.png)
方法2（比简单好）： 通过将a转换为第0个索引并将b转换为第（b-a）个索引来节省内存。 空间复杂度：O（|b-a |）。
![图片[2]-使用位空间优化操作-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_Array_updated.png)
简单地将数组的| b–a |位置散列为0和1。
C++
// C++ 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:" ; for ( int i = a; i <= b; i++) if (array[i - a] == 1) cout << i << " " ; return 0; } |
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 |
Python3
# Python3 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#
// 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 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:" ; for ( $i = $a ; $i <= $b ; $i ++) if ( $array [ $i - $a ] == 1) echo $i . " " ; // This code is contributed by mits. ?> |
Javascript
<script> // JavaScript program to mark numbers as // multiple of 2 or 5 // Driver code let a = 2, b = 10; let size = Math.abs(b - a) + 1; let array = []; // Iterate through a to b, If // it is a multiple of 2 or 5 // Mark index in array as 1 for (let i = a; i <= b; i++) if (i % 2 == 0 || i % 5 == 0) array[i - a] = 1; document.write( "MULTIPLES of 2" + " and 5:" + "<br/>" ); for (let i = a; i <= b; i++) if (array[i - a] == 1) document.write(i + " " ); // This code is contributed by code_hunt </script> |
输出：
MULTIPLES of 2 and 5:2 4 5 6 8 10
方法3（使用位操作） : 这是一个空间优化，它使用位操作技术，可以应用于在数组中映射二进制值的问题。 64位编译器中int变量的大小为4字节。1字节由内存中的8位位置表示。因此，内存中的整数由32位位置（4字节）表示。可以使用这些32位位置，而不仅仅是一个索引来散列二进制值。
![图片[3]-使用位空间优化操作-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_Array_32bit.png)
C++
// C++ 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:" ; for ( int i = a; i <= b; i++) if (checkbit(array, i - a)) cout << i << " " ; return 0; } |
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 |
Python3
# Python3 code to for marking multiples import math # 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 def checkbit( array, index): return array[index >> 5 ] & ( 1 << (index & 31 )) # Sets value of bit for corresponding index def setbit( array, index): array[index >> 5 ] | = ( 1 << (index & 31 )) # Driver code a = 2 b = 10 size = abs (b - a) # Size that will be used is actual_size/32 # ceil is used to initialize the array with # positive number size = math.ceil(size / 32 ) # Array is dynamically initialized as # we are calculating size at run time array = [ 0 for i in range (size)] # Iterate through every index from a to b and # call setbit() if it is a multiple of 2 or 5 for i in range (a, b + 1 ): if (i % 2 = = 0 or i % 5 = = 0 ): setbit(array, i - a) print ( "MULTIPLES of 2 and 5:" ) for i in range (a, b + 1 ): if (checkbit(array, i - a)): print (i, end = " " ) # This code is contributed by rohitsingh07052 |
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 |
Javascript
<script> // JavaScript code to for marking multiples // 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 function checkbit(array, index) { return array[index >> 5] & (1 << (index & 31)); } // Sets value of bit for corresponding index function setbit(array, index) { array[index >> 5] |= (1 << (index & 31)); } // Driver code let a = 2, b = 10; let 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 = Math.ceil(size / 32); // Array is dynamically initialized as // we are calculating size at run time let array = new Array(size); // Iterate through every index from a to b and // call setbit() if it is a multiple of 2 or 5 for (let i = a; i <= b; i++) if (i % 2 == 0 || i % 5 == 0) setbit(array, i - a); document.write( "MULTIPLES of 2 and 5:<br>" ); for (let i = a; i <= b; i++) if (checkbit(array, i - a)) document.write(i + " " ); // This code is contributed by Surbhi Tyagi. </script> |
输出：
MULTIPLES of 2 and 5:2 4 5 6 8 10
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
