• C

Count bits using lookup table..

hi,

i got this code from here: https://utd.edu/~rxc064000/cracktheinterview/pages/4_0.html


const unsigned char LookupTable[]     = {  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,  
                                           1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
                                           1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
                                           2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
                                           1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,    
                                           2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
                                           2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
                                           3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
                                           1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
                                           2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
                                           2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
                                           3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
                                           2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
                                           3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
                                           3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
                                           4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};


unsigned int num;
unsigned int ctr;   // Number of bits set.

ctr = LookupTable[num & 0xff] +    
      LookupTable[(num >> 8) & 0xff] +    
      LookupTable[(num >> 16) & 0xff] +    
      LoopupTable[num >> 24];


I understand how the LookupTable is set where 0 represent 0 bit sets, 1 represent 1 bits set...

But i dont understand this part: LookupTable[num & 0xff] +    
      LookupTable[(num >> 8) & 0xff] +    
      LookupTable[(num >> 16) & 0xff] +    
      LoopupTable[num >> 24];

could anyone pls pls explain this....i mean, why & 0xfff and then you have num>>8 ..etc...

pls help...
zizi21Asked:
Who is Participating?
 
pivarCommented:
Hi,

>> means shift right. That is, you shift the bits to the left by (in the example) 8,16 or 24 bits. The "& 0xff" part means "and 255" and ensures you only get the first 8 bits (0xff or 255) of the dword.

This code take each byte (8 bits) in a 4 byte (32 bits) dword and use this as index into LookupTable.

Example, you have a dword 0x01020304 as value of num

ctr = LookupTable[4] +    
      LookupTable[3] +    
      LookupTable[2] +    
      LoopupTable[1];

ie
ctr = 1 +2 + 1 +1;

/peter
0
 
ozoCommented:
num & 0xff is the rightmost 8 bits of num
LookupTable[num & 0xff] is the number of bits in the low order byte of num
num>>8 shifts the next 8 bits into the low order positon
(num >> 8) & 0xff masks them off
LookupTable[(num >> 8) & 0xff]  is the number of bits in the next byte of num
0
 
pivarCommented:
Typo. first line should read

>> means shift right. That is, you shift the bits to the *right* by (in the example) 8,16 or 24 bits. The "& 0xff"


0
 
zizi21Author Commented:
pls give me some time to understand...
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.