Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Count bits using lookup table..

Posted on 2009-02-24
4
Medium Priority
?
274 Views
Last Modified: 2012-05-06
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...
0
Comment
Question by:zizi21
  • 2
4 Comments
 
LVL 22

Accepted Solution

by:
pivar earned 1000 total points
ID: 23720172
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
 
LVL 85

Assisted Solution

by:ozo
ozo earned 1000 total points
ID: 23720221
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
 
LVL 22

Expert Comment

by:pivar
ID: 23720311
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
 

Author Comment

by:zizi21
ID: 23720382
pls give me some time to understand...
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

810 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question