Circular shift

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

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

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,

I would like to write a simple implementation of circular shift
(http://en.wikipedia.org/wiki/Circular_shift). Thank you all for any
ideas :slight_smile:

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,

I would like to write a simple implementation of circular shift
(http://en.wikipedia.org/wiki/Circular_shift). Thank you all for any
ideas :slight_smile:

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:

I would like to write a simple implementation of circular shift
(http://en.wikipedia.org/wiki/Circular_shift). Thank you all for any
ideas :slight_smile:

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:

  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

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! :slight_smile:
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)}”

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 :slight_smile:
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 “%0b"%[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:

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

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.

| Privacy Policy | Terms of Service | Remote Ruby Jobs