An operation

Basic bit operations include and or as well as xOR, left shift, and unsigned right shift.

The loop n&n-1 computes how many 1’s there are in n

If n ^ 1 is 1, you can tell if the lowest order of n is 1

N to the n is 0

N >> 1 is the same thing as dividing by 2

N << 1 wants to multiply phi by 2

Keeping these common techniques in mind can be helpful in bit operations, but most require a combination of these techniques.

461. Hamming distance

Topic describes

The Hamming distance between two integers refers to the number of different positions of the two numbers corresponding to the binary bits.

Given two integers x and y, calculate the Hamming distance between them.

Example 1

Input: 1, 4

output: 2

Explanation:

1 (0 0 0 1) 4 (0 1 0 0 0) the arrows above ↑ indicate the different positions of the corresponding binary bitsCopy the code

thinking

1 can be either one or two numbers first, so you get how many ones there are, and then you calculate how many ones there are in that number

Reference Implementation 1

To achieve 1

/ * * *@param {number} x
 * @param {number} y
 * @return {number}* /

export default (x, y) => {
  let z = x ^ y;
  let res = 0;
  while(z ! =0) {
    res++;
    z &= z - 1;
  }
  return res;
};
Copy the code

190. Reverse binary bits

Topic describes

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

Example 1

Input: 00000010100101000001111010011100

output: 00111001011110000010100101000000

Explanation: Input binary string of 00000010100101000001111010011100 said unsigned integer 43261596, so back to 964176192, the binary representation of 00111001011110000010100101000000.

Example 2

Input: 11111111111111111111111111111101

output: 10111111111111111111111111111111

Explanation: Input said unsigned integer binary string of 11111111111111111111111111111101 to 4294967293. Therefore returns the binary representation of 3221225471 to 10111111111111111111111111111111.

thinking

1 although this is an easy problem, it still feels hard to think of. After a look, we can set a result res, so that res has a sign to move to the left and n has a sign to move to the right

Finally, because we want to get unsigned, we have to move the res unsigned 0 bits to the right

Reference Implementation 1

To achieve 1

/ * * *@param {number} n - a positive integer
 * @return {number} - a positive integer
 */
// Submissions online in the linked node.
// Memory Usage: 40.2 MB, less than 76.19% of JavaScript online submissions for Reverse Bits.
export default (n) => {
  if (n === 0) return 0;
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result <<= 1;
    result |= n & 1;
    n >>= 1;
  }
  return result >>> 0;
};

Copy the code

136 a number that occurs only once

Topic describes

Given an array of integers in which only one number occurs once and the rest occur twice, find the number that occurs only once.

Example 1

Input: [4,1,2,1,2]

output: 4

Example 2

Input: nums = [4,1,2,1,2]

output: 4

thinking

1 is an obvious use of xor, because the xor of two identical numbers would be 0

Reference Implementation 1

To achieve 1

/ * * *@param {number[]} nums
 * @return {number}* /
// Submissions online in the linked node.
// Memory Usage: 40.3 MB, less than 87.12% of JavaScript online submissions for Single Number.
export default (nums) => {
  let res = nums[0];
  for (let i = 1; i < nums.length; i++) {
    res ^= nums[i];
  }
  return res;
};

Copy the code

268. Missing figures

Topic describes

Given an array nums containing n of [0, n], find the number in the range [0, n] that does not appear in the array.

Advancements: Can you solve this problem with linear time complexity using only an extra constant space algorithm?

Example 1

Input: (3, 1)

Description: n = 3, because there are three numbers, so all the numbers are in the range [0,3]. 2 is the missing number because it does not appear in NUMS.

Example 2

Input: nums = [0, 1]

output: 2

Explanation: n = 2, because there are two numbers, so all the numbers are in the range [0,2]. 2 is the missing number because it does not appear in NUMS.

Example 3

Input: nums = [9,6,4,2,3,5,7,0,1]

output: 2

Explanation: n = 9, because there are nine numbers, so all the numbers are in the range [0,9]. 8 is the missing number because it does not appear in NUMs.

thinking

1 if you want to use bits, because you already know that n^n === 0, try to use xor. But the first thing I wanted to do was sort it

2 and then you look at it, and you can do it with I, because n to the 0 is equal to === n and n to the n is equal to === 0

Reference Implementation 1

Reference Implementation 2

To achieve 1

/ * * *@param {number[]} nums
 * @return {number}* /

// submissions online in the linked node.
// Memory Usage: 100 MB, less than 100 MB of JavaScript online submissions for Missing Number.
export default (nums) => {
  const len = nums.length;
  nums.sort((a, b) = > a - b);
  let res = 0;
  for (let i = 0; i < nums.length; i++) {
    if (res === nums[i]) {
      res++;
    } else {
      if(res ^ (nums[i] ! =0)) {
        returnres; }}}return res;
};

