Asp Forum - Re: Circular shift

MenTaLguY

1/22/2008 9:22:00 PM

Zangief Ief wrote:
> I would like to write a simple implementation of *circular shift*
> (http://en.wikipedia.org/wiki/Circ...). Thank you all for any
> ideas :)

The silly things people are doing to avoid using bitwise operations
notwithstanding, there's really only one way to do it.

I'll break it down into individual pieces so you can see how it works:

def bitmask(bits)
( 1 << bits ) - 1
end

def shift_left_width(value, register_width, bits)
( value << bits ) & bitmask(width)
end

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

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

(If you know the width of the shift register or the number of bits
to shift in advance, you can simplify the math.)

-mental
--
Posted via http://www.ruby-....

11 Answers

MenTaLguY

1/22/2008 9:24:00 PM

Mental Guy wrote:
> def shift_left_width(value, register_width, bits)
> ( value << bits ) & bitmask(width)
> end

Of course, this should be:

def shift_left_width(value, register_width, bits
( value << bits ) & bitmask(register_width)
end

-mental
--
Posted via http://www.ruby-....

MenTaLguY

1/22/2008 9:26:00 PM

Grar, let me try that again without missing the closing parenthesis:

def shift_left_width(value, register_width, bits)
( value << bits ) & bitmask(register_width)
end

-mental
--
Posted via http://www.ruby-....

MenTaLguY

1/22/2008 10:16:00 PM

It may also help if I explain how each piece works. I realize that
bitwise operations are unfortunately becoming something of a "lost art",
but they are important to understand and everyone should make a special
effort to learn about them.

On Wed, 23 Jan 2008 06:22:02 +0900, Mental Guy <mental@rydia.net> wrote:

> def bitmask(bits)
> ( 1 << bits ) - 1
> end

This creates a sequence of 1s. For example:

bitmask(5) ==
( 1 << 5 ) - 1 == # 1 << n == 2 ** n
32 - 1 == # 32 ( 2 ** 5 ) is binary 100000
31 # 31 is binary 11111

Other examples:

bitmask(1) # => 1 is binary 1
bitmask(3) # => 7 is binary 111
bitmask(6) # => 63 is binary 111111

> def shift_left_width(value, register_width, bits)
> ( value << bits ) & bitmask(register_width)
> end

This shifts a number left a certain number of bits, chopping
it off at a certain width. For example:

shift_left_width(134, 8, 3) == # 134 is binary 10000110
( 134 << 3 ) & bitmask(8) ==
1072 & bitmask(8) == # 1072 is binary 10000110000
1072 & 255 == # 255 is binary 11111111
48 # 48 is binary 110000

Note how the mask controls which non-zero bits are kept from
1072 in order to make 48.

[n.b. In some languages, left shift may have a maximum
width built in, though that is not the case in Ruby. ]

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

Now, the circular version:

remaining_bits ==
8 - 3 ==
5

We are moving 3 to the left in an 8-bit register, which
means that 3 bits wrap around, and the remaining 5 bits
just get moved over.

top ==
shift_left_width(134, 8, 3) == # 134 is binary 10000110
48 # 48 is binary 110000

Note how the upper three bits were discarded, and we moved
the remaining five over by three bits.

bottom ==
134 >> 5 == # 134 is binary 10000110
4 # 4 is binary 100

Notice how we moved the top three bits over and discarded
the other five bits; the three bits we kept are the same
the same three bits that were tossed out in the previous
step.

48 | 4 == # 48 is binary 110000
# 4 is binary 100
52 # 52 is binary 110100

So, our circular shift of 134 in an eight-bit shift register
amounted to:

1. take 134 ( 10000110 )
2. split it into two parts ( 100 00110 )
3. swap them ( 00110 100 )
4. put the result back together ( 00110100 )

-mental

MenTaLguY

1/22/2008 10:40:00 PM

Lloyd Linklater wrote:
> Don't forget that the high order bit must be placed in the low order bit
> position to fulfill what the guy asked for.

I didn't. Three one-bit circular shifts is the same as one three-bit
circular shift.

One-at-a-time:

10000110
1 0000110
0000110 1
00001101
0 0001101
0001101 0
00011010
0 0011010
0011010 0
00110100

All at once:

10000110
100 00110
00110 100
00110100

-mental
--
Posted via http://www.ruby-....

Zangief Ief

1/22/2008 10:51:00 PM

Thanks a lot, Lloyd Linklater, 7stud and Mental Guy!! I am very happy to
see all of your reply for the question! :)
I have trying to use functions of Mental Guy with this few lines:

