[solution] sword finger offer 15 Number of 1 in binary (C language)

️ The finger of the sword  Offer 15.  Binary 1 The number of ️

Topic details

Write a function , Input is an unsigned integer （ In the form of a binary string ）, Returns the number of digits in its binary expression as  '1'  The number of （ Also known as   Hamming weight ).）.

Tips ：

• Please note that , In some languages （ Such as  Java） in , There is no unsigned integer type . under these circumstances , Both input and output will be specified as signed integer types , And should not affect your implementation , Because whether integers are signed or unsigned , Its internal binary representation is the same . stay  Java  in , The compiler uses   Binary complement   Notation to represent signed integers . therefore , Above   The third example   in , The input represents a signed integer  -3.

• The input must be of length  32  Of   Binary string  .

Example ：

Input ：n = 11 ( Console input  00000000000000000000000000001011)
Output ：3
explain ： Binary string of input  00000000000000000000000000001011  in , There are three of them  '1'.
Input ：n = 128 ( Console input  00000000000000000000000010000000)
Output ：1
explain ： Binary string of input  00000000000000000000000010000000  in , There is one in all for  '1'.
Input ：n = 4294967293 ( Console input  11111111111111111111111111111101, In some languages  n = -3）
Output ：31
explain ： Binary string of input  11111111111111111111111111111101  in , share  31  Position as  '1'.


Limit ：

nothing


source ：

Power button （LeetCode）

link ：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof

Their thinking

This problem requires us to solve according to the binary sequence of an integer , Calculate how many... In the binary sequence

1

, In essence, it is to examine the use of bit operation .

Method 1：

  With C Language as an example , The storage form of integer is 32 Bit binary sequence , Complement stored in memory , For positive integers , The binary original code is the same as the complement , For negative integers , The complement code is added on the basis of the inverse code obtained by subtracting the highest bit from the original code 1. The first thought is to judge whether each bit of the binary sequence of the input integer is 1. We can associate this binary sequence with

1

To perform bitwise operations , because

1

Only the last bit of a binary sequence is

1

, So if the last bit of this binary sequence is

1

Then return to

1

, Otherwise return to

0

. Then we can shift the binary sequence to the right , So you can discard the rightmost sequence , after 32 operations , We can judge how many of the whole binary sequence

1

.

Time complexity ：

  Because the binary sequence of input integers is 32 position , Whatever you type , Will cycle 32 Time , Time complexity O(32).

Method 2：

  Suppose the integer entered is

n

, We might as well

n

And

n-1

To perform bitwise operations , Then you will find that the result of the operation is the same as n comparison , One is missing from the binary sequence

1

, Generally speaking , Every time such an operation is performed , Binary

1

Will reduce one , We can design the solution according to the characteristics of this operation . We can put every time

n&(n-1)

Save your results to

n

, until

n=0

. Calculate the number of operations , namely

1

The number of .

Time complexity ：

  There are several in the binary sequence 1 Just cycle a few times , Because of the previous solution , Up to circular judgment 32 Time , Worst time complexity O(32).

Source code

programing language ：C Language online programming platform ： Power button

// Method 1
int hammingWeight(uint32_t n) {
 int cnt = 0;
 while (n)
 {
 if (n & 1)
 {
 cnt++;
 }
 n >>= 1;
 }
 return cnt;
}


// Method 2
int hammingWeight(uint32_t n) {
 int cnt = 0;
 while (n)
 {
 n = n & (n - 1);
 cnt++;
 }
 return cnt;
}


summary

For binary sequences, find the number of elements in a sequence , Can pass

n & 1

  and

n & (n-1)

Realization .<center><font color=red> The old fellow who felt the article was well written , Like comments, pay attention to a wave ！ Thank you very much! ！