13

I am trying to implement a rotate left function that rotates an integer x left by n bits

  • Ex: rotateLeft(0x87654321,4) = 0x76543218
  • Legal ops: ~ & ^ | + << >>

so far I have this:

int rotateLeft(int x, int n) {
  return ((x << n) | (x >> (32 - n)));
}

which I have realized to not work for signed integers..does anyone have any ideas as how to fix this?

so now I tried:

int rotateLeft(int x, int n) {
  return ((x << n) | ((x >> (32 + (~n + 1))) & 0x0f));
}

and receive the error:

ERROR: Test rotateLeft(-2147483648[0x80000000],1[0x1]) failed... ...Gives 15[0xf]. Should be 1[0x1]

asdfghjkl
  • 393
  • 3
  • 8
  • 20
  • 1
    Think about why your expression doesn't work for signed integers and what you could do to the part to the right of the or-operator to make it work. Also, note that `-` is not part of your legal operator list, so you need to fix that as well. – George Skoptsov Apr 13 '12 at 03:32
  • ok so I think i figured out how to get rid of the - by (32 + (~n + 1)) but I am having trouble figuring out what I can do after the | to make this work – asdfghjkl Apr 13 '12 at 03:43
  • can you create a mask to & the extraneous 1 bits away? – George Skoptsov Apr 13 '12 at 03:46
  • yes, but i have no c knowledge prior to this so I am not familiar with bitwise operators and i do not know how to use a mask – asdfghjkl Apr 13 '12 at 03:53
  • so let's say you have 0xf5 (11110101) and you want to zero out the 4 higher bits. Then you can do `0x0f & 0xf5`, which will result in 0x05. 0x0f is a mask. Does this make sense? – George Skoptsov Apr 13 '12 at 03:56
  • i think so...check my edit above – asdfghjkl Apr 13 '12 at 04:02
  • Well, now you're zeroing everything out.. while you need to zero out only the top 32-n bits, right? – George Skoptsov Apr 13 '12 at 04:04
  • yeah that is what I am trying to do but I don't know how to create that mask – asdfghjkl Apr 13 '12 at 04:07
  • Again one of these teachers that is not aware of the difficulties when shifting signed entities? There seem to be so many of them out there that don't even know that `unsigned` exists. – Jens Gustedt Apr 13 '12 at 06:30
  • 1
    @shaynie Work through this tutorial to understand bitwise operators: http://www.cprogramming.com/tutorial/bitwise_operators.html Then this problem will be much easier. – George Skoptsov Apr 13 '12 at 14:08
  • Don't hard code `32`. Use `CHAR_BIT * sizeof x` or similar. – William Pursell Apr 13 '23 at 12:20

6 Answers6

17

Current best practice for compiler-friendly rotates is this community-wiki Q&A. The code from wikipedia doesn't produce very good asm with clang, or gcc older than 5.1.

There's a very good, detailed explanation of bit rotation a.k.a. circular shift on Wikipedia.

Quoting from there:

unsigned int _rotl(const unsigned int value, int shift) {
    if ((shift &= sizeof(value)*8 - 1) == 0)
      return value;
    return (value << shift) | (value >> (sizeof(value)*8 - shift));
}

