Simple knowledge of bit operation

Several points to remember in bit operation are:

• If you want to go to the last place, use num% 2
• To remove the last bit, use num = num / 2
• If it is judged that a number is the power of 2, use (n & - n) = = n, which will be described in detail below
• The XOR of two identical numbers is 0, the XOR value of all bits and 0 remains unchanged, and the XOR value of all bits and 1 is equivalent to negation
• Manual complement tips: start from the last bit, find the first 1, and then reverse all the bits in front of 1 to complete the complement!

231. Power of 2

Meaning:

Give you an integer n, please judge whether the integer is a power of 2. If yes, return true; Otherwise, false is returned.

If there is an integer x such that n == 2x, n is considered to be a power of 2.

Example 1:

Input: n = 1
 Output: true
 Explanation: 20 = 1

Example 2:

Input: n = 16
 Output: true
 Interpretation: 24 = 16

Example 3:

Input: n = 3
 Output: false

Problem solving ideas

ask	answer
How to judge whether a number is a power of 2?	Just judge the whole number, there is only one 1
How to judge that there is only one 1?	We only need to take the complement of the whole number first, then the original code is reversed + 1 And operation, if you get the original same number, it means it is a number, if not, it proves more than one

• for instance

  Example 1: the original code of 4 is 0000 0100 Then its complement is 1111 1100. At this time, the sum operation result is 0000 0100, which is equal to the original number

  Example 2: the original code of 5 is 0000 0101 Then its complement is 1111 1011. At this time, the sum operation result is 0000 0001, which is not equal to the original number

  You can cite other examples. If and only if there is only one 1, the result of and will be equal to the original number

code:

class Solution {
public:
    bool isPowerOfTwo(int n) {
	    if(n <= 0)
            return false;
        return (n & -n) == n;
    }
};

191. Number of bit 1

meaning of the title

Write a function. The input is an unsigned integer (in the form of binary string) and returns the number of digits with '1' in its binary expression (also known as Hamming Weight ).

Example 1:

Input: 0000000000000000000000001011
 Output: 3
 Explanation: there are three digits in the binary string 0000000000000000000000000000001011 '1'. 

Example 2:

Input: 000000000000000000000000000000000000000000000
 Output: 1
 Explanation: in the binary string 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 '1'. 

Example 3:

Input: 11111111111111111111111111111111101
 Output: 31
 Explanation: there are 31 bits in the input binary string 11111111111111111111111111111101 '1'. 

Problem solving ideas:

Just take out the last bit each time to judge whether it is 1 until n equals 0;

code:

class Solution {
public:
    int hammingWeight(uint32_t n) {
    int res = 0;
	while (n)
	{
		res += n % 2;
		n = n / 2;
	}
	return res;
    }
};

190. Reverse binary

Meaning:

Inverts the binary bits of a given 32-bit unsigned integer.

Example 1:

input: 00000010100101000001111010011100
 output: 00111001011110000010100101000000
 explain: The input binary string 000000 1010010100000111010011100 represents an unsigned integer 43261596,
     Therefore, 964176192 is returned, and its binary representation is 001110010111100000010100101000000.

Example 2:

Input: 11111111111111111111111111111111101
 Output: 10111111111111111111111111111111111
 Explanation: the input binary string 11111111111111111111101 represents an unsigned integer 4294967293,
     Therefore, 3221225471 is returned, and its binary representation is 10111111111111111111111111111.

Example 1:

Input: n = 00000010100101000001111010011100
 Output: 964176192 (00111001011110000010100101000000)
Explanation: the input binary string 000000 1010010100000111010011100 represents an unsigned integer 43261596,
     Therefore, 964176192 is returned, and its binary representation is 001110010111100000010100101000000.

Problem solving ideas:

To define a variable, you only need to shift the variable one bit to the left or the last bit of N, and then n to the right Until n equals 0 Judge the number of moves, and then add 32 moves

code:

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
    if(n == 0)
        return 0;
	int ans = 0;	
	int num = 0;	//Record how many moves
	while (n)
	{
		ans = ans << 1 | (n % 2);
		n = n / 2;
		num++;
	}
	ans = ans << (32 - num);	//Need to move 32 times
	return ans;
    }
};

136. Figures that appear only once

Meaning:

Given a non empty array of integers, each element appears twice except that one element appears only once. Find the element that appears only once.

explain:

Your algorithm should have linear time complexity. Can you do it without using extra space?

Example 1:

input: [2,2,1]
output: 1

Example 2:

input: [4,1,2,1,2]
output: 4

Problem solving ideas:

Go out all the numbers, XOR them one by one, and the same ones will be eliminated. Finally, only one different one will be left

code

class Solution {
public:
    int singleNumber(vector<int>& nums) {
	int res = 0;
	for (const int i : nums)
	{
		res ^= i;
	}
	return res;
    }
};

Summary:

Bit operation can be effective in some problems, so you need to master some simple knowledge