Force deduction operation

x ^ 0s = x
x ^ x = 0
N & (n - 1) the lowest bit in the bit level representation of N can be removed. For example, for the binary representation 11110100, subtract 1 to obtain 11110011, and the two numbers are bitwise combined to obtain 11110000. N & (- n) can get the lowest bit in the bit level representation of N. for example, for the binary representation 11110100, take negative to get 00001100, and the two numbers get 00000100 by bitwise sum.
Given two decimal numbers, find their binary Hamming distance.
Perform bitwise exclusive or operation on two numbers, and count the number of 1s.

int hammingDistance(int x, int y) {
int diff = x ^ y, ans = 0;
while (diff) {
ans += diff & 1;
diff >>= 1;
}
return ans;
}

Given a decimal integer, output its flip result in binary.

uint32_t reverseBits(uint32_t n) {
uint32_t ans = 0;
for (int i = 0; i < 32; ++i) {
ans <<= 1;
ans += n & 1;
n >>= 1;
}
return ans;
}

Given an integer array, in this array, only one number appears once several times, and the other numbers appear twice, find the number that appears only once.
We can use the characteristics of X Λ x = 0 and X Λ 0 = x to XOR all the numbers in the array. The result of bitwise XOR of all numbers appearing twice is 0. 0 and the number appearing once can get the number itself.

int singleNumber(vector<int>& nums) {
int ans = 0;
for (const int & num: nums) {
ans ^= num;
}
return ans;
}

Given an integer, judge whether it is to the power of 4.
First, we consider whether a number is to the (integer) power of 2: if a number n is to the integer power of 2, its binary must be in the form of 0... 010... 0; Considering that the binary of n − 1 is 0... 001... 1, the result of bitwise sum of these two numbers must be 0. So if n & (n - 1) is 0, then the number is to the power of 2. If the number is also to the power of 4, the position of 1 in the binary representation must be odd. We can do bitwise sum of N and binary 10101... 101 (i.e. 1431655765 in decimal system). If the result is not 0, it means that the number is to the power of 4.
The power of 4 must be 2.
The power of 4 is the same as the power of 2, and only one 1 will appear. However, the 1 of 4 always appears in odd digits.
0x5 = 0101b can be used to check 1 on odd digits.
So,

//0x5 = 0101b
bool isPowerOfFour(int num) {
    if (num < 0 || num & (num-1)){//check(is or not) a power of 2.
        return false;
    }
    //Is the nth power of 2 (with a 1) and appears in odd digits
    return num & 0x55555555;//check 1 on odd bits
}

Given multiple letter strings, find the maximum value of the length product of any two letter strings, and the two letter strings cannot contain the same letter.

Input: ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4

In this example, one of the best choices is "ab" and "cd".
How to quickly determine whether two letter strings contain duplicate numbers? A binary number with a length of 26 can be established for each letter string, and each position indicates whether the letter exists. If two letter strings contain duplicate numbers, the bitwise sum of their binary representation is not 0. At the same time, we can establish a hash table to store the mapping relationship between the letter string (at the position of the array) and the binary number, which is convenient for search and call.

int maxProduct(vector<string>& words) {
unordered_map<int, int> hash;
int ans = 0;
for (const string & word : words) {
int mask = 0, size = word.size();
for (const char & c : word) {
//Use | it's just appeared
mask |= 1 << (c - 'a');
}
//The same type of letters corresponds to the maximum length
hash[mask] = max(hash[mask], size);
for (const auto& [h_mask, h_len]: hash) {
if (!(mask & h_mask)) {
//Current and saved bit by bit and when it is 0, there is no duplicate symbol
ans = max(ans, size * h_len);//Take the maximum product
}
}
}
return ans;
}

Given a nonnegative integer n, find how many 1s there are in the binary expression of all numbers from 0 to n.

Input: 5
Output: [0,1,1,2,1,2]

This problem can be solved quickly by dynamic programming and bit operation. Define an array dp, where dp[i] represents the number of 1 contained in the binary of the number I. For the ith digit, if the last bit of its binary is 1, the number of digits containing 1 is dp[i-1] + 1; If the last bit of its binary is 0, the number of 1 is the same as its arithmetic right shift result, that is, dp[i > > 1].

vector<int> countBits(int num) {
vector<int> dp(num+1, 0);
for (int i = 1; i <= num; ++i)
dp[i] = i & 1? dp[i-1] + 1: dp[i>>1];
// Equivalent to DP [i] = DP [I & (i-1)] + 1;
return dp;
}

Keywords: Algorithm leetcode LeedCode

Added by doug007 on Wed, 17 Nov 2021 17:28:48 +0200