Hello everybody,
I would like to write a simple implementation of circular shift
(Circular shift - Wikipedia). Thank you all for any
ideas 
Zangief I. wrote:
I would like to write a simple implementation of circular shift
(Circular shift - Wikipedia). 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,
I would like to write a simple implementation of circular shift
(Circular shift - Wikipedia). 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,
I would like to write a simple implementation of circular shift
(Circular shift - Wikipedia). 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:
I would like to write a simple implementation of circular shift
(Circular shift - Wikipedia). 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)}”
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!
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 "%0b”%[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