block = 134 # it's a example of decimal value

puts "block (dec): #{block}"
puts "block (bin): #{block.to_s(2)}"

# here I try to shift 2 bites at the right
new_b = circular_shift_right(block, block.to_s(2).length, 2)

# and to display the result:
puts "new_b (dec): #{new_b}"
puts "new_b (bin): #{new_b.to_s(2)}"

Is it possible to use your system like this?
circular_shift_right(my_block, number_of_bit_to_shift)

I will continue to read your code :)
Thanks again!
--
Posted via http://www.ruby-....

MenTaLguY

1/22/2008 11:04:00 PM

Zangief Ief wrote:
> Is it possible to use your system like this?
> circular_shift_right(my_block, number_of_bit_to_shift)

Yes, you can hard-code a specific width for the shift
register: just remove the register_width arguments and
replace all the instances of the register_width variable with
the specific width you want. At that point you should be able
to do simplifications like replacing the call to
bitmask(register_width) with a specific value.

Try making that change and post what you get.

-mental
--
Posted via http://www.ruby-....

Zangief Ief

1/22/2008 11:29:00 PM

Mental Guy wrote:

> 1. take 134 ( 10000110 )
> 2. split it into two parts ( 100 00110 )
> 3. swap them ( 00110 100 )
> 4. put the result back together ( 00110100 )
>
> -mental

Wow, it's perfect! Sorry, I haven't understood because of the padding in
the step 4. Now it's okay.

Here is an example of file:

block = 753
shift = 2
length = block.to_s(2).length
new_block = circular_shift_left(block, block.to_s(2).length, shift)
puts "input: #{block.to_s(2)}"
puts "output: #{new_block.to_s(2)}"

And when I execute it:

$ ruby circular_shift.rb
input: 1011110001
output: 1111000110

THANKS A LOT :)
--
Posted via http://www.ruby-....

Judson Lester

1/25/2008 8:40:00 PM

On Jan 22, 2008 3:29 PM, Zangief Ief <z4n9ief@gmail.com> wrote:
> Here is an example of file:
>
> block = 753
> shift = 2
> length = block.to_s(2).length

Ack! Be careful there. Circular shift doesn't make any sense unless
you know how wide the register is up front. Ruby will expand the
width of a number as needed, so you have to impose a width. Using
"block.to_s(2).length" breaks that imposition - the resulting circular
shift doesn't make any sense.

More practically, what if I used block=2, shift = 7? Using length
gives you a width of two, and you wind up with 64.
(Actually, that exposes a corner-case in Mental Guy's design: if bits
> register_width, you get a simple left shift of the difference.)

Instead, pick a width based on the application and stick with it.

block = 753
shift = 4
width = 12
new_block = circular_shift_left(block, width, shift)
puts "%0*b"%[width, block] #takes care of that pesky "leading 0" problem
puts "%0*b"%[width, block]

001011110001
111100010010

Judson
--
Your subnet is currently 169.254.0.0/16. You are likely to be eaten by a grue.

MenTaLguY

1/25/2008 9:47:00 PM

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-....

Judson Lester

1/25/2008 10:03:00 PM

On Jan 25, 2008 1:47 PM, Mental Guy <mental@rydia.net> wrote:
> 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.

Let's just say I share your love for binary arithmetic. But, hey, I'm
more than happy to play straight man for a good punchline.

> 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):
>

Say, that almost sounds like a use case for a class. Something like

class Register < Integer
def initialize(width, value);
...
end
end

(or even
def Register(width)
klass = class.new(Register)
#metaprogrammy stuff to define klass::width
end)

But that would be drifting from the topic.

> ---
>
> [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.

Yeah, no kidding. C (and many related languages) also fix the width
of numeric types and have built-in (<<<) circular shifts.

Judson
--
Your subnet is currently 169.254.0.0/16. You are likely to be eaten by a grue.

comp.lang.ruby

Re: Circular shift

MenTaLguY

MenTaLguY

MenTaLguY

MenTaLguY

MenTaLguY

Zangief Ief

MenTaLguY

Zangief Ief

Judson Lester

MenTaLguY

Judson Lester

x Login to ForumsZone