Hi,
I need help writing a method that performs a circular shift (either left or right, depending on parameter passed it) on a 56 bit number. It has to work such that all the higher order zeroes are retained.
Put simply, I need to be able to input a 56 bit number, rotate it once left or right, and return that rotated 56 bit number.
Please, any help out there for me?!
Thank you
Jake
In base X? Examples, please....
Can't you just "shift" the number right/left once, remembering the digit that is to be over/underflown and appending it to left/right? And then make a method that does that multiple times?
> It has to work such that all the higher order zeroes
> are retained.
What about 1s?
Btw: 56 bit number... ?
56 bits in binary code...
I understand about shifting the number right/left once, but am not sure on how to remember the digit that is to be over/underflown. I think I need a mask for bit 1 or 56 (depending on which direction I'm shifting), then shift left/right once, then apply the mask to the relevant end.
Yes, I need all the higher order ones are retained..
eg 1000....00010 => shift left should become 000....000101
1000....00010 => shift right should become 01000....0001
Thanks for any help!
First: there are no 56 bit numbers in Java - only 8, 16, 32 and 64 bit. I assume you want to store the number in a 64bit long?
shift left by one:
// get the overflow
overflow = (A >> 55) & 1;
// shift it right
A = A << 1;
// make sure that A stays in 56 bits
// (mask_56bits has the lowest 55 bits set)
A &= mask_56bits;
// add overflow back to A
A |= oveflow;
I'm sure you can now work out the right shitf?
I presume you store the number in a long? In that case you can left shift << and right shift should be done with >>> wich is an unsigned shift. If you use >> 100...0010 will become 1000...0001 because all but the sign bit are shifted.
a long in java is 64 bit and i think you want to keep the first 8 (unused) bits 0. If this is not the case you should set the firs bits to zero with number &= 0x00FFFFFFFFFFFFFF
before shifting right you can check what has to become the first bit with long carry = number & 1;
this wil set the carry to the last bit. Then you can shift the number: number >>>= 1;
Then check what bit 56 should be:if(carry != 0)
number |= 0x0080000000000000
Left shift will becomelong carry = number & 0x0080000000000000
number <<= 1;
if(carry != 0)
number |= 0x0080000000000000
Good luck.