unsigned int _rotr(const unsigned int value, int shift) {
    if ((shift &= sizeof(value)*8 - 1) == 0)
      return value;
    return (value >> shift) | (value << (sizeof(value)*8 - shift));

In your case, since you don't have access to the multiplication operator, you can replace *8 with << 3.

EDIT You can also remove the if statements given your statement that you cannot use if. That is an optimization, but you still get the correct value without it.

Note that, if you really intend to rotate bits on a signed integer, the interpretation of the rotated result will be platform dependent. Specifically, it will depend on whether the platform uses Two's Complement or One's Complement. I can't think of an application where it is meaningful to rotate the bits of a signed integer.

Community
  • 1
  • 1
Eric J.
  • 147,927
  • 63
  • 340
  • 553
  • i understand what bit rotation is and how it works but I have to program it with just the bitwise operations listed above – asdfghjkl Apr 13 '12 at 03:33
  • Is there anything in the listed implementation that you do not have access to? Note that you can replace `- 1` with `+ -1` and `*8` with `<<3`. – Eric J. Apr 13 '12 at 03:36
  • I am not aloud to use sizeOf or to call any other functions and for reference, we are to assume our 32 bit integers use two's complement – asdfghjkl Apr 13 '12 at 03:54
  • In that case you can just do the math and replace `sizeof(value)*8-1` with `4*8-1` = `31` and `sizeof(value)*8` with `32`. – Eric J. Apr 13 '12 at 04:00
  • i am also not permitted to use any loops or if statements – asdfghjkl Apr 13 '12 at 04:05
  • Then take out the `if` statements. They are just an optimization. You still get the correct result if they are omitted. – Eric J. Apr 13 '12 at 04:18
  • 1
    As a side note; I would have replaced the `8` with `CHAR_BIT` from `limits.h`. – Morpfh Apr 13 '12 at 04:47
  • @Rune is `sizeof()` isn't allowed, `CHAR_BIT` is not much of a help. – Alexey Frunze Apr 13 '12 at 14:48
  • @Alex: I meant it as a general rule of thumb it is better to use limits.h then magic numbers. – Morpfh Apr 13 '12 at 14:59
  • i highly doubt that an `if` can be an optimization when running on a OOO processor. I would say adding the `if` on the contrary seems like a pessimisation to me. – v.oddou Jun 22 '15 at 06:51
  • @v.oddou: Perhaps, but who knows what type of processor this is for (if it is even a real processor) given the constraints of the problem. – Eric J. Jun 22 '15 at 14:41
6
int rotateLeft(int x, int n) {
  return (x << n) | (x >> (32 - n)) & ~((-1 >> n) << n);
}

UPDATE:(thanks a lot @George)

int rotateLeft(int x, int n) {
  return (x << n) | (x >> (32 - n)) & ~(-1 << n);
}

not use '-' version. 

int rotateLeft(int x, int n) {
    return (x << n) | (x >> (0x1F & (32 + ~n + 1))) & ~(0xFFFFFFFF << n);
}

//test program
int main(void){
    printf("%x\n",rotateLeft(0x87654321,4));
    printf("%x\n",rotateLeft(0x87654321,8));
    printf("%x\n",rotateLeft(0x80000000,1));
    printf("%x\n",rotateLeft(0x78123456,4));
    printf("%x\n",rotateLeft(0xFFFFFFFF,4));
    return 0;
}
/* result : GCC 4.4.3 and Microsoft(R) 32-bit C 16.00.40219.01
76543218
65432187
1
81234567
ffffffff
*/
BLUEPIXY
  • 39,699
  • 7
  • 33
  • 70
  • 2
    This question is tagged as homework. Let's avoid giving explicit answers. There's much more benefit to the OP if he/she learns how to answer this question him/herself. – George Skoptsov Apr 13 '12 at 14:09
  • Well, I will not That's right, that she(he) 's does not know how making mask? – BLUEPIXY Apr 13 '12 at 14:22
  • I'm not sure what you're asking. She doesn't know what a mask is or how it works, so she needs to learn that first. In any case, in your answer `(-1 >> n)` has no effect -- do you see why? It's better to simply use ~0. – George Skoptsov Apr 13 '12 at 14:25
  • She can't use `-` op, so you should use `~0`. Your answer also needs an extra pair of parentheses. – George Skoptsov Apr 13 '12 at 15:08
  • What was that sense. She's E.g use (32 - n). Thought it was all right so. Now answer the way i do not need extra parentheses are. – BLUEPIXY Apr 13 '12 at 15:16
  • You still need extra parens. Your current expression will zero out n least significant bits. – George Skoptsov Apr 13 '12 at 16:12
  • @George Skoptsov , don't. Can you present a concrete x and n to be odd behavior? – BLUEPIXY Apr 13 '12 at 16:32
2

The best way is:

int rotateLeft(int x, int n)
{
    _asm
    {
        mov eax, dword ptr [x]
        mov ecx, dword ptr [n]
        rol eax, cl
    }
}

If you need to rotate an int variable right in your code, then the fastest way is:

#define rotl( val, shift ) _asm mov eax, dword ptr[val] _asm mov ecx, dword ptr [shift] _asm rol eax, cl _asm mov dword ptr [val], eax

val is the value you rotate, shift is the length of the rotation.

RedRidingHood
  • 568
  • 3
  • 16
  • 9
    This is non-portable, i.e. assumes an Intel compatible chip inside. – Assad Ebrahim Oct 04 '16 at 03:47
  • 2
    Forcing the compiler to store/reload the value and count is a huge amount of overhead, and much worse than what you'd get from C that the compiler recognizes and turns back into a `rol` instruction. [MSVC-style inline asm is terrible for wrapping single instructions](http://stackoverflow.com/questions/3323445/what-is-the-difference-between-asm-and-asm/35959859#35959859). – Peter Cordes Jun 07 '17 at 01:31
  • 2
    Also, this prevents a compile-time-constant count from optimizing into `rol eax, imm8`, or from optimizing away entirely if the value is also a constant after inlining. – Peter Cordes Jun 07 '17 at 01:33
0

Can you define 'rotate left' for a signed int?

I would simply cast x to an unsigned int and perform the rotation the way you have it right now.

On another note: does your code need to work on different architectures (not just 32-bit)? You may want to avoid hardcoding the int bitsize.

George Skoptsov
  • 3,831
  • 1
  • 26
  • 44
0

In ISO C (no idea if this is your implementation language or not, but it sure looks like it), shift-right on a signed integer that’s negative is implementation-defined and should thus be avoided.

If you’re doing bitops anyway, you really should cast to unsigned integers first.

mirabilos
  • 5,123
  • 2
  • 46
  • 72
0

I find a way for doing a rotate that can be useful when you work with some bit who the size is fixed and you knew it:

int rotate_bit_left(int bit_rotating){
 int LastMax = 64;
 bit_rotating = (bit_rotating>=LastMax)? ((bit_rotating << 1 ) | 0x01) : bit_rotating << 1 ;
 return bit_rotating;
 /*
  Here LastMax is 64 because in the exemple I work in the Ascii table where the max is 0111 1111 and this value can be adapted with the value of the last one bit in decimale
 */
}

This function can be changed to a right rotate 

int rotate_bit_right(int bit_rotating){
 bit_rotating = ((bit_rotating%2)==1)? ((bit_rotating >> 1)| 0x80 ): bit_rotating >> 1 ;
 return bit_rotating; 
 /*
 Because if is a odd number then the last bit is one and we have to put it in the first place
 */
}

Notice that 0x01 and 0x80 must be changed if your worked in an other case than Ascii table to Hexa number with a pattern like this : 0...0001 for the left rotate 100....0 for the right rotate

Valentin bout
  • 1