Bit Shifting in Place

Question

I was just wondering if there was a way to bit shift a number "in place"? I've googled exactly that, and I can't find anything that pertains to what I want to do. Say I have the number 0b01001101, and I want to shift it twice to the right "in place", appending any numbers that fall off to the beginning. So it would look like 0b01010011. Is there any function in c++ that would allow me to bit shift left or right like that?

Is the term "circular shift" what you're looking for? http://stackoverflow.com/questions/776508/circular-shift-operations-in-c And also you can google that term — Yuf, Jul 22 '11 at 17:05
Okay, how would I go about making my own? Should i just AND it with 1, if result is 1, shift right 1 and then OR it with 255 (or however large the binary is)? And similar method for left shift? — Polosky, Jul 22 '11 at 17:07
@Yuf Yes, I think that is exactly what I was looking for! :D — Polosky, Jul 22 '11 at 17:08
Look up "rotate with carry". Most processors have an instruction that performs this. — Thomas Matthews, Jul 22 '11 at 19:46
To nitpick, the common difference between a shift and a rotate is that a rotate involves carry (from a previous operation). — Thomas Matthews, Jul 22 '11 at 19:48

BlackBear · Answer 1 · 2011-07-22T17:14:16.333

1

Using the assembly instruction ror and getting the carry flag's value each time should do the work.

int rotate(int x, int n)
{
    for(int i = 0; i < n; i++) {
        __asm {
            ror   x, 1            ; rotate and store limit bit in cf
            lahf                  ; get part of flags in ah
            and   ah, 1           ; get only the cf
            shl   eax, 31         ; put it at the end
            and   x, eax          ; and store in x
        }
    }

    return x;
}

edited Jul 22 '11 at 17:14

answered Jul 22 '11 at 17:06

BlackBear

22,411
10
48
86

6

While I'm impressed by the mad-crazy assembly skills, I'd imagine that this code would add enormous portability problems. – riwalk Jul 22 '11 at 17:20
@Stargazer712: that's the other side of the medal :P it should work on every intel's processor though – BlackBear Jul 22 '11 at 17:22
It is not only portability, but this is probably less efficient than the C or C++ construct. – David Rodríguez - dribeas Jul 22 '11 at 18:28

score 1 · Answer 2 · answered Jul 22 '11 at 17:08

1

Write one yourself, I think it's not hard.

First store the right two bits,and then do the bit shift.Finally fill the left two bits with the stored bits.

answered Jul 22 '11 at 17:08

moonkey

311
3
13

I think I will just do this, since I need to implement it in both Python and C++. – Polosky Jul 22 '11 at 17:09

selbie · Accepted Answer · 2011-07-22T17:32:30.167

You want to implement a rotational shift

Here's a templatized version that should work with all types of ints (including shorts, chars, ints, and unsigned/signed alike).

template<class T>
T rotate_shift_right(T x, int shift)
{
    if ((shift > 0) && (shift < (sizeof(x)*8)))
    {
        x = ((unsigned)x >> shift) | (x << (sizeof(x) * 8 - shift));
    }
    return x;
}

template<class T>
T rotate_shift_left(T x, int shift)
{
    if ((shift > 0) && (shift < (sizeof(x)*8)))
    {
        x = (x << shift) | (((unsigned)x) >> (sizeof(x) * 8 - shift));
    }
    return x;
}

score 0 · Answer 4 · answered Jul 22 '11 at 17:03

0

I think shifting it and then anding the last byte onto the beginning should work.

answered Jul 22 '11 at 17:03

Rocky Pulley

22,531
20
68
106

While this Q&A has seemingly run its course you should probably edit your answer to use "or'ing" as "anding" the last byte is the wrong operation. – tinman Jul 22 '11 at 17:31

score 0 · Answer 5 · answered Jul 22 '11 at 17:04

0

No, you should create your custom one

answered Jul 22 '11 at 17:04

Manlio

10,768
9
50
79

this is true, though minimalistic, and answers the question – ShinTakezou Jul 22 '11 at 17:15
This is really a comment, not an answer to the question. Please use "add comment" to leave feedback for the author. – TemplateRex Aug 09 '12 at 11:38
@rhalbersma well, if I read again the question I think my post is actually an answer. Maybe too short (guess that's why 2 downvotes) but is correct. – Manlio Aug 09 '12 at 13:39
@Saphrosit it is a "strict subsequence" of the accepted answer (because you don't specify how to write one), and doesn't add anything. If you self-delete, you regain your downvotes :-) – TemplateRex Aug 09 '12 at 13:41

score 0 · Answer 6 · answered Jul 22 '11 at 17:07

0

This is implemented as vendor-specific extensions. For MSVC, you can use _rotl8, _rotl16 (or _rotr* for rotating to the right). Not sure about GCC, but you can always drop to assembly and use the rol or ror.

answered Jul 22 '11 at 17:07

Blindy

65,249
10
91
131

Bit Shifting in Place

6 Answers6