Excellent algorithms use a lot of place operations, and bit operations are rarely used in the work, with an example, we have a look at its advantages and principles, by the way mark a wave of common bit operations.

Last article “interesting binary” we talked about some basic knowledge of binary, but did not talk about the operation in place, some students shout not enough, that this article mainly explains the use of the next bit operation, or from an example, I hope to inspire you. Remember the following example application please mark, help a lot.

A, sudoku

Sudoku is a good example to introduce bit operation. There is a big difference in efficiency between using bit operation and not using it. Let’s start with sudoku requirements:

1. The current number contains 1 to 9 and is not repeated

2. The number in the current column contains 1 to 9 and does not repeat

3. The numbers in the house where the current number is located (i.e. the big grid of 3×3) all contain 1-9 and are not repeated (the house is one in each thick line as shown below).

,

1. General algorithm

If we use the conventional method, every time we fill in a number, we need to check whether there are repeated numbers in the current row, column and other positions in the palace. In extreme cases, we need to cycle 27 (3*9) times to check. Let’s take a look at the check under the conventional algorithm

Int sp (int sp) {// check(int sp) {// return 1 intfg= 0;if(!fg) fg= check1(sp, startH[sp], addH) ; // Check if there are the same numbers in the same columnif(!fg) fg= check1(sp, startV[sp], addV) ; // Check if the peer has the same numberif(!fg) fg= check1(sp, startB[sp], addB) ; // Check if there are the same numbers as the nine squaresreturn(fg); } int check1(int sp, int start, int *addnum)fg= 0, i, sp1 ; / / of all evilforcyclefor(i=0; i<9; i++) {
	      sp1= start+ addnum[i] ;
	      if(sp! =sp1 && sudoku[sp]==sudoku[sp1])fg++ ;
	   }
	   return(fg); }Copy the code

Is this efficiency scary? Every time you fill in one, you need to check27 times. Is there an algorithm for checking once? Of course we do. We do it in bits, all at once. Let’s look at the idea of the next bit operation:

2. Bit operation

As shown in the figure above, a single row (or column or house) of data has a total of 9 digits from 1 to 9, which are collectively referred to as nine house numbers. If we use binary, with nine digits as the bit coordinates of binary data, using nine bits of binary can be corresponding to one and one, there is data in the bit, identified as 1, no data identified as 0, so a positive number can solve a row of nine data states, without the need to save an array.

For example, if you look at the dark red part of the figure, the current nine houses of data already have 1 and 3, then the first and third digits from the right of the binary are identified as 1, a number 5 can store the current row (or column, house) array state, if the number is 511, it indicates that all the nine houses of digits are used up, as shown in the first row.

Check To check whether a number is already in use, you can take a bit operation to get the k-th right bit of the binary to check whether it is 1. If 1, the specified number is already in use. Let’s look at the specific check algorithm:

// sp is the current position index, indexV row index, indexH column index, Int check(int sp,int indexV,int indexH,int indexB) {int sp,int indexV,int indexH,int indexB Return 1 if have used int status = statusV [indexV] | statusH [indexH] | statusB [indexB]; // All 9 numbers are usedif (status>=STATUS_MAX_VALUE)
		{
			return1; } int number=sudoku[sp]; // Select the KTH bit from the right, if 1 indicates that the value already existsreturn status>>(number-1)&1;
	}Copy the code

Int markStatus(int indexV,int indexH,int indexB,int number){if (number<1)
		{
			return0; } / / put the right number of the first k (counting from 1) into 1 statusV [indexV] | = (1 < < (number 1)); statusH[indexH]|=(1<<(number-1)); statusB[indexB]|=(1<<(number-1)); }Copy the code

How do we get the number that can be filled in at the current position using the following legend position

You can see that two bits solves the problem of checking the available numbers, whereas the conventional algorithm required 27 lookups to get them. Of course, this algorithm can also be optimized, such as the use of heuristic DFS, search available numbers, faster, you can click here.

Conventional algorithm and bit operation algorithm C language code, I have uploaded the code cloud, want to know click the following link, go to view. (Regular algorithm Google)

Address: general algorithm Sudoku, bit version Sudoku

Second, the basic

1. Bit operators

Note:

1. Bitwise operations apply only to integers, not to floats and doubles.

2, in addition to the logical right shift symbol is not the same as various languages, such as Java is >>>.

3. Bitwise operators have a lower precedence, so use parentheses to ensure the order of operations. For example, 1& I +1 executes I +1 before &.

3. Application examples

Great application example, you can mark it, convenient to use in the future.

1. Mixture

Bit operation instance

2. Switch two numbers

int swap(int a, int b)  
{  
    if (a != b)  
    {  
        a ^= b;  
        b ^= a;  
        a ^= b;  
    }  
}  Copy the code

3. Find the absolute value

int abs(int a)  
{  
    int i = a >> 31;  
    return ((a ^ i) - i);  
}  Copy the code

Binary search 32-bit integer leading 0 number

int nlz(unsigned x)
{
   int n;

   if (x == 0) return(32);
   n = 1;
   if((x >> 16) == 0) {n = n +16; x = x <<16; }if((x >> 24) == 0) {n = n + 8; x = x << 8; }if((x >> 28) == 0) {n = n + 4; x = x << 4; }if((x >> 30) == 0) {n = n + 2; x = x << 2; } n = n - (x >> 31);return n;
}Copy the code

5, binary reverse order

int reverse_order(int n){

  n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1);
  n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2);
  n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4);
  n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8);
  n = ((n & 0xFFFF0000) >> 16) | ((n & 0x0000FFFF) << 16);

  return n;
}Copy the code

6. The number of ones in binary

unsigned int BitCount_e(unsigned int value) { unsigned int count = 0; // 11 01 00 10 = 01 01 00 00 00 + 10 00 00 00 10, // Value = 11 01 00 10, high_v = 01 01 00 00, low_v = 10 00 00 10 // then value = high_v + low_v, High_v_1 = high_v >> 1 = high_v / 2 / value = high_v_1 + high_v_1 + low_v Value = value & 0x55555555 + (value >> 1) &0x55555555; value = value - ((value >> 1) & 0x55555555); Value = (value & 0x33333333) + ((value >> 2) & 0x33333333); value = (value & 0x0f0f0f0f) + ((value >> 4) & 0x0f0f0f0f); value = (value & 0x00ff00ff) + ((value >> 4) & 0x00ff00ff); value = (value & 0x0000ffff) + ((value >> 8) & 0x0000ffff);returnvalue; //value = (value & 0x55555555) + (value >> 1) &0x55555555; //value = (value & 0x33333333) + ((value >> 2) & 0x33333333); //value = (value & 0x0f0f0f0f) + ((value >> 4) & 0x0f0f0f0f); //value = value + (value >> 8); //value = value + (value >> 16); //return (value & 0x0000003f);
    }Copy the code

———————–end————————-

Big size, pay attention to personal growth and technical learning, hope to use their own little change, can give you some inspiration

Scan for more.