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.

Thanks ahead.

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

es*****@acm-dot-org.invalid