This is code that my TA help me get, but then I completely forgot how it worked exactly since I can't seem to get the right answer, and the interview grading is tomorrow. If anybody can help please do. Thanks
* bitCount - returns count of number of 1's in word
* Examples: bitCount(5) = 2, bitCount(7) = 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 40
* Rating: 4
*/
int bitCount(int x) {
int m4 = 0x1 | (0x1<<8) | (0x1<<16) | (0x1<<24);
int m1 = 0xFF;
int s4 = (x&m4) + ((x>>1)&m4) + ((x>>2)&m4) + ((x>>3)&m4) + ((x>>4)&m4) + ((x>>5)&m4) + ((x>>6)&m4) + ((x>>7)&m4);
int s1 = (s4&m1) + ((s4>>8)&m1) + ((s4>>16)&m1) + ((s4>>24)&m1);
return s1;
}
It is often easier to see what happen in the bit-related operation when you convert it to its bit representation:
Assuming the int is 32-bit, then the following are the m4 & m1 in their bit-representation:
0000 0001 0000 0001 0000 0001 0000 0001 //m4, masking across the 4 bytes
0000 0000 0000 0000 0000 0000 1111 1111 //m1, masking only 1 byte, the Least Significant Byte (LSB)
I suppose m stands for mask, while 4 & 1 refer to 4 bytes and 1 byte respectively
And then the tricky part is the s4. You might need to examine it step by step to get the idea of what it is.
Firstly, note the right-bitwise-shift and the masking with m4:
pqrs tuvw pqrs tuvw pqrs tuvw pqrs tuvw // x
0000 0001 0000 0001 0000 0001 0000 0001 //m4
---------------------------------------- &
0000 000w 0000 000w 0000 000w 0000 000w //x&m4
pqrs tuvw pqrs tuvw pqrs tuvw pqrs tuvw // x
---------------------------------------- >> 1
0pqr stuv wpqr stuv wpqr stuv wpqr stuv // x >> 1
0000 0001 0000 0001 0000 0001 0000 0001 //m4
---------------------------------------- &
0000 000v 0000 000v 0000 000v 0000 000v //(x>>1)&m4
.
.
pqrs tuvw pqrs tuvw pqrs tuvw pqrs tuvw // x
---------------------------------------- >> 7
0000 000p qrst uvwp qrst uvwp qrst uvwp // x >> 7
0000 0001 0000 0001 0000 0001 0000 0001 //m4
---------------------------------------- &
0000 000p 0000 000p 0000 000p 0000 000p //(x>>7)&m4
And secondly, note the addition of the 8 elements obtained from above results:
0000 000w 0000 000w 0000 000w 0000 000w //x&m4
0000 000v 0000 000v 0000 000v 0000 000v //(x>>1)&m4
.
.
0000 000p 0000 000p 0000 000p 0000 000p //(x>>7)&m4
---------------------------------------- +
//Resulting in s4
Thus, since p to w each can only be 0 or 1 and you have eight of such element, consequently, per 8-bit segment you have:
p+q+r+s+t+u+v+w // each element is either 0 or 1
From there, it can be seen clearly that the result for the addition 8 elements above would range from 0 to 8.
That is, you will get 0000 0000 (0 in decimal representation - if all is 0) to 0000 1000 (8 in decimal representation - if all is 1) per 8-bit segment.
Consequently, you will have the s4 in the following format:
0000 abcd 0000 efgh 0000 ijkl 0000 mnop // s4
Where abcd, efgh, ijkl, and mnop are the result of additions p to w per byte.
Now, notice that you get the sum of the number of bits in x spread across the 4 bytes.
(sum I suppose this is what s in the variables stands for - sum)
0000 abcd //byte 1, left most, MSB
0000 efgh //byte 2, second from left
0000 ijkl //byte 3, second from right
0000 mnop //byte 4, rightmost, LSB
Thus, you need to combine the result in those four bytes in s4 to find the sum in one byte
(and I suppose, this is what s1 stands for: sum in one byte)
You get s1 by:
Hence, the following operations (in the bit level) occur:
0000 abcd 0000 efgh 0000 ijkl 0000 mnop // s4
0000 0000 0000 0000 0000 0000 1111 1111 //m1
--------------------------------------- &
0000 0000 0000 0000 0000 0000 0000 mnop
0000 0000 0000 abcd 0000 efgh 0000 ijkl // s4 >> 8
0000 0000 0000 0000 0000 0000 1111 1111 //m1
--------------------------------------- &
0000 0000 0000 0000 0000 0000 0000 ijkl
.
.
0000 0000 0000 0000 0000 0000 0000 abcd // s4 >> 24
0000 0000 0000 0000 0000 0000 1111 1111 //m1
--------------------------------------- &
0000 0000 0000 0000 0000 0000 0000 abcd
It can be seen that you simply have the following additions of four elements:
0000 0000 0000 0000 0000 0000 0000 mnop //0 to 8
0000 0000 0000 0000 0000 0000 0000 ijkl //0 to 8
0000 0000 0000 0000 0000 0000 0000 efgh //0 to 8
0000 0000 0000 0000 0000 0000 0000 abcd //0 to 8
--------------------------------------- +
//Final result, s1
You have simple addition of four numbers, each having value of 0 to 8. Thus, it must result in a value of 0 to 32 (0 is when all is 0, 32 is when all is 8), which is the number of bit 1 in the variable x. And thus the function is named bitCount.
That is how the function works.
Final note: knowing this, you could even change m1 with 0x0F (instead of 0xFF) and the result would still be the same.