Author 
Message 
John Kugelma #1 / 19

sizeof without sizeof
Quote:
> I was trying to see what was the fastest > way I could find out the size of an int on > a machine (in bits) without using sizeof(int)*8 > or limits.h
<snip strange ways to compute the size of an int, which don't work correctly> Quote: > And while I'm on the subject, does anybody know how sizeof > is actually implemented? > I looks to me like its done in the preprocessor.
No, not quite, but sizeof does create a compile time constant. Since the sizeof a type or object is constant and must be determined at compile time, there's no reason why sizeof(int)*CHAR_BIT (CHAR_BIT instead of 8) should not be the fastest method of determining the number of bits in an integer, since it will create a constant. Certainly typing 52 into your source code is the fastest way to calculate 52? However, if you want to determine the number of bits that contribute to an integer's value, that's a different story. Here you will have to have some run time checking. But it shouldn't really matter how fast this code is, since you'll only have to do it once. Here's some code you could use to determine the number of useful bits in an integral type: unsigned int bits = 7; unsigned type num = 0x80; for (; num; bits++, num <<= 1); /* "bits" holds number of value bits now. */ Where type is one of char, short, int, or long. This also doesn't assume any properties about the types such as that they are all exact multiples of a certain number of bits (your code assumes types are 2^n bits wide). ... I just reread your message, and you said you don't want to use <limits.h>. Why not? 
I believe we can change anything. I believe in my dream.  Joe Satriani

Tue, 12 Dec 2000 03:00:00 GMT 


Bill Kric #2 / 19

sizeof without sizeof
I was trying to see what was the fastest way I could find out the size of an int on a machine (in bits) without using sizeof(int)*8 or limits.h I assume that most machines will have an int that is both a multiple of 8 and a power of 2. My first attempt was this: unsigned bits = 8; while(1<<bits) bits+=bits; printf("An int is %d", bits); this didn't work because according to Microsoft's VC 4.2 help: "The results are undefined if the right operand of a shift expression is negative or if the right operand is greater than or equal to the number of bits in the (promoted) left operand." In fact, when walking through the disassembly in the de{*filter*}, it appears that the shift instruction isn't executed at all. (note: I have an Intel PII300) This all seems strange since you can do a shift in a loop more than 32 times and shift the number until it's zero. But anyway, my second attempt was: unsigned bits = 8; while((1<<bits1)<<1) bits+=bits; printf("An int is %d", bits); I had to shift 31 times then 1 more. This works but is ugly. Anybody have thoughts on how to do this a better way? And while I'm on the subject, does anybody know how sizeof is actually implemented? I looks to me like its done in the preprocessor. ... Bill

Wed, 13 Dec 2000 03:00:00 GMT 


Siemel Nar #3 / 19

sizeof without sizeof
Quote: >I was trying to see what was the fastest >way I could find out the size of an int on >a machine (in bits) without using sizeof(int)*8 >or limits.h
sizeof(T) is computed at compile time. There's no run time overhead. In fact sizeof(T)*8 is also a computation that can be done at compile time, since it's of the form constant*constant.  


Wed, 13 Dec 2000 03:00:00 GMT 


Lawrence Kir #4 / 19

