rvired
BAN USERrvired@gmail.com for Comments
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
/* Iterated bitcount iterates over each bit. The while condition sometimes helps
terminates the loop earlier */
int iterated_bitcount (unsigned int n)
{
int count=0;
while (n)
{
count += n & 0x1u ;
n >>= 1 ;
}
return count ;
}
/* Sparse Ones runs proportional to the number of ones in n.
The line n &= (n-1) simply sets the last 1 bit in n to zero. */
int sparse_ones_bitcount (unsigned int n)
{
int count=0 ;
while (n)
{
count++ ;
n &= (n - 1) ;
}
return count ;
}
/* Dense Ones runs proportional to the number of zeros in n.
It first toggles all bits in n, then diminishes count repeatedly */
int dense_ones_bitcount (unsigned int n)
{
int count = 8 * sizeof(int) ;
n ^= (unsigned int) -1 ;
while (n)
{
count-- ;
n &= (n - 1) ;
}
return count ;
}
/* Precomputed bitcount uses a precomputed array that stores the number of ones
in each char. */
static int bits_in_char [256] ;
void compute_bits_in_char (void)
{
unsigned int i ;
for (i = 0; i < 256; i++)
bits_in_char [i] = iterated_bitcount (i) ;
return ;
}
int precomputed_bitcount (unsigned int n)
{
// works only for 32-bit ints
return bits_in_char [n & 0xffu]
+ bits_in_char [(n >> 8) & 0xffu]
+ bits_in_char [(n >> 16) & 0xffu]
+ bits_in_char [(n >> 24) & 0xffu] ;
}
/* Here is another version of precomputed bitcount that uses a precomputed array
that stores the number of ones in each short. */
static char bits_in_16bits [0x1u << 16] ;
void compute_bits_in_16bits (void)
{
unsigned int i ;
for (i = 0; i < (0x1u<<16); i++)
bits_in_16bits [i] = iterated_bitcount (i) ;
return ;
}
int precomputed16_bitcount (unsigned int n)
{
// works only for 32-bit int
return bits_in_16bits [n & 0xffffu]
+ bits_in_16bits [(n >> 16) & 0xffffu] ;
}
/* Parallel Count carries out bit counting in a parallel
fashion. Consider n after the first line has finished
executing. Imagine splitting n into pairs of bits. Each pair contains
the <em>number of ones</em> in those two bit positions in the original
n. After the second line has finished executing, each nibble contains
the <em>number of ones</em> in those four bits positions in the
original n. Continuing this for five iterations, the 64 bits contain
the number of ones among these sixty-four bit positions in the
original n. That is what we wanted to compute. */
#define TWO(c) (0x1u << (c))
#define MASK(c) (((unsigned int)(-1)) / (TWO(TWO(c)) + 1u))
#define COUNT(x,c) ((x) & MASK(c)) + (((x) >> (TWO(c))) & MASK(c))
int parallel_bitcount (unsigned int n)
{
n = COUNT(n, 0) ;
n = COUNT(n, 1) ;
n = COUNT(n, 2) ;
n = COUNT(n, 3) ;
n = COUNT(n, 4) ;
/* n = COUNT(n, 5) ; for 64-bit integers */
return n ;
}
/* Nifty Parallel Count works the same way as Parallel Count for the
first three iterations. At the end of the third line (just before the
return), each byte of n contains the number of ones in those eight bit
positions in the original n. A little thought then explains why the
remainder modulo 255 works. */
#define MASK_01010101 (((unsigned int)(-1))/3)
#define MASK_00110011 (((unsigned int)(-1))/5)
#define MASK_00001111 (((unsigned int)(-1))/17)
int nifty_bitcount (unsigned int n)
{
n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ;
n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ;
n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ;
return n % 255 ;
}
/* MIT Bitcount
Consider a 3 bit number as being
4a+2b+c
if we shift it right 1 bit, we have
2a+b
subtracting this from the original gives
2a+b+c
if we shift the original 2 bits right we get
a
and so with another subtraction we have
a+b+c
which is the number of bits in the original number.
Suitable masking allows the sums of the octal digits in a 32 bit number to
appear in each octal digit. This isn't much help unless we can get all of
them summed together. This can be done by modulo arithmetic (sum the digits
in a number by molulo the base of the number minus one) the old "casting out
nines" trick they taught in school before calculators were invented. Now,
using mod 7 wont help us, because our number will very likely have more than 7
bits set. So add the octal digits together to get base64 digits, and use
modulo 63. (Those of you with 64 bit machines need to add 3 octal digits
together to get base512 digits, and use mod 511.)
This is HACKMEM 169, as used in X11 sources.
Source: MIT AI Lab memo, late 1970's.
*/
int mit_bitcount(unsigned int n)
{
/* works for 32-bit numbers only */
register unsigned int tmp;
tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}
void verify_bitcounts (unsigned int x)
{
int iterated_ones, sparse_ones, dense_ones ;
int precomputed_ones, precomputed16_ones ;
int parallel_ones, nifty_ones ;
int mit_ones ;
iterated_ones = iterated_bitcount (x) ;
sparse_ones = sparse_ones_bitcount (x) ;
dense_ones = dense_ones_bitcount (x) ;
precomputed_ones = precomputed_bitcount (x) ;
precomputed16_ones = precomputed16_bitcount (x) ;
parallel_ones = parallel_bitcount (x) ;
nifty_ones = nifty_bitcount (x) ;
mit_ones = mit_bitcount (x) ;
if (iterated_ones != sparse_ones)
{
printf ("ERROR: sparse_bitcount (0x%x) not okay!\n", x) ;
exit (0) ;
}
if (iterated_ones != dense_ones)
{
printf ("ERROR: dense_bitcount (0x%x) not okay!\n", x) ;
exit (0) ;
}
if (iterated_ones != precomputed_ones)
{
printf ("ERROR: precomputed_bitcount (0x%x) not okay!\n", x) ;
exit (0) ;
}
if (iterated_ones != precomputed16_ones)
{
printf ("ERROR: precomputed16_bitcount (0x%x) not okay!\n", x) ;
exit (0) ;
}
if (iterated_ones != parallel_ones)
{
printf ("ERROR: parallel_bitcount (0x%x) not okay!\n", x) ;
exit (0) ;
}
if (iterated_ones != nifty_ones)
{
printf ("ERROR: nifty_bitcount (0x%x) not okay!\n", x) ;
exit (0) ;
}
if (mit_ones != nifty_ones)
{
printf ("ERROR: mit_bitcount (0x%x) not okay!\n", x) ;
exit (0) ;
}
return ;
}
int main (void)
{
int i ;
compute_bits_in_char () ;
compute_bits_in_16bits () ;
verify_bitcounts (UINT_MAX) ;
verify_bitcounts (0) ;
for (i = 0 ; i < 100000 ; i++)
verify_bitcounts (lrand48 ()) ;
printf ("All bitcounts seem okay!\n") ;
return 0 ;
}
#include <stdio.h>
#include <malloc.h>
typedef struct list {
struct list *next;
int val;
}list;
void PrintList(list *start)
{
while(start != NULL)
{
printf("%d ", start->val);
start = start->next;
}
printf("\n");
}
list * Reverse(list *root, int count)
{
list *prev = NULL, *start = root, *nex, *newroot = NULL;
int i=0;
while( i < count && start != NULL)
{
nex = start->next;
start->next = prev;
prev = start;
start = nex;
i = i+1;
}
if(start == NULL)
return prev;
if(newroot == NULL)
newroot = prev;
PrintList(prev);
prev = Reverse(start, count);
root->next=prev;
return newroot;
}
void alloc(list **node, int val)
{
*node = (list *)malloc(sizeof(list));
(*node)->val = val;
(*node)->next = NULL;
}
void BuildList (list **root)
{
list *start = *root, *temp=NULL;
int i=0, n=0;
printf("Enter the number of nodes: ");
scanf(" %d", &n);
while(i < n)
{
alloc(&temp, i+1);
if(start == NULL)
{
*root = temp;
start = temp;
i = i+1;
continue;
}
alloc(&temp, i+1);
start->next = temp;
start = temp;
i = i+1;
}
}
int main(void)
{
list *root=NULL, *nroot;
int bcount;
BuildList(&root);
PrintList(root);
printf("Enter the Block Size:");
scanf(" %d", &bcount);
nroot = Reverse(root, bcount);
printf("Final Reverse List:");
PrintList(nroot);
return 0;
}
- rvired March 30, 2010