Bitwise rotate array

This is a discussion on Bitwise rotate array within the C Programming forums, part of the General Programming Boards category; Hi Guys, First post!! I come from micro controller land where we speak RISC asm, so C has been a ...

  1. #1
    Registered User
    Join Date
    Jan 2013
    Posts
    69

    Bitwise rotate array

    Hi Guys,
    First post!!
    I come from micro controller land where we speak RISC asm,
    so C has been a little difficult to grasp when it comes to dealing with bits.

    I was reading this thread:
    Help! I am going crazy. Bit shifting a byte array

    and got this function working:
    Code:
    void shiftl(void *object, size_t size) {
        
        unsigned char *byte;
        for ( byte = object; size--; ++byte ) {
            
        unsigned char bit = 0;
        if ( size ) {
        bit = byte[1] & (1 << (CHAR_BIT - 1)) ? 1 : 0;
        }
            
        *byte <<= 1;
        *byte  |= bit;
        }
    }
    
    The trouble I'm having is reversing it to make a new function to rotate right instead of left.
    I know that object is the beginning of the array and size is the size,
    so to shift right I should begin from object+size to make the for
    loop run backwards. I don't know what ++byte is for.

    Also, does;
    Code:
     if ( size ) {}
    mean if size does not equal zero? or greater than zero?
    I've never seen that before.
    I see where the byte is shifted, but don't understand:
    Code:
    *byte  |= bit;
    any help appreciated, thanks

  2. #2
    Registered User
    Join Date
    Mar 2011
    Posts
    546
    if (size) means 'if (size is nonzero)'. 'if' statements are true if the value is any nonzero value. they are false if the term is 0.

    a left shift puts a 0 in the first bit. the *byte |= bit is meant to put the high bit that was rotated out back into the zero position.

  3. #3
    Registered User
    Join Date
    Jan 2013
    Posts
    69
    Quote Originally Posted by dmh2000 View Post
    if (size) means 'if (size is nonzero)'. 'if' statements are true if the value is any nonzero value. they are false if the term is 0.

    a left shift puts a 0 in the first bit. the *byte |= bit is meant to put the high bit that was rotated out back into the zero position.
    Thanks
    What is "++byte" doing in the for loop?

  4. #4
    Registered User
    Join Date
    Jan 2013
    Posts
    69
    One gold star please

    Code:
    void shiftr(void *object, size_t size) {
        
        unsigned char *byte;
        for ( byte = object; size--; ++byte ) {
            
        unsigned char bit = 0;
        if ( size ) {
        bit = byte[1] & (1 >> (CHAR_BIT + 1)) ? 1 : 0;
        }
            
        *byte >>= 1;
        *byte  |= bit;
        }
    }
    

    EDIT,,,, bah! it's still not correct!
    Last edited by xArt; 01-23-2013 at 07:10 PM. Reason: oops

  5. #5
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,323
    Just for simplicity, I'll use a variable of 4 bits

    Is this what you need to do?

    (notation value[element])

    Before
    1001[0] 1101[1] 0010[2]

    after
    0100[0] 1110[1] 1001[2]


    If so, the algorithm should be easy to figure out...
    if last element was odd before being shifted, then n = (n>>1) + 1000
    otherwise n = n>>1
    Fact - Beethoven wrote his first symphony in C

  6. #6
    Registered User
    Join Date
    Jan 2013
    Posts
    69
    Yes, but looking at the results further,
    it doesn't look like the original function carries the bit that drops off the left,
    and feeds it into the right of the array, so it's not exactly what I'm after.
    If you rotate it enough, the array will end up all zeros.

    EDIT,,

    this is the big rotate I really wanted (shift left though), but I didn't do it.

    Code:
    void shiftl(void *object, size_t size) {
        
        unsigned char *byte;
        
        byte = object;  // NEW
        unsigned char leftbit = byte[1] & (1 << (CHAR_BIT - 1)) ? 1 : 0;   // NEW
        for ( byte = object; size--; ++byte ) {
            
            
            unsigned char bit = 0;
            if ( size ) {
    
    
                bit = byte[1] & (1 << (CHAR_BIT - 1)) ? 1 : 0;
            }
            else {
                bit = leftbit;  // NEW
            }  // NEW
            *byte <<= 1;
            *byte  |= bit;
        }
    }
    Last edited by xArt; 01-23-2013 at 08:39 PM.

  7. #7
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,323
    I'm having a hard time trying to figure out what you want to do.

    Can you post your most current "shiftr()" and I'll have a look at what could be going wrong.
    Fact - Beethoven wrote his first symphony in C

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    Now you've created a problem if the size of the buffer is less than 2 bytes.
    I'd remove the conditional out of the loop. The following should perform correct rotates, both intentionally processing the bytes in the same order, as you had it:
    Code:
    void shiftl(void *object, size_t size) {
        unsigned char *byte, *last;
        unsigned char firstBit;
        if (size != 0) {
            byte = object;
            last = byte + size-1;
            firstBit = byte[0] >> (CHAR_BIT-1);
            while (byte < last) {
                byte[0] = (byte[0] << 1) | (byte[1] >> (CHAR_BIT-1));
                ++byte;
            }
            (*last) = (*last) << 1 | firstBit;
        }
    }
    
    void shiftr(void *object, size_t size) {
        unsigned char *byte, *end;
        unsigned char bit, nextBit;
        if (size != 0) {
            byte = object;
            end = byte + size;
            bit = *(end-1) & 1;
            while (byte < end) {
                nextBit = byte[0] & 1;
                byte[0] = (byte[0] >> 1) | (bit << (CHAR_BIT-1));
                ++byte;
                bit = nextBit;
            }
        }
    }
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Jan 2013
    Posts
    69
    I read the rules, and thought you weren't supposed to do handouts...
    Thanks tho

    The last function posted is the most current because it feeds the bits dropped from
    the left end of the array back into the right end so it's a big rotate rather than a big shift.
    Last edited by xArt; 01-24-2013 at 01:40 AM. Reason: more

  10. #10
    Registered User
    Join Date
    Jan 2013
    Posts
    69
    Now you've created a problem if the size of the buffer is less than 2 bytes
    I feel like I'm walking into a trap, but what sort of array has one element?
    Wouldn't that just be a variable?

  11. #11
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    Quote Originally Posted by xArt View Post
    I feel like I'm walking into a trap, but what sort of array has one element?
    Wouldn't that just be a variable?
    You're getting a pointer, not an array. This is a perfectly valid function call :

    unsigned char foo = 0xAB;
    shift(&foo, sizeof(foo));

    Or a variable can end up being more than 2 bytes :

    unsigned long long foo2 = 0x1234567812345678ULL;
    shift(&foo2, sizeof(foo2));

    Probably best to handle all cases.

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    Oh was this not for work reasons?
    Well, you pretty much had a solution anyway, and I didn't actually test mine either so it might have horrible bugs in it.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  13. #13
    Registered User
    Join Date
    Jan 2013
    Posts
    69
    The rule might just be for homework, something in another thread gave me the impression that I was
    never going to get code.
    This is a personal project anyway.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Rotate char array
    By pascalbb in forum C++ Programming
    Replies: 8
    Last Post: 10-18-2006, 10:26 AM
  2. Do I really need to rotate?
    By JimJoyce in forum Game Programming
    Replies: 13
    Last Post: 02-24-2005, 03:04 PM
  3. How to rotate
    By cfrost in forum Windows Programming
    Replies: 5
    Last Post: 07-15-2004, 10:08 AM
  4. how to rotate url randomly?
    By Antipher in forum Tech Board
    Replies: 3
    Last Post: 03-21-2003, 01:34 AM
  5. How Do you rotate a multidimensional array?
    By werdy666 in forum C++ Programming
    Replies: 3
    Last Post: 09-29-2002, 10:03 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21