sizeof without sizeof
Quote: >I was trying to see what was the fastest >way I could find out the size of an int on >a machine (in bits) without using sizeof(int)*8 >or limits.h
Why do you not want to use those? Strictly not all bits in an integer need contribute to its value, so the question is whether you want the number of bits in the object or the number of bits that contribute to the value. Why is speed an issue? You only need to calculate this once and thren work from a stored result. Quote: >I assume that most machines will have an int >that is both a multiple of 8 and a power of 2.
That is probably true for most machines but why limit your code to just those machines? Quote: >My first attempt was this: >unsigned bits = 8; >while(1<<bits) > bits+=bits;
bits *= 2; is less obfuscated and I'd be very surprised if it was less efficient. Quote: >printf("An int is %d", bits);
Since bits is unsigned use %u. Quote: >this didn't work because according to Microsoft's VC 4.2 help: >"The results are undefined if the right operand of a shift >expression is negative or if the right operand is greater >than or equal to the number of bits in the (promoted) left >operand."
That is correct. Quote: >In fact, when walking through the disassembly in the de{*filter*}, >it appears that the shift instruction isn't executed at all. >(note: I have an Intel PII300)
I believe that the shift instructions there only look at the low order 5 bits of the shift value, so you'll probably end up with a zero shift. Quote: >This all seems strange since you can do a shift in a loop >more than 32 times and shift the number until it's zero.
The standard leaves the behaviour undefined so that variable shift widths can be implement efficiently on various archetectures. Quote: >But anyway, my second attempt was: >unsigned bits = 8; >while((1<<bits1)<<1) > bits+=bits; >printf("An int is %d", bits); >I had to shift 31 times then 1 more. >This works but is ugly. >Anybody have thoughts on how to do this a better way?
Others have posted methods that shift a bit at a time but what are you really trying to achieve? Quote: >And while I'm on the subject, does anybody know how sizeof >is actually implemented?
sizeof is an operator that priduces as its result the size of the *type* of its operand. The operand may be either an explicit type enclosed in parentheses or an expression. In the latter case the type of the expression is determined and then the size of that type. Quote: >I looks to me like its done in the preprocessor.
No, it has nothing to do with the preprocessor, you can't even use it in #if expressions.  


Wed, 13 Dec 2000 03:00:00 GMT 


Bill Kric #5 / 19

sizeof without sizeof
Quote:
> > I was trying to see what was the fastest > > way I could find out the size of an int on > > a machine (in bits) without using sizeof(int)*8 > > or limits.h > I just reread your message, and you said you don't want to use > <limits.h>. Why not?
It's just an exercise to flex my coding skills. A friend and I do this sort of thing from time to time to keep us thinking. Here's one that we did a few weeks back... Given an unsigned int, find the largest power of 2 that will "fit" in it. i.e. given 133 you get 128, given 4000 you get 2048, given 25432 you get 16384, etc... The idea is to find the fastest, most efficient way. Bonus points for portability. Note, we tossed around the idea of using a lookup table but decided that took away the coding challenge and ruled it out. ... Bill

Fri, 15 Dec 2000 03:00:00 GMT 


Siemel Nar #6 / 19