Copy the code

The 2

/ * * *@param {number[]} nums
 * @return {number}* /

// submissions online in the linked node.
// Memory Usage: 41.4 MB, less than 28.25% of JavaScript online submissions for Missing Number

export default (nums) => {
  let res = nums.length;
  for (let i = 0; i < nums.length; i++) {
    res ^= i;
    res ^= nums[i];
  }
  return res;
};

Copy the code

260. The number III that occurs only once

Topic describes

Given an integer array nums, exactly two elements appear only once, and all the rest appear twice. Find the two elements that appear only once.

Example 1

Input: [1,2,1,3,2,5]

Output: (3, 5)

thinking

1 use bit operations here, really hard to think about, even see the results are still not well understood, because just beginning to n ^ n = = = 0, so think twice by traversal respectively the number of two different, but not found, because the two different Numbers may be adjacent together, later found out that the test cases.

Then I looked at the solution, and it was really hard to think of

If a and b are two different numbers in the array then a to the b is definitely not equal to 0, because if it’s equal to 0, then a is equal to, if a to the b is not equal to 0, So there has to be one bit in the binary representation so let’s say that m is equal to a to the b to the other value in the array, then we can get the lowest value of 1 by m & ~(m-1) so the array has to be divided into two parts, one is 1, one is 0, Otherwise you can’t get xor to come out and this is equal to one so this is all one and then the last xor to come out and this is all zero and this is another result

Reference Implementation 1

To achieve 1

/ * * *@param {number[]} nums
 * @return {number[]}* /

// Submissions: 80 ms, faster than 92.98% of JavaScript online submissions for Single Number III.
// Memory Usage: 80 MB, less than 87.72% of JavaScript online submissions for Single Number III.
export default (nums) => {
  let res = [0.0];
  let sum = 0;
  for (let i = 0; i < nums.length; i++) {
    sum ^= nums[i];
  }

  sum = sum & ~(sum - 1);

  for (let i = 0; i < nums.length; i++) {
    if ((nums[i] & sum) === 0) {
      res[0] ^= nums[i];
    } else {
      res[1] ^= nums[i]; }}return res;
};

Copy the code

Time complexity O (n), space complexity O (1)

342. A power of 4

Topic describes

Given an integer, write a function to determine whether it is a power of 4. If so, return true; Otherwise, return false.

The integer n is a power of 4. There is an integer x such that n == 4x

Example 1

Input: n = 16

output: true

Example 2

Input: n = 16

output: false

thinking

So one here is if it’s 4 squared, three things have to happen

// 1 n > 0 // 2 n is 2 squared, that is, n &n -1 // 3 where all 1's are in odd digitsCopy the code

Reference Implementation 1

To achieve 1

/ * * *@param {number} n
 * @return {boolean}* /
// Submissions online in the linked node.
// Memory Usage: 40 MB, less than 50 MB of JavaScript online submissions for Power of Four.
export default (n) => {
  // If it is 4 squared, three conditions must be met
  // 1 n > 0
  // 2 n is 2 squared which is n ^ n-1
  // all 1's in 3 n are in odd numbers

  return n > 0 && (n & (n - 1= = =))0 && (n & 0b1010101010101010101010101010101) > 0;
};

Copy the code

318. Maximum word length product

Topic describes

Given a string array of words, find the maximum length(word[I]) * length(word[j]) that contains no common letters. You can think of each word as containing only lowercase letters. If no such two words exist, return 0. br/>

Example 1

Input: [“abcw”,”baz”,”foo”,”bar”,”xtfn”,”abcdef”]

output: 16

Explanation: These two words are “abCW” and “XTFN”.

Example 2

Input: [“a”,”ab”,”abc”,”d”,”cd”,”bcd”,”abcd”]

output: 4

Explanation: These two words are “ab” and “CD”.

Example 3

Input: [“a”,”aa”,”aaa”,”aaaa”]

output: 0

Explanation: There are no such two words.

thinking

If you want to make sure that there are no identical characters in two strings, you can use an array of length 26. If the first digit is 1, then the string “A” exists.

If two arrays representing strings are used and are equal to 0, the two strings do not contain the same characters

Reference Implementation 1

To achieve 1

/ * * *@param {string[]} words
 * @return {number}* /
