The number of 1’s in binary (including an extension problem)

A, the title

Write a function that takes an unsigned integer (as a binary string) as input and returns the number of ‘1’ digits in its binary expression (also known as the Hamming weight). .

Tip:

Note that in some languages, such as Java, there are no unsigned integer types. In this case, both input and output will be specified as signed integer types, and your implementation should not be affected because the internal binary representation is the same whether the integer is signed or unsigned. In Java, the compiler uses binary complement notation to represent signed integers. Therefore, in example 3 above, the input represents the signed integer -3.

Example 1:

Input: n = 11 (00000000000000000000000000001011) the console input output: 3: input binary string in 00000000000000000000000000001011, a total of three for the '1'.Copy the code

Example 2:

Input: n = 128 (00000000000000000000000010000000) the console input output: 1: input binary string in 00000000000000000000000010000000, a total of a '1'.Copy the code

Example 3:

Input: n = 4294967293 (console enter 11111111111111111111111111111101, n = 3) in the part of the language output: 31: 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.

191: leetcode-cn.com/problems/nu…

Source: LeetCode link: leetcode-cn.com/problems/er… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

solution

One bit, one bit to the right, judging the last bit at a time

func hammingWeight(_ n: Int) -> Int {
    var count = 0
    var temp = n
    
    while temp > 0 {
        count + = (temp & 1 = = 1) ? 1 : 0
        temp > > = 1
    }

    return count
}
Copy the code

Think about a

This solution is easy to figure out. So the interviewer might ask, well, moving one place to the right is mathematically equivalent to dividing by two, so can I just divide by two?

Better not. Because the efficiency of division is much lower than the efficiency of bitwise operation, bitwise operation is also used to replace multiplication and division in the actual coding process, especially in the code with high frequency calls.

Second, expand the problem

Does the above solution still work if the unsigned integers in the problem are replaced by signed integers?

0x80000000 is a negative number, so instead of 0x40000000 to the right, it’s 0xC0000000

Moving to the right will fill the blanks with sign bits, negative for 1, positive for 0

If the single memory is moved to the right, it will loop forever

Let’s think about it a little differently. Let’s move 1

• Knowledge supplement:
  • Negative numbers are identified in the computer binary by complement
  • Negative complement: the sign bit is reversed, and then +1

solution

func hammingWeight2(_ n: Int) -> Int {
    var count: Int = 0
    var flag: Int = 1
    
    while (flag ! = 0) {
        count + = (n & flag = = flag) ? 1 : 0
        if flag < 0 {// The highest bit is 1
            return count
        }
        flag < < = 1
    }

    return count
}
Copy the code

👋

• 📦 Technical documentation
• 🐙 making
• Wechat: RyukieW

My apps