Hello everybody,

I would like to write a simple implementation of *circular shift*

(http://en.wikipedia.org/wiki/Circular_shift). Thank you all for any

ideas

Hello everybody,

I would like to write a simple implementation of *circular shift*

(http://en.wikipedia.org/wiki/Circular_shift). Thank you all for any

ideas

Zangief I. wrote:

I would like to write a simple implementation of

circular shift

(http://en.wikipedia.org/wiki/Circular_shift). Thank you all for any

ideas

Well, I am not sure just what you are looking for but here is at least

something until one of the sharpies replies:

reverse_this_number = 1234

puts reverse_this_number.to_s(2) # before

top_bit_set = ((2**(reverse_this_number.size * 8)) &

reverse_this_number) != 0

reverse_this_number *= 2

if top_bit_set then

reverse_this_number += 1 # set the low order bit

end

puts reverse_this_number.to_s(2) # after

output:

10011010010

100110100100

Note: the output will be missing the leading zero, but it shifts it

correctly.

This is how it would be internally:

010011010010

100110100100

Zangief I. wrote:

Hello everybody,

circular shift

(http://en.wikipedia.org/wiki/Circular_shift). Thank you all for any

ideas

arr = [1, 2, 3]

arr << arr.shift

p arr

arr[0, 0] = arr.pop

p arr

â€“output:â€“

[2, 3, 1]

[1, 2, 3]

Zangief I. wrote:

Hello everybody,

circular shift

(http://en.wikipedia.org/wiki/Circular_shift). Thank you all for any

ideas

num = 1234

str = num.to_s(2)

puts str

puts

arr = str.split("")

arr << arr.shift

puts arr.join

arr[0, 0] = arr.pop

puts arr.join

â€“output:â€”

10011010010

00110100101

10011010010

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

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

Zangief I. wrote:

circular shift

(http://en.wikipedia.org/wiki/Circular_shift). 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

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 G. [email protected] 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:

- take 134 ( 10000110 )
- split it into two parts ( 100 00110 )
- swap them ( 00110 100 )
- put the result back together ( 00110100 )

-mental

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

Hey Mental G.,

Donâ€™t forget that the high order bit must be placed in the low order bit

position to fulfill what the guy asked for.

Thanks a lot, Lloyd L., 7stud and Mental G.!! I am very happy to

see all of your reply for the question!

I have trying to use functions of Mental G. with this few lines:

block = 134 # itâ€™s a example of decimal value

puts â€śblock (dec): #{block}â€ť

puts â€śblock (bin): #{block.to_s(2)}â€ť

new_b = circular_shift_right(block, block.to_s(2).length, 2)

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!

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

On Jan 22, 2008 3:29 PM, Zangief I. [email protected] 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 G.'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

On Sat, 26 Jan 2008 05:40:00 +0900, â€śJudson L.â€ť [email protected]

wrote:

(Actually, that exposes a corner-case in Mental G.'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.

Mental G. wrote:

- take 134 ( 10000110 )
- split it into two parts ( 100 00110 )
- swap them ( 00110 100 )
- 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

On Sat, 26 Jan 2008 07:03:12 +0900, â€śJudson L.â€ť [email protected]

wrote:

On Jan 25, 2008 1:47 PM, Mental G. [email protected] 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.

Yeah, your reply struck me as fairly bit-savvy; Iâ€™m mostly just writing

for the benefit of any bit-curious folks out there on the list.

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

Then thereâ€™s also the whole shift-with-sign-extension (or not) thingâ€¦

-mental

On Jan 25, 2008 1:47 PM, Mental G. [email protected] 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

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

Sponsor our Newsletter | Privacy Policy | Terms of Service | Remote Ruby Jobs