Re: fast bit rotation
- Posted by jiri babor <jbabor at paradise.net.nz> Jan 01, 2004
- 451 views
Derek wrote: >Doesn't the INTEGER type only support 30-bit integers? I make the range for INTEGER types to be from (-power(2,30)) to (power(2,30) - 1). It seems that Euphoria uses 30-bits to hold the value, one bit to hold the sign and the 32nd bit to hold the flag to tell if its an integer or something else? Just guessing. I guess it's just semantics. Commonly we talk about 32-bit integers, not 31, even when all 32 bits are used to hold *signed* integers in just about any other language. >And thank you, Robert, for your explanation. I still think any self-respecting language should have fast shifts and rotations built into it. Why is this Jiri? I would have thought that they are only a few programming problems where bit shifting/rotating is of much use. Low-level device interfacing, cryptography, image/audio manipulating, low-RAM environments (8-bit embedded systems), ... I suppose it depends on your hobby. One of mine happens to be data compression, which you left out of your otherwise good account. In many algorithms, especially for lossless compression, you fiddle bits all the time. I know it's a well trodden turf, but still pretty interesting. >What are you working on that needs it? After a couple of years I resurrected my 'dream language' project that I am sketching in Euphoria. For that I need fast tables. In the past I used sorted tables with binary searches. Now I want to try hashed tables, and at the moment I am evaluating several faster hashing algorithms. Many of them use shifts and/or rotations to introduce some extra noise into the hashing functions to achieve more even bucket distribution. I have already one or two really interesting and reasonably flexible schemes going, probably good enough for general consumption - but only after a bit more testing... jiri