Lengths of each node in the linked JavaScript online link.
// Memory Usage: 0.75 MB, less than 85.96 percent of JavaScript online submissions for Maximum Product of Word Lengths.
export default (words) => {
  if (words.length < 1) return 0;
  const len = words.length;
  const value = new Array(len).fill(0);
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < words[i].length; j++) {
      If the first digit of the array is 1, then a exists
      value[i] |= 1 << (words[i].charCodeAt(j) - 97); }}let maxProduct = 0;
  for (let i = 0; i < len; i++)
    for (let j = i + 1; j < len; j++) {
      if ((value[i] & value[j]) === 0 && words[i].length * words[j].length > maxProduct)
        maxProduct = words[i].length * words[j].length;
    }
  return maxProduct;
};


Copy the code

338. Bit count

Topic describes

Given a non-negative integer num. For each number I in the range 0 ≤ I ≤ num, count the number of 1s in its binary number and return them as an array. br/>

Example 1

Input: 2

Output:,1,1 [0]

Example 2

Input: 5

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

Advanced:

1 It is very easy to give a solution with time complexity O(n * sizeof(integer)). But can you do that in one scan in linear time O(n)?

2 requires the spatial complexity of the algorithm to be O(n)

Can you improve the solution further? Requires that you do this without using any built-in functions (such as __builtin_popcount in C++) in C++ or any other language.

thinking

1 O(n * sizeof(integer))

Dp [I] is the number of digits I have, so it is easy to think that if the first digit of I is 0, dp[I] = dp[I >>1], if the first digit of I is 1, The dp [I] = dp [I > > 1)

Reference Implementation 1

Reference Implementation 2

To achieve 1

/ * * *@param {number} num
 * @return {number[]}* /

// submissions online in the linked node.
// Memory Usage: 100 MB, less than 100 MB of JavaScript online submissions for Counting Bits.

export default (num) => {
  let res = [0];
  for (let i = 1; i <= num; i++) {
    let bits = 0;
    while(i ! = =0) {
      bits++;
      i &= i - 1;
    }
    res.push(bits);
  }
  return res;
};

Copy the code

The 2

/ * * *@param {number} num
 * @return {number[]}* /

// submissions online in the linked node.
// Memory Usage: 100 MB, less than 100 MB of JavaScript online submissions for Counting Bits.
// dp[I] = dp[I >>1] // dp[I] = dp[I >>1]
export default (num) => {
  const dp = [];
  dp[0] = 0;
  if (num === 0) {
    return dp;
  }
  dp[1] = 1;
  if (num === 1) {
    return dp;
  }
  for (let i = 2; i <= num; i++) {
    dp[i] = dp[i >> 1] + (i & 1);
  }
  return dp;
};

Copy the code

693. Alternate binary numbers

Topic describes

Given a positive integer, check whether its binary representation always alternates zeros and ones: in other words, the two adjacent digits in the binary representation are never the same.

Example 1

Input: 5

The binary representation of 5 is: 101

Example 2

Input: 7

The binary representation of 7 is: 111.

thinking

If you just look at the solution, you will find it is very easy, but how do you come up with it?

So if you want to know if n is alternating, if you want to know if n is alternating, you can do n to the n over 2, where n to the n over 2 is always 1, and then you can do and with n to the n over 2 plus 1, and if it’s alternating, it’s 0, otherwise it’s not alternating

Reference Implementation 1

To achieve 1

/ * * *@param {number} n
 * @return {boolean}* /
// Runtime: 56 ms, faster than 80.61 of JavaScript online submissions for Binary Number with Alternating Bits.
// Memory Usage: 38.5 MB, less than 54.08% of JavaScript online submissions for Binary Number with Alternating Bits.
export default (n) => {
  n = n ^ Math.floor(n >> 1);
  return! (n & (n +1));
};

Copy the code

476. The complement of numbers

Topic describes

Given a positive integer, print its complement. A complement is the negation of the binary representation of the number.

Example 1

Input: 5

Explanation: The binary representation of 5 is 101 (without leading zeros) and its complement is 010. So you have to print 2.

Example 2

Input: 1

Explanation: The binary representation of 1 is 1 (with no leading zeros) and its complement is 0. So you need to print 0.

thinking

So this is a very obvious case of trying to invert the 1, so for example, when it’s 5, binary is 101, but if you directly invert the 5, the high place is always 1, which obviously doesn’t match the result, so you have to find a way to put the high place to 0

So you can get the same mask as 5, say 111, with a high order of 0

Reference Implementation 1

To achieve 1

/ * * *@param {number} num
 * @return {number}* /
// submissions online for Number Complement
// Memory Usage: 10000 MB, less than 10000 MB of JavaScript online submissions for Number Complement.
export default (n) => {
  let mask = 1;
  while (mask < n) {
    mask = (mask << 1) | 1;
  }
  return ~n & mask;
};

Copy the code