Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Like it and see. Make it a habit. Wechat search [a coding] follow this programmer who is struggling in the Internet.

This article is collected on Github – Technical expert Training, which contains my learning route, series of articles, interview question bank, self-study materials, e-books, etc.

Subtracting 1 from an integer and summing it with the original integer turns the rightmost 1 of the integer into a 0. So you can do this as many times as the binary number of an integer has 1’s.

— Leetcode

preface

Hello, everyone. I’m One.

Confused algorithm, rarely confused

A question encountered during the interview

Question

Offer 15. Number of 1s in binary

Difficulty: Easy

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

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.

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.

Solution

Another problem that can be solved by clever bit operations.

(n−1) : binary number NN the rightmost 1 becomes a 0, and all zeros to the right of this 1 become 1s. N & (n-1) : Binary number n the rightmost 1 becomes 00, remaining unchanged.

  • And I keep getting rid of the 1’s on the right-hand side
  • Count the number of operations performed and
  • It ends when n = 0

Code

All LeetCode codes have been synchronized to Github

Welcome to star

/ * * *@author yitiaoIT
 */
public class Solution {
    public int hammingWeight(int n) {
        int sum = 0;
        while(n ! =0) {
            sum++;
            n &= n - 1;
        }
        returnsum; }}Copy the code

Result

Complexity analysis

  • Time complexity: O(N)

Last

One foot is difficult to go, one hand is difficult to sing, a person’s power is limited after all, a person’s journey is doomed to be lonely. When you set a good plan, with full of blood ready to set out, must find a partner, and Tang’s monk to the West, the master and his disciples four people united as one to pass the ninety-eight difficult. So,

If you want to get into a big factory,

To learn data structures and algorithms,

If you want to keep brushing,

To have a group of like-minded people,

Please join the team to brush the questions