Rotate Bits Right Operation in Ruby

Rotate Bits Right operation in Ruby

Some facts:

• Ruby has operators << and >> to shift, but no built-in rotate operator. You have to fake it.
• Ruby's Fixnum class automatically promotes to Bignum when the value exceeds the machine word size. This includes numbers that would fit in an unsigned word but not a signed word -- for example, 0xffffffff is a positive Bignum, not a negative Fixnum.

So if you want a rotate operation, you a) have to write it using the shift operators, b) either hardcode 32 or 64 bits or ask Fixnum for the word size, and c) accept that the result might end up being a Bignum.

That being said, this might work:

class Integer
  def ror count
    (self >> count) | (self << (32 - count)) & 0xFFFFFFFF
  end
end

>> printf "0x%x\n", (0x01234567.ror 4)
0x70123456

How to left rotate bits of an Integer

Ruby will automatically switch to a different internal representation in order to accommodate larger numbers, so you'll need to cap it with masking:

class Integer
  def rotl32(n)
    mask = (1 << (32 - n)) - 1

    ((self & mask) << n) | (self >> (32 - n))
  end
end

Where mask indicates which bits should be shifted left, the rest effectively trimmed off before shifting.

Ruby will gladly do really ridiculous stuff like 1 << (1 << 16) which produces a number 19,729 digits long. This is also an Integer.

Note if you need this method more performant you'd want to use a look-up table rather than computing every time, though as always I'd benchmark to make sure that approach is faster.

Ruby's bitwise shift operator confusion in conjuction with array

When you have:

@games << game

<< is actually a method. If it is a method, you ask, why isn't it written in the normal way:

@games.<<(game)

? You could, in fact, write it that way and it would work fine. Many Ruby methods have names that are symbols. A few others are +, -, **, &, || and %. Ruby knows you'd prefer writing 2+3 instead of 2.+(3), so she let's you do the former (and then quietly converts it to the latter). This accommodation is often referred to as "syntactic sugar".

<< is one of @games' methods (and game is <<'s argument), because @games is the receiver of the method << (technically :<<). Historically, it's called the "receiver" because with OOP you "send" the method to the receiver.

To say that << is a method of @games means that << is an instance method of @games's class. Thus, we have:

@games.methods.include?(:<<) #=> true
@games.class.instance_methods.include?(:<<) #=> true

I expect @games is an instance of the class Array. Array's instance methods are listed here. For example:

@games = [1,2,3]
@games.class     #=> [1,2,3].class => Array
@games << 4      #=> [1,2,3,4]
@games.<<(5)     #=> [1,2,3,4,5]

On the other hand, suppose @games were an instance of Fixnum. For example:

@games = 7
@games.class     #=> 7.class => Fixnum

which in binary looks like this:

@games.to_s(2)   #=> "111"

Then:

@games << 2      #=> 28
28.to_s(2)       #=> "11100"

because << is an instance method of the class Fixnum.

As a third example, suppose @games were a hash:

@games = { :a => 1 }
@games.class     #=> { :a => 1 }.class => Hash

Then:

@games << { :b => 2 }
  #=> NoMethodError: undefined method `<<' for {:a=>1}:Hash

The problem is clear from the error message. The class Hash has no instance method <<.

One last thing: consider the method Object#send. Recall that, at the outset, I said that methods are sent to receivers. Instead of writing:

@games = [1,2,3]
@games << 4         #=> [1,2,3,4]

you could write:

@games.send(:<<, 4) #=> [1, 2, 3, 4] 

This is how you should think of methods and receivers. Because send is an instance method of the class Object, and all objects inherit Object's instance methods, we see that send is "sending" a method (:<<, which can alternatively be expressed as a string, "<<") and its arguments (here just 4) to the receiver.

There are times, incidentally, when you must use send to invoke a method. For one, send works with private and protected methods. For another, you can use send when you want to invoke a method dynamically, where the name of the method is the value of a variable.

In sum, to understand what method does in:

receiver.method(*args)

look for the doc for the instance method method in receiver's class. If you Google "ruby array", for example, the first hit will likely be the docs for the class Array.

Ruby Unsigned Right Shift

An unsigned shift operator can easily be implemented using simple bit shifting and masking:

public static int unsignedShift(int amt, int val) {
    int mask = (1 << (32 - amt)) - 1;   
    return (val >> amt) & mask;
}

The mask works by setting all bits to 1 that should be retained after the shift. Note that this returns different results compared to Java for amt >= 32 and amt = 0.

Why do Ruby and JavaScript bitwise operators yield different results with the same operands?

For the Ruby version, it looks like 256 >> -4 is equivalent to 256 << 4, so the negative operand essentially just switches the direction of the shift.

From looking at the ECMAScript specification for the right-shift operator, in JavaScript, the operand is converted to an unsigned 32-bit integer before the shift, so the -4 becomes 4294967292. After this conversion the 5 least-significant bits are used for the shift, in other words we would end up shifting by 4294967292 & 0x1f bits (which comes out to 28). It probably shouldn't surprise you at all to see that 256 >> 28 gives 0.

For convenience, here is the text from the spec (steps 6 and 7 are most relevant to your confusion here):

The Signed Right Shift Operator ( >> )

Performs a sign-filling bitwise right shift operation on the left operand by the amount specified by the right operand.

The production ShiftExpression : ShiftExpression >> AdditiveExpression is evaluated as follows:

1. Let lref be the result of evaluating ShiftExpression.
2. Let lval be GetValue(lref).
3. Let rref be the result of evaluating AdditiveExpression.
4. Let rval be GetValue(rref).
5. Let lnum be ToInt32(lval).
6. Let rnum be ToUint32(rval).
7. Let shiftCount be the result of masking out all but the least significant 5 bits of rnum, that is, compute rnum & 0x1F.
8. Return the result of performing a sign-extending right shift of lnum by shiftCount bits. The most significant bit is propagated. The result is a signed 32-bit integer.

As a side note, if you want to play around with this by converting a value to an unsigned 32-bit integer you can use val >>> 0 as seen in touint32.js from V8 JavaScript Engine.

Bitwise operators in ruby programming

First, let’s understand the operator precedence:

# 5 3  4   1   2
  ~(~1<<((2*n)>>1))

1. 2*n multiplies n by 2
2. >>1 divides the result by 2 making these two operations completely redundant, the original code is 100% equal to ~(~1<<n)
3. ~1 is a bitwise complement, for 0b01 it is -0b10, which is -2,
4. base<<power is a doubled power, hence we have -2^(5+1) = -64
5. bitwise complement again produces 0b0111111 out of -0b1000000.

Use bitwise AND with string on ruby on rails

I try with this: 0000 0000 1000 0000 0000 0000 0000 0000 (64 bits) to
take bytes between the third bytes and the 10th bytes. So I want do a
bitwise "&" with 0000 0000 1000 0000 0000 0000 0000 0000 & 0011 1111
1100 0000 0000 0000 0000 0000 to take just this : 00 0000 10

Let's do it:

("00000000100000000000000000000000".to_i(2) & "00111111110000000000000000000000".to_i(2)).to_s(2)
=> "100000000000000000000000"

Which is exactly what is expected! The number shown in the error ("10000000000000000000000000000000000000000000000000000000") is 2^56, which, when using bitwise AND with it and 2^62+2^63 is expected to give you a zero result...

I suggest you check your input again, and trust ruby's & to do the job...

---

Related Topics