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.

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

  2. fermineutron

    fermineutron Guest

    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?
    fermineutron, Nov 4, 2006
    #2
    1. Advertising

  3. 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 to the upper bits of
    X[i-1] */
    X[i-1] |= X << (8*sizeof(unsigned long) - 5);
    X >>=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.
    Chris Johnson, Nov 4, 2006
    #3
  4. fermineutron

    Eric Sosman Guest

    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
    lid
    Eric Sosman, Nov 4, 2006
    #4
  5. fermineutron

    fermineutron Guest

    Thanks everyone,
    all replies were very helpfull.
    fermineutron, Nov 4, 2006
    #5
  6. > Also is there a way to determine the count of the most significant
    > non-zero bit in a variable?



    http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn


    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.
    Samuel Stearley, Nov 5, 2006
    #6
  7. Chris Johnson wrote:
    > 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;
    > }


    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 * ((-1ul >> 5) + 1);
    X >>=5;
    }

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

    --
    Peter
    Peter Nilsson, Nov 6, 2006
    #7
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Matthew Wilson

    iterating bit-by-bit across int?

    Matthew Wilson, Oct 23, 2003, in forum: Python
    Replies:
    12
    Views:
    518
    Brian Kelley
    Oct 25, 2003
  2. Reid Nichol
    Replies:
    11
    Views:
    1,150
    Francesco Bochicchio
    Sep 11, 2004
  3. Ross A. Finlayson
    Replies:
    19
    Views:
    570
    Keith Thompson
    Mar 10, 2005
  4. gamehack

    Bit shifts and endianness

    gamehack, Jan 5, 2006, in forum: C Programming
    Replies:
    72
    Views:
    6,771
    Dave Thompson
    Jan 11, 2006
  5. geo

    Be cautious when iterating bit-shifts

    geo, Nov 16, 2009, in forum: C Programming
    Replies:
    4
    Views:
    366
    Phil Carmody
    Nov 21, 2009
Loading...

Share This Page