Application of bit-wise operation in Ruby

I remember that I used to use a lot of bit-wise operation in C. But can we also apply it in Ruby. In this post I am going to try explore the possibility of implementing bit-wise operation in Ruby.

I somehow assume the readers have some basic understanding how bit-wise operation works.

1. Quick review of bit-wise operations

Ruby has 6 bit-wise operators:

• Bitwise AND: &
• Bitwise OR: |
• Bitwise XOR(exclusive OR): ^
• Bitwise NOT: ~
• Bitwise Left Shif: <<
• Bitwise Right Shift: >>

Bitwise AND between 2 binary number means that bits at the same position will result in 1(true) if and only if both are true. For example:

145.to_s(2)  #=> "10010001"
130.to_s(2)  #=> "10000010"
(145 & 130).to_s(2) #=> "10000000" or 128

Bitwise OR between two binary numbers result in 0 or false if and only if both are false. For example:

145.to_s(2)  #=> "10010001"
130.to_s(2)  #=> "10000010"
(145 | 130).to_s(2) #=> "10010011" or 147

Bitwise XOR between two binary numbers result in 0 or false if and only if both are 1 or 0. For example:

145.to_s(2)  #=> "10010001"
130.to_s(2)  #=> "10000010"
(145 ^ 130).to_s(2) #=> "10011" or 19

Bitwise NOT of a binary number is the flip of each bit form 0 to 1 or 1 to 0. But that is not quite the story; there is something quite tricky about this in Ruby. for example: 145.to_s(2) #=> "10010001" (~145).to_s(2) #=> "-10010010" or -146

But this does not seem to be a flip and minus is actually not representable withminus sign, on the contrary, minus is represented by 1 in the left most bit using method called two's complement:

Two complements has 3 rules:

• 0 is represented by all zeros.

• Positive numbers starts at zero and counts upward towards a maximum value of 2(n-1)-1 where n is the number of bits. This means that the maximum value possible to represent using 4 bits is 2(5-1)-1 = 15 or 01111.

• For negative numbers, the meaning of zeros and ones changes. Instead of starting at zero, negative numbers starts at -1, which is represented using all ones, and are counted downward using zeros towards a minimum of -2(n-1). In the case of a 5 bit number that would be -2(5-1) = -16 or 10000.

This means that instead of being able to represent the numbers 0 to 31, 5 bits can represent the numbers -16 to 15. Here are some examples of positive and negative integers and their binary representation

For example:

Binary  | Decimal
00000   |    0
00001   |    1
00010   |    2
00110   |    6
11111   |    -1
11110   |    -2
11101   |    -3
10000   |    -16

Here is a trick to see the real flip of bitwise NOT

a = 145
b = ~a  #=> -146

8.downto(0).map { |i| a[i] }.join  #=> "010010001"
8.downto(0).map { |i| b[i] }.join  #=> "101101110"

Left Shif operator moves each bit of binary number to the left. A shift by 1 to the left results in the doubling of the number.

For example: 34 << 1 #=> 68

Right Shift operator moves each bit of binary number to the right. A shift by 1 to the right results in the halving the number.

For example: 34 >> 1 #=> 17

Now I hope you have some idea of what binary operations are now. Let's explore some of its implication.

2. Application of binary operations

The implementation of bitwise operators often use the concept of bit flag and git bit flag and bit mask.

Bit flag and bit mask

suppose we have bit masks below to represent permission status of the user.

READ = 0x01
WRITE = 0x02
EDIT = 0x04
DELETE = 0x08
ADMIN = 0x0f

class User
  attr_accessor :name, :permission

  def initialize(name, permission=0)
    @name = name
    @permission = permission
  end

  def read?
    permission & READ == READ
  end

  def write?
    permission & WRITE == WRITE
  end

  def edit?
    permission & EDIT == EDIT
  end

  def delete?
    permission & DELETE == DELETE
  end

  def admin?
    permission & ADMIN == ADMIN
  end
end

