1

Possible Duplicate:
How to perform rotate shift in C
Bitwise rotate left function

In C/C++ I have << and >> as left shits and right shifts respectively.

To test the function of this operator, I want to find the first set bit of a number n, do a left shift by 1 and then do the | of the shifted number with the first bit I found previously.

How should I do this?

Community
  • 1
  • 1
user1413523
  • 345
  • 1
  • 7
  • 15
  • Use another variable as a buffer or use asm. – Bartek Banachewicz Aug 13 '12 at 20:56
  • What's `n`'s type (it matters)? – Luchian Grigore Aug 13 '12 at 20:58
  • 2
    It's not too hard to do this in C/C++. Though if performance matters, there are instructions to do this. But you'll need intrinsics or asm to access them. – Mysticial Aug 13 '12 at 20:59
  • Possible duplicate: http://stackoverflow.com/questions/2835469/how-to-perform-rotate-shift-in-c and http://stackoverflow.com/questions/3323633/efficient-way-of-doing-64-bit-rotate-using-32-bit-values. Somewhat similar but not a duplicate http://stackoverflow.com/questions/10134805/bitwise-rotate-left-function – tinman Aug 13 '12 at 20:59
  • @tinman not a dupe, those are unsigned numbers. – Luchian Grigore Aug 13 '12 at 21:02
  • 1
    @LuchianGrigore: The questions never ask about unsigned but the answer are such. There is also http://stackoverflow.com/questions/776508/circular-shift-operations-in-c which has a C++ version with typedefs for the type. – tinman Aug 13 '12 at 21:06
  • @tinman: Only the last one: http://stackoverflow.com/questions/10134805/bitwise-rotate-left-function is correct. – Martin York Aug 13 '12 at 21:14
  • 1
    @LuchianGrigore: What is the difference when doing a rotation? We are only looking at the bit pattern so signed/unsigned is not relevant (I think). – Martin York Aug 13 '12 at 21:15
  • @LokiAstari what I understand by rotation is that you want the first bit moved to the end. & that can be a problem if you shift a signed value to the left. – Luchian Grigore Aug 13 '12 at 21:17
  • @LuchianGrigore: I am not sure you will be able to predicate the value (only the bit pattern). – Martin York Aug 13 '12 at 21:18
  • Rotation is not a well-defined concept on signed numbers, so one can simply treat the input as an unsigned number. – markgz Aug 14 '12 at 00:42

2 Answers2

1
long long int shiftleft(long long int number, unsigned n)    
{unsigned minusone=sizeof(long long int)*8-1;
 long long int r= number & (1LL<<minusone);//save the sign, which is the most significant bit
 long long int mask = (1LL<<minusone)-1;  //a mask to get all other bits

 return ( number<<n) | ((number & mask) >>(minusone-n)) | r; //rotate left in a loop only 63 bits 
}

haven't tested the code

titus
  • 5,512
  • 7
  • 25
  • 39
  • Best practices for compiler-friendly rotates in C: http://stackoverflow.com/questions/776508/best-practices-for-circular-shift-rotate-operations-in-c. It's far easier to just cast to unsigned for the rotate. – Peter Cordes Aug 17 '15 at 18:17
0

You can do a rotate left like this:

int n; // amount to rotate by
unsigned int d; // the positive number to rotate.
if(n < (CHAR_BIT * sizeof(int)))
    int x = (n << d)|(n >> ((CHAR_BIT * sizeof(int)) - d));

However this will only work on a positive number. and right rotation can be accomplished like this:

if(n < (CHAR_BIT * sizeof(int)))
    int x = (n >> d)|(n << ((CHAR_BIT * sizeof(int)) - d));

This also only works on positive numbers.

Rivasa
  • 6,510
  • 3
  • 35
  • 64