sizeof without sizeof 
Author Message
 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 re-read 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  
 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 PII-300)

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<<bits-1)<<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  
 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  
 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 PII-300)

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<<bits-1)<<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  
 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 re-read 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  
 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 hard-coded at compile time.

But maybe there's a better way?

--
----------------------------------

----------------------------------



Fri, 15 Dec 2000 03:00:00 GMT  
 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 C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
C-FAQ ftp: ftp://rtfm.mit.edu, C-FAQ Book: ISBN 0-201-84519-9
Try "C Programming: A Modern Approach" ISBN 0-393-96945-2
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 hard-coded at compile time.

>But maybe there's a better way?

>--
>----------------------------------

>----------------------------------



Fri, 15 Dec 2000 03:00:00 GMT  
 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  
 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  
 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 base-10 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**(j-1))/(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 out-of-range 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 semi-interesting 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  
 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 platform-specific.
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  
 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 all-bits-zero, 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^(n-1))%37];
  }

-- Mat.



Sun, 17 Dec 2000 03:00:00 GMT  
 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  
 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  
 
 [ 19 post ]  Go to page: [1] [2]

 Relevant Pages 

1. relation between sizeof(void*), sizeof(int)

2. sizeof (struct) ! = sizeof struct elements

3. sizeof a/sizeof *a

4. sizeof(foo) -1 or sizeof(foo)

5. sizeof(void*) versus sizeof(foo*)

6. sizeof(int) sizeof(long) etc.

7. sizeof Object without memeber variable

8. coding style advice for sizeof (long) < sizeof (size_t)?

9. sizeof (pointer to array)/sizeof (p[0]) how to use ?

10. sizeof a char * [] passed to function

11. sizeof() problem

12. /Wp64 and sizeof int question

 

 
Powered by phpBB® Forum Software