Bit counting in a UINT32

- 
unsigned int v; // count bits set in this (32-bit value)
unsigned int c; // store the total here
 
/* Naive way */
for(c = 0; v; c++)
v &= v - 1 ; 
 
/* Parallel computing */  
static const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};

c = v - ((v >> 1) & B[0]);
c = ((c >> S[1]) & B[1]) + (c & B[1]);
c = ((c >> S[2]) + c) & B[2];
c = ((c >> S[3]) + c) & B[3];
c = ((c >> S[4]) + c) & B[4]; 
The B array, which is in binary pattern: 


B[0] = 0x55555555 = 01010101 01010101 01010101 01010101
B[1] = 0x33333333 = 00110011 00110011 00110011 00110011
B[2] = 0x0F0F0F0F = 00001111 00001111 00001111 00001111
B[3] = 0x00FF00FF = 00000000 11111111 00000000 11111111
B[4] = 0x0000FFFF = 00000000 00000000 11111111 11111111

 We can adjust the method for larger integer sizes by continuing with  the patterns for the Binary Magic Numbers, B and S.    If there are k bits, then we need the arrays S and B to be ceil(lg(k))  elements long, and we must compute the same number of expressions for c as S or B are long.  For a 32-bit v, 16 operations are used. 





































Comments








Post a Comment
























Popular posts from this blog









Airtel Digital tv remote factory reset and reprogram






-















 Following is the way to reset Airtel Digial tv universal remote reset procedure.   1. Press red button and ok button together untill red light blinks twice. 2. Release the buttons and press 980 buttons one by one (not together)   3. Red light will blink again two times, now press ok button.    Reprogramming   There are 5 basic functions which your new Airtel remote needs to learn about your TV 1. TV Power code 2. TV Mute code 3. AV code 4. TV VOL + code 5. TV VOL – code Steps for Universal remote setup: Step 1:  Bring Airtel digital TV remote in learning mode. Press and hold ‘’OK + Numeric 2” key for 3 seconds. The LED blinks twice to indicate that your Airtel remote is ready to learn. Step 2 :  Hold the source remote and Airtel remote in front of each other ( 3cm-6m apart). Step 3:  Press & release the key (First on Airtel remote and then on Source remote) which needs to be programmed in Airtel remote. Example: Press and release the TV Power key on both remotes and release. The A








Read more










Tracking Linux kworker threads






-















    How to find out which part of kernel/module has created this workqueue. How to track a kworker-thread named for example ''kworker/0:3 to its origin in kernel-space?     I found  this thread on lkml  that answers your question a little. (It seems even Linus himself was puzzled as to how to find out the origin of those threads.)   Basically, there are two ways of doing this:  $ echo workqueue:workqueue_queue_work > /sys/kernel/debug/tracing/set_event $ cat /sys/kernel/debug/tracing/trace_pipe > out.txt (wait a few secs)   For this you will need  ftrace  to be compiled in your kernel, and to enable it with:  mount -t debugfs nodev /sys/kernel/debug   More information on the function tracer facilities of Linux is available in the  ftrace.txt documentation .   This will output what threads are all doing, and is useful for tracing multiple small jobs.  cat /proc/THE_OFFENDING_KWORKER/stack   This will output the stack of a single thread doing a lot of work. It may allow you








Read more










Asynchronus I/O (AIO) in vxworks and Linux






-















 In generic Asynchronus I/O (AIO) can be designed using User lavel or in Kernel level.  In user level  1) Process needs async callback/notification create another thread and process which goes to sleep on blocking calls (read/write/ioctls/select)  2) One Async master handler (process/thread) keeps track.All the process needs the service submit job to them.The master handler handles the async fd in Blocking mode and reply to requesting processes (or call the callback function) using some async notificatin like signal.  In Kernel Level  1) Call some system call and submit some job to kernel workQ .After work is complete kernel notify using signal to user space.      In VxWorks :    aioPxLib provide the POSIX 1003.1b standard.Which is task implementation of aio service.  functions available:  1) aio_read() - initiate an asyn. read.  2) aio_write() - initiate an syn write  3) aio_listio() - Initiate a aio list upto LIO_MAX  4) aio_error() - Get an aio error status.  5) aio_return() - Get a








Read more