Velocity Reviews > bit shifts across array elements

# bit shifts across array elements

fermineutron
Guest
Posts: n/a

 11-04-2006
Lets say i have array

unsigned long X[4];

Now, i want to shift right bits in the array by 5. that is the lowest 5
bits of element N will become the highest 5 bits of element N-1. the
lowest 5 bits of 0th element are lost.

what is the best way to do this?

My C reference book does not go in detail on preserving the bits which
are lost during bitshifts.

X[3]=X[3]>>5;
but what is X[2] in this case?

Also is there a way to determine the count of the most significant
non-zero bit in a variable?
for example in the case

0010010101010010

answer would be 14. This can be done by repeatedly testing the variable
storing above value against 2^N untill 2^N is greater than X. The count
of most significant bit would be N-1, assuming the right ost bit is in
0th position, but is there a more efficient way to do this?

In both cases timing is critical.

fermineutron
Guest
Posts: n/a

 11-04-2006

fermineutron wrote:
> Lets say i have array
>
> unsigned long X[4];
>
> Now, i want to shift right bits in the array by 5. that is the lowest 5
> bits of element N will become the highest 5 bits of element N-1. the
> lowest 5 bits of 0th element are lost.
>
> what is the best way to do this?
>
> My C reference book does not go in detail on preserving the bits which
> are lost during bitshifts.
>
> X[3]=X[3]>>5;
> but what is X[2] in this case?
>
> Also is there a way to determine the count of the most significant
> non-zero bit in a variable?
> for example in the case
>
> 0010010101010010
>
> answer would be 14. This can be done by repeatedly testing the variable
> storing above value against 2^N untill 2^N is greater than X. The count
> of most significant bit would be N-1, assuming the right ost bit is in
> 0th position, but is there a more efficient way to do this?
>
> In both cases timing is critical.
>

I guess i could do the following to determine most significan non-zero
bit count:
T stores the value to be tested.
n=0;
while(T>0){
T=T>>1;
n++;
}

is there a beter way?

Chris Johnson
Guest
Posts: n/a

 11-04-2006

fermineutron wrote:
> Lets say i have array
>
> unsigned long X[4];
>
> Now, i want to shift right bits in the array by 5. that is the lowest 5
> bits of element N will become the highest 5 bits of element N-1. the
> lowest 5 bits of 0th element are lost.
>
> what is the best way to do this?
>
> My C reference book does not go in detail on preserving the bits which
> are lost during bitshifts.
>
> X[3]=X[3]>>5;
> but what is X[2] in this case?

X[0] >>= 5;
int i;
for(i = 1; i < arraylen; i++){
/* Move the least significant bits of X[i] to the upper bits of
X[i-1] */
X[i-1] |= X[i] << (8*sizeof(unsigned long) - 5);
X[i] >>=5;
}

> Also is there a way to determine the count of the most significant
> non-zero bit in a variable?
> for example in the case
>
> 0010010101010010
>
> answer would be 14. This can be done by repeatedly testing the variable
> storing above value against 2^N untill 2^N is greater than X. The count
> of most significant bit would be N-1, assuming the right ost bit is in
> 0th position, but is there a more efficient way to do this?

I use the following:

for(i = 0;n >> i; i++);

i is now the position of the most significant bit (assuming the far
right is bit 1)

> In both cases timing is critical.
>

Eric Sosman
Guest
Posts: n/a

 11-04-2006
fermineutron wrote:
> fermineutron wrote:
>
>>Lets say i have array
>>
>>unsigned long X[4];
>>
>>Now, i want to shift right bits in the array by 5. that is the lowest 5
>>bits of element N will become the highest 5 bits of element N-1. the
>>lowest 5 bits of 0th element are lost.
>>
>>what is the best way to do this?
>>
>>My C reference book does not go in detail on preserving the bits which
>>are lost during bitshifts.
>>
>>X[3]=X[3]>>5;
>>but what is X[2] in this case?
>>
>>Also is there a way to determine the count of the most significant
>>non-zero bit in a variable?
>>for example in the case
>>
>>0010010101010010
>>
>>answer would be 14. This can be done by repeatedly testing the variable
>>storing above value against 2^N untill 2^N is greater than X. The count
>>of most significant bit would be N-1, assuming the right ost bit is in
>>0th position, but is there a more efficient way to do this?
>>
>>In both cases timing is critical.
>>

>
>
> I guess i could do the following to determine most significan non-zero
> bit count:
> T stores the value to be tested.
> n=0;
> while(T>0){
> T=T>>1;
> n++;
> }
>
> is there a beter way?

Maybe. Timings are highly machine-dependent, and a technique
that whizzes on one system may wheeze on another. A few ideas:

1) If you know the number of bits in a T-type value you can
do a binary search. For example, if T is a sixteen-bit unsigned
integer you could do

int n = 0;
if (T > 0x00FF) { n = 8; T >>= 8; }
if (T > 0x000F) { n += 4; T >>= 4; }
if (T > 0x0003) { n += 2; T >>= 2; }
n += T >> 1;

1a) Even if you don't know the number of bits but do know a
lower bound, you can use a "big bite" linear search followed by
a binary search as above. For example, if T is an unsigned integer
known to be at least sixteen bits wide but possibly wider,

int n = 0;
while (T > 0xFFFF) { n += 16; T >>= 16; }
/* ... followed by binary search as above */

2) Use a "big bite" linear search to reduce T to a convenient
range and then index a precomputed table with the reduced T.

3) A trick mentioned on this forum within the past few weeks:
Convert T to a floating-point type and extract the exponent.

Before spending much time on these or any other alternatives,
be sure you have solid *evidence* for the criticality of the
timing. Suspicion is not enough.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid

fermineutron
Guest
Posts: n/a

 11-04-2006
Thanks everyone,

Samuel Stearley
Guest
Posts: n/a

 11-05-2006
> Also is there a way to determine the count of the most significant
> non-zero bit in a variable?

http://graphics.stanford.edu/~seande...gerLogDeBruijn

fermineutron wrote:
> Lets say i have array
>
> unsigned long X[4];
>
> Now, i want to shift right bits in the array by 5. that is the lowest 5
> bits of element N will become the highest 5 bits of element N-1. the
> lowest 5 bits of 0th element are lost.
>
> what is the best way to do this?
>
> My C reference book does not go in detail on preserving the bits which
> are lost during bitshifts.
>
> X[3]=X[3]>>5;
> but what is X[2] in this case?
>
> Also is there a way to determine the count of the most significant
> non-zero bit in a variable?
> for example in the case
>
> 0010010101010010
>
> answer would be 14. This can be done by repeatedly testing the variable
> storing above value against 2^N untill 2^N is greater than X. The count
> of most significant bit would be N-1, assuming the right ost bit is in
> 0th position, but is there a more efficient way to do this?
>
> In both cases timing is critical.
>

Peter Nilsson
Guest
Posts: n/a

 11-06-2006
Chris Johnson wrote:
>
> X[0] >>= 5;
> int i;
> for(i = 1; i < arraylen; i++){
> /* Move the least significant bits of X[i] to the upper bits
> of X[i-1] */
> X[i-1] |= X[i] << (8*sizeof(unsigned long) - 5);
> X[i] >>=5;
> }

The restriction of unpadded integers and 8 bit bytes only is
unnecessary...

X[0] >>= 5;
for(i = 1; i < arraylen; i++)
{
X[i-1] |= X[i] * ((-1ul >> 5) + 1);
X[i] >>=5;
}

[Many compilers will optimise the * to a shift, so you gain portability
without losing efficiency.]

--
Peter