bit shifts across array elements

Discussion in 'C Programming' started by fermineutron, Nov 4, 2006.

  1. fermineutron

    fermineutron Guest

    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.

    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


    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.
    fermineutron, Nov 4, 2006
    1. Advertisements

  2. fermineutron

    fermineutron Guest

    I guess i could do the following to determine most significan non-zero
    bit count:
    T stores the value to be tested.

    is there a beter way?
    fermineutron, Nov 4, 2006
    1. Advertisements

  3. How about:

    X[0] >>= 5;
    int i;
    for(i = 1; i < arraylen; i++){
    /* Move the least significant bits of X to the upper bits of
    X[i-1] */
    X[i-1] |= X << (8*sizeof(unsigned long) - 5);
    X >>=5;
    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)
    Chris Johnson, Nov 4, 2006
  4. fermineutron

    Eric Sosman Guest

    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, Nov 4, 2006
  5. fermineutron

    fermineutron Guest

    Thanks everyone,
    all replies were very helpfull.
    fermineutron, Nov 4, 2006
  6. Also is there a way to determine the count of the most significant

    Samuel Stearley, Nov 5, 2006

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

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

    [Many compilers will optimise the * to a shift, so you gain portability
    without losing efficiency.]
    Peter Nilsson, Nov 6, 2006
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.