From: Mental Guy <mental@...>
Date: 2008-01-26T06:47:02+09:00
Subject: Re: Circular shift

On Sat, 26 Jan 2008 05:40:00 +0900, "Judson Lester" <nyarly@gmail.com> 
wrote:
> (Actually, that exposes a corner-case in Mental Guy's design: if bits
>> register_width, you get a simple left shift of the difference.)

Well, it isn't so much a corner case as it is a bug:  since the shift
register is circular, the number of bits to shift is actually a modular
quantity.  Shifting by (for example) 7 bits in a 3-bit register should
get you to the same place as shifting by 1 bit in a 3-bit register,
as 7 % 3 == 1.

 def circular_shift_right(value, register_width, bits)
   bits %= register_width
   remaining_bits = register_width - bits
   top = shift_left_width(value, register_width, remaining_bits)
   bottom = value >> bits
   top | bottom
 end

The other implication is that shifting by (modular) bits in one
direction is the same as shifting by remaining_bits in the other:

  10101100
 101 01100
 01100 101
  01100101

As should be visually obvious, that could be either a right shift
by five bits, or a left shift by three, and -3 % 8 == 5 in modular
arithmetic[1].  So:

 def circular_shift_left(value, register_width, bits)
   circular_shift_right(value, register_width, -bits)
 end

I had hoped to walk the OP through discovering this for himself,
but he ran off once he decided I'd solved his problem for him, so
I didn't pursue it.

Since you showed interest, though, I'll continue with what I would
have eventually gotten to:  if the register width is a power of two,
you can do some additional tricks.

I mentioned the identity:

 1 << n == 2 ** n

Which is a special case of the identities:

 m << n == m * 2 ** n
 m >> n == m / 2 ** n

There is also the identity:

 m & ( ( 1 << n ) - 1 ) == m % 2 ** n

So, if register_width is guaranteed to be a power of two:

 def circular_shift_right(value, register_width, bits)
   bits &= register_width - 1
   remaining_bits = register_width - bits
   top = shift_left_width(value, register_width, remaining_bits)
   bottom = value >> bits
   top | bottom
 end

Now, if we decide to hard-code a specific register width, we
can simplify things pretty dramatically (let's pick 8, which
is 2 ** 3):

 def circular_shift_right_8(value, bits)
   bits &= 8 - 1
   remaining_bits = 8 - bits
   top = shift_left_width(value, register_width, remaining_bits)
   bottom = value >> bits
   top | bottom
 end

 def circular_shift_right_8(value, bits)
   bits &= 7
   remaining_bits = 8 - bits
   top = shift_left_width(value, register_width, remaining_bits)
   bottom = value >> bits
   top | bottom
 end

 def circular_shift_right_8(value, bits)
   bits &= 7
   remaining_bits = 8 - bits
   top = ( value << remaining_bits ) & bitmask(8)
   bottom = value >> bits
   top | bottom
 end

 def circular_shift_right_8(value, bits)
   bits &= 7
   remaining_bits = 8 - bits
   top = ( value << remaining_bits ) & ( 1 << 8 ) - 1
   bottom = value >> bits
   top | bottom
 end

 def circular_shift_right_8(value, bits)
   bits &= 7
   remaining_bits = 8 - bits
   top = ( value << remaining_bits ) & 255
   bottom = value >> bits
   top | bottom
 end

 def circular_shift_right_8(value, bits)
   bits &= 7
   top = ( value << ( 8 - bits ) ) & 255
   bottom = value >> bits
   top | bottom
 end

 def circular_shift_right_8(value, bits)
   bits &= 7
   ( value << ( 8 - bits ) ) & 255 | ( value >> bits )
 end

And, of course:

 def circular_shift_left_8(value, bits)
   circular_shift_right_8(value, -bits)
 end

-mental

---

[1] Be careful when porting code to other languages; they may differ
in their treatment of negative numbers with the modulo operator, and
in C its behavior is platform-dependent.  Ruby's way is the best way
for modular arithmetic though.
-- 
Posted via http://www.ruby-forum.com/.