446,148 Members | 1,282 Online
Need help? Post your question and get tips & solutions from a community of 446,148 IT Pros & Developers. It's quick & easy.

# bit shifts across array elements

 P: n/a 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. Nov 4 '06 #1
6 Replies

 P: n/a 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? Nov 4 '06 #2

 P: n/a 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? How about: 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. Thanks ahead. Nov 4 '06 #3

 P: n/a fermineutron wrote: fermineutron wrote: >>Lets say i have arrayunsigned long X[4];Now, i want to shift right bits in the array by 5. that is the lowest 5bits of element N will become the highest 5 bits of element N-1. thelowest 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 whichare 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 significantnon-zero bit in a variable?for example in the case0010010101010010answer would be 14. This can be done by repeatedly testing the variablestoring above value against 2^N untill 2^N is greater than X. The countof most significant bit would be N-1, assuming the right ost bit is in0th 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 Nov 4 '06 #4

 P: n/a Thanks everyone, all replies were very helpfull. Nov 4 '06 #5

 P: n/a 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. Thanks ahead. Nov 5 '06 #6

 P: n/a Chris Johnson wrote: How about: 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 Nov 6 '06 #7

### This discussion thread is closed

Replies have been disabled for this discussion.