Bit operation topic

1. Bitmap solves the occurrence of numbers in a certain range , Save a lot of time

• Topic analysis
     Use hash method to solve , The general idea is to apply for a hash table , Put the hash value of each number in the file after the hash function into the corresponding hash grid ( Add one to the corresponding position value of the hash table ); After traversing all the numbers in the file , Observe Hashtable , The elements in the hash table are 0 The number corresponding to the position of is the number that does not appear ;
     But in that case , You need to apply for a length of 2³² Hash table for , Each position is an unsigned integer type uint(4 Bytes ,32 position , The scope is 0 ~ 2³²-1, It can meet the requirement that all numbers in the file are the same ); This limits memory 10M, It must not be enough ; Let alone limit memory 10kB;

   If memory is limited 3KB, that 3KB=3000byte,3000/4 = 750 Unsigned integers ; So the application length is 512 Hash table for ; take 0 ~ 2³² The data is divided into 512 Share , Then traverse the data in the file , Add the corresponding hash table position element 1; When the number in the file is traversed , Observe the size of each element in the hash table , Find out what has not been achieved 2³² / 512 The location of , This explanation 512 Of the data , This part of the data is missing , The missing data we are looking for must be in this part ; Then iterate over the file elements again , Figures not in this section are ignored , In this part of the figure press the new 512 Block principle storage ; Proceed in sequence , You can go to 3KB In memory ;

2. Bit operation to find the maximum value

The bit operation compares the maximum of two numbers

• Ideas 1
• code

int flip(int n)
{
    
	return n ^ 1;
}


int sign(int n)
{
    
	return flip((n >> 31) & 1);
}

int get_max1(int a, int b)
{
    
	int c = a - b;
	int scA = sign(c);//a-b For non negative ,scA=1;a-b Negative ,scA=0
	int scB = flip(scA);// a - b For non negative ,scB = 0; a - b Negative ,scB = 1
	return a * scA + b * scB;
}

Ideas 1 problem : When a-b When it overflows , The result is not right

• Ideas 2
• code2

int get_max2(int a, int b)
{
    
	int c = a - b;
	int sa = sign(a);//a For non negative ,sa = 1;
	int sb = sign(b);//b For non negative ,sa = 1
	int sc = sign(c);
	int difSab = sa ^ sb; //a and b The symbols are different ,difSab =1;
	int samSab = flip(difSab);//a and b The symbols are the same ,samSab =1;
	int returnA = difSab * sa + samSab * sc;//a,b Same symbols and a>b  perhaps 
										    //a,b Symbols are different and a>0 Back when A
	int returnB = flip(returnA);
	return a * returnA + b * returnB;

}

doubt ： How to determine a,b The symbols are different ,a>0 When ,sign by 1

3. Determine whether an integer is 2 The power of

• Ideas 1
  If an array is judged to be 2 Of n The next power ; Then move the number to the right n position , Determine whether the end of this time is bit 1, If it is 1, It means 2 Of n The next power

• Ideas 2
  The number if bit 2 The power of , Then there is only one binary form 1;
  If x&(x-1)=0, that x Namely 2 The power of ;

• code

bool is4pow(int n)
{
    
	return (n&(n-1))==0;
}

4. Determine whether an integer is 4 The power of

1. Judge X Is it 2 The power of , That is, there is only one binary form 1
   2） If X by 2 The power of , Further judgment is needed X Is it 4 The power of
   If X by 4 The power of , In binary form , It could be in the 0,2,4,6,8 There is only one even number 1, There is no one on the odd bit 1;X&（0101010101…0101）!=0, explain X by 4 The power of

• code

bool is4pow(int n)
{
    
	return (n&(n-1))==0 & (n&0x5555)!=0;
}

Use bit operation to add, subtract, multiply and divide two numbers

https://www.bilibili.com/video/BV13g41157hK?p=16

An hour 40 branch