Seebs said:
If you need a branch for this, you've done it wrong.
Perhaps... I was starting to wonder if there is a better way than using a
lookup table.
Today is a new today with a fresh look at things
Now that the basic algorithm is done it's easier to see where problems might
be.
There are two or three different problems which are slightly different from
each other.
1. The first problem is calculating a mask to represents all one's for the
lowest bits up to bitcount.
So if bitcount is 5, bits 0 to 4 most be set.
Bit count can go up to 32 for a longword.
Bit count could even go up to 64 for a int64. But this case can be ignored
for now.
So the limit of bit count 32 is good enough for now.
Since shr 32 and shl 32 is not possible a solution is needed. A fast one too
for that matter.
Noone has yet provided one in there examples, perhaps because the examples
where limited to 16 bit words.
Anyway since there are only 5 bits available for shl and shr there is a
logical problem for intel:
"Do we support range 0 to 31 or do we support range 1 to 32 ?"
Intel choose to support range 0 to 31.
Logically/interestingly shr 0 and shl 0 do absolutely nothing !
Yet I have heard nobody complain about this apperently lack of
functionality, which is just as useless as doing shr 32 and shl 32...
The last could have even been more usefull but ok. Depends on the situation
perhaps.
The conclusion therefore can be/most be that shr 0 and shl 0 are usefull
after all !
If "we" can wrap around the bitcount from 32 back to 0 than at least we will
prevent "garbage".
Now the question is, is it usefull to wrap around ? This will probably
depend on the code and the situation.
So let's examine it:
The technique used so far to calculate a mask is to set the mask initially
to all one's as follows:
1111111-32-one's-11111111
Depending on the bit count this masks needs to be shifted left. If bitcount
is 1 the mask should have all one's except one zero as follows:
1111111-31 one's-11111110
The zero will represent the content bit later on. It's clear to me that with
the current masking formula only 31 bits can be shifted out.
Example: (1 shl 31)-1 = 0111 1111 1111 1111 1111 1111 1111 1111
(I just found a nice button on the windows calculator it's called Lsh (Left
shift I guess) it can be used to do these calculations... nice)
The problem is clear: the last bit is missing.
I was thinking, maybe a "bitcount mod 32" might help so let's see what
happens:
32 mod 32 would become zero.
The formula will be:
not ( -1 shl 0 );
-1 shl 0 = -1
-1 = all bits set.
not (-1) = must therefore be logically all bits cleared.
This is not what we want... we want all bits set for a bitcount of 32.
Therefore there is clearly a problem.
So we need a different solution.
The algorithm exits on bitcount 0 so the mask of all one's is therefore
useless.
Perhaps the mask can be changed as follows:
not ( -2 shl ? );
This would assume bitcount is always 1 or greater.... therefore we can
subtract 1 from the bitcount.
the formula would then be:
not ( -2 shl (BitCount-1) )
Now let's see if this works for BitCount 1, 5 and 32 as verifications.
Case 1: not ( -2 shl (1-1) ) = not ( - 2 shl 0 ) = not(-2)
Logically all bits are set except the last one. (Assuming two complements
computers, have a nice time figuring out how to support it in "portable C"
)
Therefore it gets changed into: etc0000000000001
Which is indeed what we want.
Now let's continue with the 32.
Case 32: not( -2 shl (32-1) ) = not ( -2 shl 31 )
Logically all bits will be pushed out except the first one...
So I would expect it to be all zero's... notting all zero's gives a mask of
all one's.
Which is what we want.
For now the problem with "masking" seems to be solved.
However the problem for shifting "content" still needs to be looked. I am
not yet sure if it can be solved.
Bye,
Skybuck.
