Original title:
Write the function int bitcount (short infut) Takes a short as infut and returns an int. The function returns the number of bits set in the input variable. For instance: Bitcount (7) -> 3 Bitcount (2543) - > 9 Bitcount (11111) -> 9
The question in the "Interview Series 1 ...", netizens pointed out the shortcomings of the answer, and give another algorithm for different efficiency, thank you very much, and put it out to share with you.
/ * * The average efficiency is relatively low, and the worst case is to cycle SIZEOF (X) * 8 times. * Take a look at the following function, it is for 32-bit, as for other digits. * * RETURN NUMBER OF BITS SET * /
Unsigned int x) {x = (x & 0x5555555 ul) ((x >> 1) & 0x55555555ul); // 0-2 in 2 bits x = (x & 0x33333333 ul) (x >> 2 ) & 0x33333333 el); // 0-4 in 4 BITS #IF 1 // Version 1 x = (x & 0x0F0F0FUL) ((x >> 4) & 0x0f0f0f0ful); // 0-8 in 8 bits x = ( X & 0x00FF00FUL) (x >> 8) & 0x00FF00FFUL); // 0-16 in 16 BITS X = (x & 0x0000FFFUL) ((x >> 16) & 0x0000FFFUL); // 0-31 in 32 Bits Return X; #ELSE // Version 2 x = (x (x >> 4)) & 0x0f0f0f0ful; // 0-8 in 4 BITS X = X >> 8; // 0-16 in 8 BITS X = x >> 16; // 0-32 in 8 bits returnx x & 0xff; #ndif}
Add:
Because the netizen is more difficult to know, the refined code is more difficult, so I will talk about my opinion. If there is a place, please also give more guidance.
Regarding the understanding of the number of binary numbers, each bit can only be 0 and 1, so in this place, we can understand that each bit can represent the number of 1 in this bit.
Look at the first line of code: x = (x & 0x5555555 ul) ((x >> 1) & 0x55555555ul);
5 binary is 0101, when X & 0x5555555UL draws the result of 0, 2, 4, 6 ..., 30 bits, namely 0, 2, 4, 6, ..., 30 bits included 1 Number; then naturally understand (x >> 1) & 0x55555555 ul results are the value of 1, 3, 5, 7, ..., 31 bits, 1, 3, 5, 7,. .., 31 bits contain 1 number. Add two: xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx
0101 0101 0101 0101 0101 0101 0101 0101
-------------------------------------------------- ----------------------
0x0x 0x0x 0x0x 0x0x 0x0x 0x0x 0x0x 0x0x (here is the value of X in X] 0, 2, 4, ..., 30 bits)
0xxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx
0101 0101 0101 0101 0101 0101 0101 0101
-------------------------------------------------- ----------------------
0Y0Y 0Y0Y 0Y0Y 0Y0Y 0Y0Y 0Y0Y 0Y0Y 0Y0Y (here is the value of 1, 3, 5, ..., 31 bits)
0x0x 0x0x 0x0x 0x0x 0x0x 0x0x 0x0x 0x0x
0Y0Y 0Y0Y 0Y0Y 0Y0Y 0Y0Y 0Y0Y 0Y0Y 0Y0Y
-------------------------------------------------- ----------------------
ZZ ZZ ZZ ZZ ZZ ZZ zz
You can see 32-bit X numbers as a minimum unit, the value z of X Y is in this two-bit minimum unit, 1. It can be seen that the space of the two plus number 0 is smoked to store the carry. So until now, we get numbers in numbers, each two is the minimum unit, and the values in every two digits represent the number of 1 in these two digits.
According to this type, we use the same method to calculate the number of 4 bits in the minimum unit, 4 bits, namely: x = (x & 0x333333333 ul) ((x >> 2 ) & 0x33333333 ul);
Then 8 bits, 16 bits, when calculated to 32-bit minimum units, 32 digits indicate the number of 1 in the 32-bit 1, the answer is revealed.