user = User.new('John', READ)
p user.name
#=> "John"
p user.read? ? "can read" : "cannot read"
#=> "can read"
p user.write? ? "can write" : "cannot write"
#=> "cannot write"
p user.permission
#=> 1

user2 = User.new('Tom', READ | WRITE)
p user2.name
#=> "Tom"
p user2.read? ? "can read" : "cannot read"
#=> "can read"
p user2.write? ? "can write" : "cannot write"
#=> "can write"
p user2.edit? ? "can edit" : "cannot edit"
#=> "cannot edit"
p user2.permission
#=>

user3 = User.new('Jerry', READ | WRITE | EDIT)
p user3.name
#=> "Jerry"
p user3.read? ? "can read" : "cannot read"
#=> "can read"
p user3.write? ? "can write" : "cannot write"
#=> "can read"
p user3.edit? ? "can edit" : "cannot edit"
#=> "cannot edit"
p user3.delete? ? "can delete" : "cannot delete"
#=> "cannot delete"
p user3.permission
#=> 7

user4 = User.new('Boss', ADMIN)
p user4.name
#=> "Boss"
p user4.read? ? "can read" : "cannot read"
#=> "can read"
p user4.write? ? "can write" : "cannot write"
#=> "can write"
p user4.edit? ? "can edit" : "cannot edit"
#=> "can edit"
p user4.delete? ? "can delete" : "cannot delete"
#=> "can delete"
p user4.permission
#=> 15

The example above is quite straightforward. I hope you can appreciate its elegance of the code above. I want to explain a bit more about the example above.

user = User.new("Krish", READ)
p user.name
#=> "Krish"
p user.read? ? "can read" : "cannot read"
#=> "can read"
p user.write? ? "can write" : "cannot write"
#=> "cannot write"

# we want to add write permission to Krish
user.permission |= WRITE
p user.write? ? "can write" : "cannot write"
#=> "cannot write"

Suppose now we want to revoke Krish write permission, we can do this by using NOT operator and AND operator.

user.permission &= ~WRITE
p user.write? ? "can write" : "cannot write"
#=> "cannot write"

Sometimes we don't know about status of the permission, but we just want to change the permission,i.e, just to toggle it to its opposite. We can accomplish this by using XOR operator.

p user.write? ? "can write" : "cannot write"
#=> "cannot write"
user.permission ^= WRITE
p user.write? ? "can write" : "cannot write"
#=> "can write"

But if we do this operation again

user.permission ^= WRITE
p user.write? ? "can write" : "cannot write"
#=> "cannot write"

It changes back again. so it toggles back and forth.

We will look at another application of bitwise operator in encrytion and decryption.

Encrytion and Decryption

we will show encryption and decryption of some letters Suppose we have a predetermined way of swapping the bit of a character.

For example: 0-5, 1-2, 3-7, 4-6

MASK0 = 0x01
MASK1 = 0x02
MASK2 = 0x04
MASK3 = 0x08
MASK4 = 0x10
MASK5 = 0x20
MASK6 = 0x40
MASK7 = 0x80

def crypt(ch)
  b0 = (ch & MASK5) >> 5
  b1 = (ch & MASK2) >> 1
  b2 = (ch & MASK1) << 1
  b3 = (ch & MASK7) >> 4
  b4 = (ch & MASK6) >> 2
  b5 = (ch & MASK0) << 5
  b6 = (ch & MASK4) << 2
  b7 = (ch & MASK3) << 4

  encrypted = b0|b1|b2|b3|b4|b5|b6|b7
  [encrypted].pack("U*")[0]
end

original = 'box'

encrypted = original.scan(/./).map { |c| crypt(c.unpack("U*")[0]) }.join
p encrypted
#=> "\u0015·Ñ"

decrypted = encrypted.scan(/./).map { |c| crypt(c.unpack("U*")[0]) }.join
p decrypted
#=> "box"

I hope you enjoy reading and get something. With some creativity, bitwise operation can be quite intriguing. If you have any questions please comment. I' d love to hear what you say about this.