sizeof without sizeof
Quote: >Given an unsigned int, find the largest power of 2 >that will "fit" in it. i.e. given 133 you get 128, >given 4000 you get 2048, given 25432 you get 16384, >etc...
What is the fastest way to do this? I was pondering over this myself. Needed it for some code. If the first bit from the left that is ON is the N'th bit, my algorithm finds the answer in N iterations. Is there a faster way? For example, if number=00101101 (1 byte), then after 3 iterations the answer is found to be 2^5=32. There is also the problem of making the algorithm robust. So if number=00000000, then answer should be 1. The algorithm shouldn't loop forever. Quote: >The idea is to find the fastest, most efficient way. >Bonus points for portability.
inline int base2::logdown(int num) { const int s_upperbit=1<<(8*sizeof(int)1); int lg=8*sizeof(int)1; // assumed: lg&upper=0 while (! ((num&s_upperbit)  (lg&s_upperbit)) ) num<<=1, lg; return lg; Quote: }
Note the optimizations of costant folding and constant propogation. LINE1 and LINE2 are hardcoded at compile time. But maybe there's a better way?  


Fri, 15 Dec 2000 03:00:00 GMT 


Dann Corbi #7 / 19

sizeof without sizeof
Usually, when you ask "What is the fastest way to <splat>?" you are getting into implementation issues. Fastest on machine Q with the Frobozz compiler might be among the slowest reasonable alternatives on machine V using the Smargle compiler. Also, questions about algorithms are probably better
number that I use sometimes: /* Log base 2 estimator */ int qlog2(unsigned long n) { register int i = (n & 0xffff0000) ? 16 : 0; if ((n >>= i) & 0xff00) i = 8, n >>= 8; if (n & 0xf0) i = 4, n >>= 4; if (n & 0xc) i = 2, n >>= 2; return (i  (n >> 1)); Quote: }
/* It is obviously hardwired to longs of 32 bits or less, and hence is an utter, horrid kludge. The principle is obvious enough that you should be able to fix it in a jiffy, if you so desire. */  Hypertext CFAQ: http://www.eskimo.com/~scs/Cfaq/top.html CFAQ ftp: ftp://rtfm.mit.edu, CFAQ Book: ISBN 0201845199 Try "C Programming: A Modern Approach" ISBN 0393969452 Want Software? Algorithms? Pubs? http://www.infoseek.com Quote:
>>Given an unsigned int, find the largest power of 2 >>that will "fit" in it. i.e. given 133 you get 128, >>given 4000 you get 2048, given 25432 you get 16384, >>etc... >What is the fastest way to do this? I was pondering >over this myself. Needed it for some code. If the >first bit from the left that is ON is the N'th bit, >my algorithm finds the answer in N iterations. Is >there a faster way? >For example, if number=00101101 (1 byte), then after >3 iterations the answer is found to be 2^5=32. >There is also the problem of making the algorithm robust. >So if number=00000000, then answer should be 1. The >algorithm shouldn't loop forever. >>The idea is to find the fastest, most efficient way. >>Bonus points for portability. >inline int base2::logdown(int num) >{ > const int s_upperbit=1<<(8*sizeof(int)1); > int lg=8*sizeof(int)1; // assumed: lg&upper=0 > while (! ((num&s_upperbit)  (lg&s_upperbit)) ) > num<<=1, lg; > return lg; >} >Note the optimizations of costant folding and constant propogation. >LINE1 and LINE2 are hardcoded at compile time. >But maybe there's a better way? > >
>

Fri, 15 Dec 2000 03:00:00 GMT 


Mathew Hend #8 / 19

sizeof without sizeof
: /* Log base 2 estimator */ : int qlog2(unsigned long n) : { : register int i = (n & 0xffff0000) ? 16 : 0; : if ((n >>= i) & 0xff00) : i = 8, n >>= 8; : if (n & 0xf0) : i = 4, n >>= 4; : if (n & 0xc) : i = 2, n >>= 2; : return (i  (n >> 1)); : } : : /* : It is obviously hardwired to longs of 32 bits or less, and hence is an : utter, horrid kludge. The principle is obvious enough that you should be : able to fix it in a jiffy, if you so desire. : */ The following should adjust to any number of bits, so long as you round up ULONG_BIT to a power of two. For example, if an unsigned long has 34 bits, #define ULONG_BIT as 64. #define ULONG_BIT (32) int hibit(unsigned long n) { int h=1,i=ULONG_BIT; unsigned long m=1; if(n)for(h=0;i/=2;n&(m^=m>>i)&&(n&=m,h+=i)); return h; } It is possible to find the highest bit without any logical conditionals (bitwise/arithmetic operations only), but I doubt such a method would be much faster than either of the above.  Mathew Hendry (actually at vissci.com, not dev.null) 

Sat, 16 Dec 2000 03:00:00 GMT 


Siemel Nar #9 / 19

sizeof without sizeof
Quote:
>: /* Log base 2 estimator */ >: int qlog2(unsigned long n) >: { >: register int i = (n & 0xffff0000) ? 16 : 0; >: if ((n >>= i) & 0xff00) >: i = 8, n >>= 8; >: if (n & 0xf0) >: i = 4, n >>= 4; >: if (n & 0xc) >: i = 2, n >>= 2; >: return (i  (n >> 1)); >: }
Since some architectures support only single bit shifts, an instruction like x>>16 actually takes 16 cycles. This means that the worst case running time of the above is still O(N), where N is the number of bits in a byte. However, on architectures that support multiple bit shifts, the above will be O(lg(N)). Quote: >The following should adjust to any number of bits, so long as you >round up ULONG_BIT to a power of two. For example, if an unsigned long >has 34 bits, #define ULONG_BIT as 64.
Can also use const ULONG_BIT=2*sizeof(int); as the constants are (usually) hard coded are compile time. This one is really hard to read. The init part of the for loop sets up variable "h", the comparison part doesn't access "h" directly, and the the increment part does more than just increment "h". Quote: > #define ULONG_BIT (32) > int > hibit(unsigned long n) { > int h=1,i=ULONG_BIT; > unsigned long m=1; > if(n)for(h=0;i/=2;n&(m^=m>>i)&&(n&=m,h+=i)); > return h; > }
 


Sat, 16 Dec 2000 03:00:00 GMT 


Ben Pfaf #10 / 19

sizeof without sizeof
>: /* Log base 2 estimator */ >: int qlog2(unsigned long n) >: { >: register int i = (n & 0xffff0000) ? 16 : 0; >: if ((n >>= i) & 0xff00) >: i = 8, n >>= 8; >: if (n & 0xf0) >: i = 4, n >>= 4; >: if (n & 0xc) >: i = 2, n >>= 2; >: return (i  (n >> 1)); >: } Since some architectures support only single bit shifts, an instruction like x>>16 actually takes 16 cycles. This means that the worst case running time of the above is still O(N), where N is the number of bits in a byte. However, on architectures that support multiple bit shifts, the above will be O(lg(N)). [I'm coming into this thread late, so forgive me if this has already been suggested.] It seems to me that a binary search would work in lg(N) time regardless of processor architecture. However, the constant additive term and constant multiplier (A + B*lg(N)) might make it slower than a similar bitwise method. You might note that I have successfully used a similar technique to estimate log10(N) for numbers between 0 and 1e40, faster than the library log10() function (of course, this is processor dependent). The following code, for your amu{*filter*}t, is from GNU PSPP 0.1.19. It's ANSI, at least if you assume that finite() can be written in terms of +/ HUGE_VAL: /* I played with different implementations of this routine for more than a week, 'til I was blue in the face. Let's instead rely on the underlying implementation of sprintf: 1. If the number has a magnitude 1e40 or greater, then we needn't bother with it, since it's guaranteed to need processing in scientific notation. 2. Otherwise, do a binary search for the base10 magnitude of the thing. log10() is not accurate enough, and the alternatives are frightful. Besides, we never need as many as 6 (pairs of) comparisons. 3. The algorithm used for searching is Knuth's Algorithm 6.2.1C (Uniform binary search). Look it up in _The Art of Computer Programming_if you don't own it, why not? You should! DON'T CHANGE ANYTHING HERE UNLESS YOU'VE THOUGHT ABOUT IT FOR A LONG TIME! The rest of the program is heavily dependent on specific properties of this routine's output. LOG ALL CHANGES! FIXME? Another possible implementation would simply, after testing for magnitude > 1e40, sprintf with %f, then postprocess. Might be _a_lot_ simpler, but there are many pitfalls in this routine. */ static void convert_F (const fmt_spec *fp, double v) { /* Used for determining whether v is between two powers of 10. This is Ki, 1<=i<=40, from Knuth. */ static const double tab[] = { 0, 1e01, 1e02, 1e03, 1e04, 1e05, 1e06, 1e07, 1e08, 1e09, 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, 1e20, 1e21, 1e22, 1e23, 1e24, 1e25, 1e26, 1e27, 1e28, 1e29, 1e30, 1e31, 1e32, 1e33, 1e34, 1e35, 1e36, 1e37, 1e38, 1e39, 1e40, }; /* This is the DELTA array from Knuth. DELTA[j] = floor((40+2**(j1))/(2**j)). */ static const int delta[8] = { 0, (40 + 1) / 2, (40 + 2) / 4, (40 + 4) / 8, (40 + 8) / 16, (40 + 16) / 32, (40 + 32) / 64, (40 + 64) / 128, }; /* The number of digits in floor(v), including sign. This is `i' from Knuth. */ int nint = (40 + 1) / 2; /* Used to step through delta[]. This is `j' from Knuth. */ int j = 2; /* Magnitude of v. This is `K' from Knuth. */ double mag; /* Number of characters for the fractional part, including the decimal point. */ int ndec; /* Pointer into buf used for formatting. */ char *cp; /* Used to count characters formatted by nsprintf(). */ int n; #if DEBUGGING static int seq = 0; seq++; #endif /* First check for infinities and NaNs. 12/13/96. */ if (!finite (v)) { n = nsprintf (buf, "%f", v); if (n == fp>w) return; else if (n > fp>w) memset (buf, '*', fp>w); else { memmove (&buf[fp>w  n], buf, n); memset (buf, ' ', fp>w  n); } return; } /* Then check for radically outofrange values. */ mag = fabs (v); if (mag >= tab[fp>w]) goto scientific; if (mag < 1.0) { nint = 0; /* Avoid printing `.000'. 7/6/96. */ if (approx_eq (v, 0.0)) v = 0.0; } else /* Now perform a `uniform binary search' based on the tables tab[] and delta[]. After this step, nint is the number of digits in floor(v), including any sign. */ while (1) { if (mag >= tab[nint]) /* Should this be approx_ge()? */ { assert (delta[j]); nint += delta[j++]; } else if (mag < tab[nint  1]) { assert (delta[j]); nint = delta[j++]; } else break; } [...this is the end of the at least semiinteresting code...]  (supporter of the campaign for grumpiness where grumpiness is due in c.l.c) Please: do not email me copies of your posts to comp.lang.c do not ask me C questions via email; post them instead

Sat, 16 Dec 2000 03:00:00 GMT 


Lawrence Kir #11 / 19

sizeof without sizeof
Quote:
> >: /* Log base 2 estimator */ > >: int qlog2(unsigned long n) > >: { > >: register int i = (n & 0xffff0000) ? 16 : 0; > >: if ((n >>= i) & 0xff00) > >: i = 8, n >>= 8; > >: if (n & 0xf0) > >: i = 4, n >>= 4; > >: if (n & 0xc) > >: i = 2, n >>= 2; > >: return (i  (n >> 1)); > >: } > Since some architectures support only single bit shifts, an instruction > like x>>16 actually takes 16 cycles. This means that the worst case > running time of the above is still O(N), where N is the number of bits > in a byte. However, on architectures that support multiple bit shifts, > the above will be O(lg(N)).
O notation models the behaviour as N approaches infinity so it can't sensibly be applied to a small problem like this. This breaks down once you exceed the machine register size. Quote: >[I'm coming into this thread late, so forgive me if this has already >been suggested.] >It seems to me that a binary search would work in lg(N) time >regardless of processor architecture.
That assumes that each step takes constant time. The point being made is that here that isn't necessarily the case (although with moderm processors it usually is). Quote: > However, the constant additive >term and constant multiplier (A + B*lg(N)) might make it slower than a >similar bitwise method. >You might note that I have successfully used a similar technique to >estimate log10(N) for numbers between 0 and 1e40, faster than the >library log10() function (of course, this is processor dependent).
One function that might well be usefully employed in this sort of situation is frexp(). Of course how fast it will be is platformspecific. Potentially all it has to do is split out the exponent and mantissa parts of a floating point value so it could be very fast.  


Sat, 16 Dec 2000 03:00:00 GMT 


Mathew Hend #12 / 19

sizeof without sizeof
Quote:
> >: /* Log base 2 estimator */ > >: int qlog2(unsigned long n) > >: { > >: register int i = (n & 0xffff0000) ? 16 : 0; > >: if ((n >>= i) & 0xff00) > >: i = 8, n >>= 8; > >: if (n & 0xf0) > >: i = 4, n >>= 4; > >: if (n & 0xc) > >: i = 2, n >>= 2; > >: return (i  (n >> 1)); > >: } > Since some architectures support only single bit shifts,
Hmm, which ones, just out of interest? Quote: > an instruction > like x>>16 actually takes 16 cycles. This means that the worst case > running time of the above is still O(N), where N is the number of bits > in a byte.
If you're worried about shifts, use masks instead, int qlog2_mask1(unsigned long n) { int h=0; unsigned long m; if (n&(m=0xffff0000UL)) n&=m,h+=16; if (n&(m=0xff00ff00UL)) n&=m,h+= 8; if (n&(m=0xf0f0f0f0UL)) n&=m,h+= 4; if (n&(m=0xccccccccUL)) n&=m,h+= 2; if (n&(m=0xaaaaaaaaUL)) h+= 1; return h; } On, the other hand, if the loading of large constants is a problem, you can generate the masks on the fly, int qlog2_mask2(unsigned long n) { int h=0; unsigned long m=1; if (n&(m^=m>>16)) n&=m,h+=16; if (n&(m^=m>> 8)) n&=m,h+= 8; if (n&(m^=m>> 4)) n&=m,h+= 4; if (n&(m^=m>> 2)) n&=m,h+= 2; if (n&(m^=m>> 1)) h+= 1; return h; } This is emenable to rewriting as a loop, int qlog2_loop1( unsigned long n ) { int h=0,i=32; unsigned long m=1; while (i/=2) if (n&(m^=m>>i)) n&=m,h+=i; return h; } With a bit more twiddling, and the addition of a test for allbitszero, you might end up with something like, Quote: > > #define ULONG_BIT (32) > > int > > hibit(unsigned long n) { > > int h=1,i=ULONG_BIT; > > unsigned long m=1; > > if(n)for(h=0;i/=2;n&(m^=m>>i)&&(n&=m,h+=i)); > > return h; > > }
:) BTW, here's another approach, with no branches. It's rather brute force, ugly, and pretty slow. Can anyone improve it? int hi_bit11(unsigned long n){ int i=16; unsigned long m=0xffffUL; /* table for modulo trick */ static const int t[]={ 1,31,6,30,9,5,0,29,16,8,2,4,21,1,19,28,25,15,1,7, 10,1,17,3,22,20,26,1,11,18,23,27,12,24,13,14,1}; /* reverse bits (ugh) */ n=n>>i&m(n&m)<<i,i/=2, m^=m<<i,n=n>>i&m(n&m)<<i,i/=2, m^=m<<i,n=n>>i&m(n&m)<<i,i/=2, m^=m<<i,n=n>>i&m(n&m)<<i,i/=2, m^=m<<i,n=n>>i&m(n&m)<<i; /* xor / modulo trick */ return t[(n^(n1))%37]; }  Mat.

Sun, 17 Dec 2000 03:00:00 GMT 


Siemel Nar #13 / 19

sizeof without sizeof
Quote: >> Since some architectures support only single bit shifts, >Hmm, which ones, just out of interest?
Don't know. BTW, I've found a way to do it in O(lg(N)) operations (~5 operations if sizeof(int)=4) period! Basically, you expand out the if loop, making an explicit binary comparison tree in the process. No bit shifts. For example, if sizeof(int)=1, then base2::logdown(int num) is int lg; if (num&0xf0) { if (num&0xc0) { if (num&0x80) return 7; return 6; } if (num&0x20) return 5; return 4; } if (num&0xc) { if (num&0x08) return 3; return 2; } if (num&0x2) { return 1; } if (num&0x1) return 0; return 1; In the production code, we make a switch on sizeof(int). Since sizeof(int) is known at compile time, the optimzer will optimize away dead code! int base2::logdown(int num) { switch (sizeof(int)) { case 4: return ... case 2: return ... } //default algorithm Quote: }
 


Sun, 17 Dec 2000 03:00:00 GMT 


Lawrence Kir #14 / 19

sizeof without sizeof
Quote: >>> Since some architectures support only single bit shifts, >>Hmm, which ones, just out of interest? >Don't know. >BTW, I've found a way to do it in O(lg(N)) operations (~5 operations >if sizeof(int)=4) period! Basically, you expand out the if loop, >making an explicit binary comparison tree in the process. No >bit shifts. >For example, if sizeof(int)=1, then base2::logdown(int num) is
Even if sizeof(int) is 1 it must still be at least 16 bits wide. sizeof produces a count in terms of bytes or character. A byte in C can consist of 8 *or more* bits. So for example above sizeof(int)=4 does not imply that an int is 32 bits wide (it is at least 32 bits wide in that case). Quote: > int lg; > if (num&0xf0) { if (num&0xc0) { if (num&0x80) return 7; > return 6; } if (num&0x20) return 5; return 4; } > if (num&0xc) { if (num&0x08) return 3; return 2; } > if (num&0x2) { return 1; } > if (num&0x1) return 0; > return 1;
This code would be a lot easier to read if you formatted it sensibly. A problem with many modern processors is that branch misprediction can cost heavily.  


Sun, 17 Dec 2000 03:00:00 GMT 


Page 1 of 2

[ 19 post ] 

Go to page:
[1]
[2] 
