[leetcode] skillfully use bit operation

introduction

During programming , Bit operation is one of the commonly used operations , Direct operation on binary bits makes bit operation more efficient than general operation instructions . Clever bit operation , It can solve some problems that are difficult to be solved by other operation symbols or more complex to be solved by other methods .

01

In binary digits “1” The number of

int get_1_Count(int n)
{
  int count = 0;
  while (n)
  {
    n = n&(n-1);
    count++;
  }
  return count;
}

Copy

02

Add two numbers

Don't use “+” Operator to add two input parameters , Bit operation can also be done ！ That is XOR ！

• a^b： Sum without carry after bitwise addition ;
• a&b： Where carry can be generated ;
• (a&b)<<1： Get the carry value .

int get_sum_by_bitAdd(int a, int b)
{
  int aTemp = 0, bTemp = 0;
  while (b != 0) {
    aTemp = a ^ b;
    bTemp = (a & b) << 1;
    a = aTemp;
    b = bTemp;
  }
  return a;
}

Copy

03

Subtract two numbers

First of all, we need to know an operation law of bit operation ：~n=-(n+1), such as ：~3=-4

Subtract two numbers , Such as a-b It can be converted into addition a+(-b), According to the above operation rules -b=~(b-1), therefore a-b=a+(-b)=a+[~(b-1)], Use the bit operation in the previous section to add two numbers .

int sub_by_bit(int a, int b)
{
  int _b = ~(b - 1);
  return get_sum_by_bitAdd(a, _b);
}

Copy

04

Exchange two numbers

Exchange two numbers without creating temporary variables , It is also XOR ！

• The first XOR ： Find two variables bit Different bits , Save as a;
• Second XOR ： Take the opposite b Li and a Different bit position , take b Become the original a;
• Third XOR ： Take the opposite a Li and b Different bit position , take a Become the original b.

void swap_by_bitXor(int a, int b)
{
  printf("%d  %d \n", a, b);
  a = a^b;
  b = a^b;
  a = a^b;
  printf("%d  %d \n", a, b);
}

Copy

05

Find the one that only appears once in the array 1 Number （ The rest of the numbers appear twice ）

LeetCode The first 136 topic ： Given an array of non-empty integers , Except that an element only appears once , Each of the other elements occurs twice . Find the element that only appears once .

//  The basic method ：
// 1. a^b^c = a^c^b
// 2.   a^a = 0
// 3.   a^0 = a
 
int find_Once_by_bitXor(int[] arr, int Length) {
    int result = 0;
    for (int i = 0; i < Length; i++) {
        result ^= arr[i];
    }
 
    return result;
}

Copy

similarly ,LeetCode The first 389 topic ： Given two strings s and t, They contain only lowercase letters . character string t By string s Random rearrangement , Then add a letter at random . Please find out in t The letters added in . Example ：

Input ：s = "abcd" t = "abcde" Output ：e explain ：'e' It's the letter that was added .

The idea of solving the problem is consistent with the above , Exclusive or , The end result is the added value ：

char findTheDifference(string s, string t) {
        char ch = 0;
        
        for(int i=0;i<s.size();i++){
            ch^=s[i];
        }
        for(int i=0;i<t.size();i++){
            ch^=t[i];
        }   
        return ch;
    }

Copy

06

Find the one that only appears once in the array 1 Number （ The rest of the figures appear 3 Time ）

LeetCode The first 137 topic ： Given an array of non-empty integers , Except that an element only appears once , Each of the other elements appears three times . Find the element that only appears once

In this case , be-all bit There are only two kinds of situations ,3*n,3*n + 1, there n Is any integer , Suppose you traverse the array , In fact, there will be an intermediate state 3*n + 2 There is , For other numbers besides this number , The process is probably 3*n + 1 -> 3*n + 2 -> 3*n, All we need to record is 3*n + 1 and 3*n + 2 The situation of , because 3*n It is actually an initial state （n=0）, Whether to record or not has nothing to do with the answer we finally want to return , And record 3*n + 2 To recover some bit from 3*n + 2 To 3*n.

int singleNumber(int[] nums, int Length) {
    int one = 0, two = 0;
    for (int i = 0; i < Length; ++i) {
        //  Find the current  3n + 1
        one = (nums[i] ^ one) & (~two);
        //  Find the current  3n + 2
        two = (nums[i] ^ two) & (~one);
    }
 
    return one;
}

Copy

You can do a simple test about the above code , Because it is to find the number that only appears once in the array , So it has nothing to do with the order of numbers , Don't put Jungle Let's take the simplest example nums[4] = {3,3,3,1} , The process is as follows ：