«

"Richard G. Riley" <> writes:
[snip]
> Cant assume that : CHAR_BIT will be 8 or so and sizeof(int) will be 4,
> but KT pointed out that maximum unsigned int might still be 32767
> due to padding bits.

Not quite. The standard guarantees that UINT_MAX is at least 65535.

--
Keith Thompson (The_Other_Keith) kst- <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

On 2006-03-14, Keith Thompson <kst-> wrote:
> "Richard G. Riley" <> writes:
> [snip]
>> Cant assume that : CHAR_BIT will be 8 or so and sizeof(int) will be 4,
>> but KT pointed out that maximum unsigned int might still be 32767
>> due to padding bits.
>
> Not quite. The standard guarantees that UINT_MAX is at least 65535.
>

whoops, sorry : brain off there.

Richard G. Riley said:

> On 2006-03-14, Keith Thompson <kst-> wrote:
>> "Richard G. Riley" <> writes:
>> [snip]
>>> Cant assume that : CHAR_BIT will be 8 or so and sizeof(int) will be 4,
>>> but KT pointed out that maximum unsigned int might still be 32767
>>> due to padding bits.
>>
>> Not quite. The standard guarantees that UINT_MAX is at least 65535.
>>
>
> whoops, sorry : brain off there.

It seems you have discovered the ability to apologise for your mistakes. I
suggest you develop that skill further.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

"Richard G. Riley" <> writes:
> But any techniques for doing the standard bit fiddles without
> occurring extra unnecessary cpu bandwidth would be nice. By standard
> bit fiddles I mean : shift & rotate, anding, oring, shift til bit
> found etc. The operations will be occurring on sequences of
> words and the smallest word will be the standard CPU word size (32
> bits). By sequences of words : I might, for example, be locating
> the first non zero bit from the left in sequence of 64 words.

Slightly off-topic, POSIX has ffs(), which returns the index of the
first non-zero bit in an int. Compare each int with zero, in
sequence, and sic ffs() at the first non-zero one. Presumably, your
implementation will translate the call to ffs() into the most
efficient instruction sequence for your platform; on some systems, it
maps to a single CPU instruction.

As for regular "shift & rotate, anding, oring", if your implementation
does not translate the equivalent C operators into efficient machine
code, you'd better find another one that does.

DES
--
Dag-Erling Smørgrav -

Richard G. Riley schrieb:
> On 2006-03-14, Michael Mair <> wrote:
>>Richard G. Riley schrieb:
>>>On 2006-03-13, Keith Thompson <kst-> wrote:
>>>>"Richard G. Riley" <> writes:
>>>>>On 2006-03-13, Keith Thompson <kst-> wrote:
>>>>>>It's guaranteed that, for any integer type, all-bits-zero is a
>>>>>>representation of the value 0. (Neither the C90 nor the C99 standard
>>>>>>says this, but n1124 does; this change was made in TC2 in response to
>>>>>>DR #263. I've never heard of an implementation that doesn't have this
>>>>>>property anyway, and I'd be comfortable depending on it.) For
>>>>>>one's-complement and sign-magnitude representations, there are two
>>>>>>distinct representations of zero (+0 and -0), but you can avoid that
>>>>>>by using an unsigned type. But unsigned types *can* have padding
>>>>>>bits, so even if buf[i]==0, you might still have missed a 1 bit.
>>>>>
>>>>>Could you please explain this? If I have calculated (or even knw..) that the
>>>>>underlying word size is 32 bit and I use an unsigned int to represent
>>>>>this in C, then how do padding bits make any difference? Isnt the
>>>>>variable guarenteed to go from 0 to 2^32-1?
>>>>
>>>>No, it isn't. The guaranteed range of unsigned int is 0 to 32768.
>>>>But, for example, an implementation could legally have:
>>>> CHAR_BIT == 8
>>>> sizeof(unsigned int) == 4
>>>> INT_MAX == 32767
>>>>An unsigned int then has 32 bits: 16 value bits and 16 padding bits.
>>>>
>>>>For details, see section 6.2.6.2 of the C99 standard.
>>>
>>>Wow. That would break a lot of code. Assumimg some situation like
>>>that, is their a constant "MAX BITS FOR ULONG" or "MAX WORD SIZE IN BITS"? e.g
>>>to get a platform independant assurance of the number of bits one can
>>>use in a single HW word? Having said that, in my sample code in the
>>>initial reply to Eric, I would only need to recalculate my "start
>>>mask" from 0x80000000 to "whatever" when I calculate "usable bits per
>>>HW word" in program init. Since the overhead of doing that calc is
>>>almost less than zero compared to cother computation, I could do that.
>>
>>If you intend "fast and portable", then consider doing the
>>following:
>
> That is the best. My initial requirements are slightly smaller : fast
> on x86 as I originally specified and "works elsewhere when it might be
> needed the day hell freezes over" .-; Having said that, I have taken
> Thomsons comments to heart about word padding for some reason : I see
> no real overhead (when keeping everything in C) to ensure platform
> compatability in the C level. It will be, I admit, the first code I
> ever wrote where a machine word can potentially hold less values than
> its size indicates : unless of course I do come across an unforseen
> performance hit in which case bye bye good practice.
>
>>Build a "guaranteedly portable" version of your intended to be fast
>>stuff.
>>Then start documenting your assumptions for your "fast header": Add a
>>source file which is not linked with the rest of the code but fails
>>compilation (during preprocessing or actual compiling) if one of
>>these assumptions is violated.
>>Say you have determined that sizeof(int)*CHAR_BIT is 32 Bits, then
>>0xFFFFFFFF - INT_MAX should be 0. In other words, neither
>> char inttestl[0x7FFFFFFF - (long)INT_MAX + 1L];
>
> Cant assume that : CHAR_BIT will be 8 or so and sizeof(int) will be 4,
> but KT pointed out that maximum unsigned int might still be 32767
> due to padding bits..I asked for an easy way to determine "usable bit
> size" but got no reply so I guess its just some code to do at
> init. Not too far up on the priority list I must admit though.

Apart from the one excess "unsigned": My point here is that
you well may assume no padding, 2s complement and everything
that makes life easy as long as you can guarantee that your
code will not compile if these assumptions are invalid.
Writing code to cater for every possible situation the standard
permits may be a noble goal to aim at but will definitely not
_help_ you with the "fast" part (*).
Thus the portable version to have in your hand for testing the
fast version and for having fallback code. If you program it at
the same time as the rest, you do not waste much time -- but
it will save you much time if you need it (and don't have to
remember what all of this was supposed to do); and maybe even
earlier, when testing the fast version against the bulletproof
version...
____
(*) It is possible that it won't hinder you either.


Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.