For 3 minutes a day, take the algorithmic counterattack route.

Handled in the collection

A daily collection of LeetCode preambles

Code warehouse

Making: github.com/meteor1993/…

Gitee: gitee.com/inwsy/LeetC…

Title: Number of bits 1

Title source: leetcode-cn.com/problems/nu…

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

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:

  • 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 should not affect your implementation, because the internal binary representation of an integer is the same whether it 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.

Solution 1: violence verification

This is a little bit less of a problem than the one we had yesterday, but it’s still looking at binary arithmetic.

To figure out how many 1’s there are in a binary, you can loop from the last digit, and compare that to 1, and we’ve done this before, and a common way to do that is to do modulo operations, and you get the last digit, but if it’s a 32-bit binary, then the first digit is a plus or minus sign.

So taking the last bit of binary is usually not a modulo operation, but a bit operation &1.

We can use ampersand 1 to verify that the last digit is 1, and we can use ampersand 10 to verify that the second to last digit is 1, and we can keep going.

Here’s the answer to the question:

public int hammingWeight(int n) {
    int count = 0;
    int mask = 1;
    for (int i = 0; i < 32; i++) {
        if((n & mask) ! =0) {
            count++;
        }
        mask <<= 1;
    }
    return count;
}
Copy the code

Solution plan 2: exclusive plan

The answer to this problem describes this solution, which is a bit of a binary number manipulation trick.

When a binary number n operates with bits & of n-1, it is always possible to change the last bit from 1 to 0 while leaving the other bits unchanged.

And this is easy to understand because it’s binary, so the last digit of n minus one and n must be 0 and 1, so if you do an ampersand on both of them, that’s the same thing as if you do an ampersand on 0 and 1, you get 0.

And n, if the last digit is 0, it borrows a 1 from the highest digit, which feels a little bit like a decimal borrowing.

And if we keep going through this cycle, at some point we’re going to run out of 1’s at the top, and we’re going to end up with 0’s at the top, and the number of times we’re going to end up with 1’s in this n.

public int hammingWeight_1(int n) {
    int count = 0;
    while(n ! =0) {
        count++;
        n &= (n - 1);
    }
    return count;
}
Copy the code

Backing with the problem yesterday, today’s topic reason feel difficulty not so high, is the main investigation of binary arithmetic, bit operations in addition to have &, commonly used and | and ^ operation, meet the topic can give priority to the binary bit operations with some special values.