Can't Copy and Paste this?
Click here for a copy-and-paste friendly version of this code!
//**************************************
//
//INCLUDE files for :Count bits in a num
// ber (recursive table look-up)
//**************************************
//
/* bittops.h +++Date last modified: 05-Jul-1997 */
/*
** Macros and prototypes for bit operations
**
** public domain for SNIPPETS by:
**Scott Dudley
**Auke Reitsma
**Ratko Tomic
**Aare Tali
**J. Blauth
**Bruce Wedding
**Bob Stout
*/
#ifndef BITOPS__H
#define BITOPS__H
#include
#include
#include
#include "sniptype.h"/* for TOBOOL() */
#include "extkword.h"/* for CDECL*/
/*
** Macros to manipulate bits in any integral data type.
*/
#define BitSet(arg,posn) ((arg) | (1L << (posn)))
#define BitClr(arg,posn) ((arg) & ~(1L << (posn)))
#define BitFlp(arg,posn) ((arg) ^ (1L << (posn)))
#define BitTst(arg,posn) TOBOOL((arg) & (1L << (posn)))
/*
** Macros to manipulate bits in an array of char.
** These macros assume CHAR_BIT is one of either 8, 16, or 32.
*/
#define MASK CHAR_BIT-1
#define SHIFT ((CHAR_BIT==8)?3:(CHAR_BIT==16)?4:8)
#define BitOff(a,x) ((void)((a)[(x)>>SHIFT] &= ~(1 << ((x)&MASK))))
#define BitOn(a,x)((void)((a)[(x)>>SHIFT] |= (1 << ((x)&MASK))))
#define BitFlip(a,x) ((void)((a)[(x)>>SHIFT] ^= (1 << ((x)&MASK))))
#define IsBit(a,x)((a)[(x)>>SHIFT]&(1 << ((x)&MASK)))
/*
** BITARRAY.C
*/
char *alloc_bit_array(size_t bits);
intgetbit(char *set, int number);
void setbit(char *set, int number, int value);
void flipbit(char *set, int number);
/*
** BITFILES.C
*/
typedef struct {
FILE * file;/* for stream I/O*/
charrbuf;/* read bit buffer */
charrcnt;/* read bit count*/
charwbuf;/* write bit buffer */
charwcnt;/* write bit count */
} bfile;
bfile * bfopen(char *name, char *mode);
int bfread(bfile *bf);
voidbfwrite(int bit, bfile *bf);
voidbfclose(bfile *bf);
/*
** BITSTRNG.C
*/
void bitstring(char *str, long byze, int biz, int strwid);
/*
** BSTR_I.C
*/
unsigned int bstr_i(char *cptr);
/*
** BITCNT_1.C
*/
int CDECL bit_count(long x);
/*
** BITCNT_2.C
*/
int CDECL bitcount(long i);
/*
** BITCNT_3.C
*/
int CDECL ntbl_bitcount(long int x);
int CDECL BW_btbl_bitcount(long int x);
int CDECL AR_btbl_bitcount(long int x);
/*
** BITCNT_4.C
*/
int CDECL ntbl_bitcnt(long x);
int CDECL btbl_bitcnt(long x);
#endif /* BITOPS__H */
code:
Can't Copy and Paste this?
Click here for a copy-and-paste friendly version of this code!
Terms of Agreement:
By using this code, you agree to the following terms...
1) You may use this code in your own programs (and may compile it into a program and distribute it in compiled format for langauges that allow it) freely and with no charge.
2) You MAY NOT redistribute this code (for example to a web site) without written permission from the original author. Failure to do so is a violation of copyright laws.
3) You may link to this code from another website, but ONLY if it is not wrapped in a frame.
4) You will abide by any additional copyright restrictions which the author may have placed in the code or code's description.
**
//
/* +++Date last modified: 05-Jul-1997 */
/*
** BITCNT_4.C - Recursive bit counting functions using table lookup
**
** public domain by Bob Stout
*/
#include "bitops.h"/* from Snippets */
static char bits[256] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, /* 0- 15 */
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 16 - 31 */
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 32 - 47 */
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 48 - 63 */
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 64 - 79 */
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 80 - 95 */
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 96 - 111 */
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 112 - 127 */
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 128 - 143 */
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 144 - 159 */
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 160 - 175 */
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 176 - 191 */
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 192 - 207 */
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 208 - 223 */
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 224 - 239 */
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8/* 240 - 255 */
};
/*
** Count bits in each nybble
**
** Note: Only the first 16 table entries are used, the rest could be
**omitted.
*/
int CDECL ntbl_bitcnt(long x)
{
int cnt = bits[(int)(x & 0x0000000FL)];
if (0L != (x >>= 4))
cnt += ntbl_bitcnt(x);
return cnt;
}
/*
** Count bits in each byte
*/
int CDECL btbl_bitcnt(long x)
{
int cnt = bits[ ((char *)&x)[0] & 0xFF ];
if (0L != (x >>= 8))
cnt += btbl_bitcnt(x);
return cnt;
}
#ifdef TEST
#include
#include "snip_str.h"/* for plural_text() macro*/
main(int argc, char *argv[])
{
long n;
while(--argc)
{
int i;
n = atol(*++argv);
i = btbl_bitcnt(n);
printf("%ld contains %d bit%s set\n",
n, i, plural_text(i));
}
return 0;
}
#endif /* TEST */