This is the 22nd day of my participation in the Gwen Challenge.More article challenges

For a better tomorrow, keep brushing LeetCode!

The title

Implement a function that takes an integer (in the form of a binary string) and outputs the number of 1s in the binary representation of that number. For example, 9 in binary is 1001 with two bits of 1. Therefore, if the input is 9, the function outputs 2.

Example 1:

Input: 00000000000000000000000000001011 output: 3: input binary string in 00000000000000000000000000001011, a total of three for the '1'.Copy the code

Example 2:

Input: 00000000000000000000000010000000 output: 1: input binary string in 00000000000000000000000010000000, a total of a '1'.Copy the code

Example 3:

Input: 11111111111111111111111111111101 output: 31 explanation: input binary string in 11111111111111111111111111111101, a total of 31 as' 1 '.Copy the code

Tip:

The input must be a binary string of length 32.Copy the code

Solution one – bit operation

Their thinking

We know that n&(n−1)n \& (n−1)n&(n−1) will change the least significant 1 of NNN to 0, so we can use this property to calculate the number of 1 in the binary bits of NNN. Namely, until n = = 0 n = = 0 n = = 0 n & n (n – 1) \ & n (n – 1) & (n – 1) the number of operations.

code

func hammingWeight(num uint32) (n int) {
    for ; num > 0; num &= num - 1 {
        n++
    }
    return
}
Copy the code

The execution result

Execution time: 0 ms, beat 100.00% user memory consumption in all Go commits: 1.9 MB, beat 61.94% of users in all Go commitsCopy the code

Complexity analysis

  • Time complexity: O(logn)O(logn)O(logn). The number of cycles is equal to the number of ones in the binary bits of NNN, and the worst case is all ones in the binary bits of NNN.
  • Space complexity: O(1)O(1)O(1)

Topic link

191. The number of bits 1

Similar to the topic

  • Reverse binary
  • A power of 2
  • Bit count
  • Binary watch
  • Hamming distance
  • Alternate binary number
  • In binary representation, the prime number is computed to be set