DEV Community

loading...

Ruby Bit Manipulation

delbetu profile image M Bellucci ・3 min read

Some days ago as part of a recruiting process, I faced a code-challenge on Devskiller.
One of the challenges requires using an integer to represents the Groups that a User belongs to.
For example 101 means that the user belongs to Group0 and Group2 but not to Group1.

7 years ago I probably would pass this challenge but since this challenge is assessing the most underused feature of the language for a web-developer and it is time-constrained, I didn't pass :'( .

So if you want to succeed on this kind of challenges make sure you can unerstand this code:

# operators Description
# &   AND
# |   OR
# ^   XOR
# ~   NOT
# <<  left shift
# >>  right shift

# Calculating the binary version of the number (.to_s(2) doesn't work for negated values ~x)
def binary_string(number)
  31.downto(0).reduce('') {|result, index| result += number[index].to_s }
end
alias :bs :binary_string

# returns the value of the bit at the position index
# index 0 is the last bit
def get_bit(number, index)
  # since Ruby is awesome this also could be implemented as number[index]

  ith_one = 1 << index       # 0000000000100
  ith_bit = number & ith_one # 1101101101X01 & 0000000000100 => 0000000000X00
  ith_bit >> index           # 000000000000X
end

# puts a 1 in the index position of number starting from right to left
# doesn't change its parameter instead returns a new number
# index 0 is the less significant bit
def set_bit(number, index)
  ith_one = 1 << index # 00000000010000000
  number | ith_one
end

# puts a 0 in the index position of number starting on 0 from right to left
# index 0 is the less significant bit
def clear_bit(number, index)
  mask = ~(1 << index)
  number & mask
end

# param value must be 0 or 1
def update_bit(number, index, value)
  mask = ~(1 << index)
  (number & mask) | (value << i)
end

x = 5
zeroes = 0 # 000000000000000000000000000000
ones = ~0 # 111111111111111111111111111111

########################## XOR ##########################
p "#{ x ^ zeroes } == #{ x }"
p "#{ bs(x ^ ones) } == #{bs(~x)}" # using bs because to_s prints a negative binary
p "#{ x ^ x } == #{0}"

########################## OR ##########################
p "#{ x | zeroes } == #{ x }"
p "#{ x | ones } == #{ones}"
p "#{ x | x } == #{x}"

########################## AND ##########################
p "#{ x & zeroes } == #{ zeroes }"
p "#{ x & ones } == #{x}"
p "#{ x & x } == #{x}"

# Convert into array
0b01010101.to_s(2).split('')
# => ["1", "0", "1", "0", "1", "0", "1"]


################################## Sample Problem #################################################
# Insertion:
#   You are given two 32-bit numbers, N and M, and two bit positions, i and j.
#   Write a method to insert M into N such that M starts at bit j and ends at bit i.
#   You can assume that the bits j through i have enough space to fit all of M.
#
#   That is, if M = 10011, you can assume that there are at least 5 bits between j and i.
#   You would not, for example, have j = 3 and i = 2, because M could not fully fit between bit 3 and bit 2.
#
# EXAMPLE
# Input:
#   N = 10000000000, M = 10011, i = 2, j = 6
# Output:
#   N = 10001001100
###################################################################################################

def merge_bits_at(n, m, i, j)
  # m = M4 M3 M2 M1 M0
  # m1 = 0  0  M3 M2 M1 M0 0 0
  # n = N7 N6 N5 N4 N3 N2 N1 N0
  # n1 = N7 N6 0  0  0  0  N1 N0
  # n1 | m1 = N7 N6 M3  M2  M1  M0  N1 N0

  m1 = ( m << i )      # 0  0  M3 M2 M1 M0 0 0

  ones = ~0
  x1 = ones << i      # 1 1 1 1 1 1 0 0
  x2 = ~( ones << j ) # 0 0 1 1 1 1 1 1
  mask = x1 & x2      # 0 0 1 1 1 1 0 0
  mask = ~mask        # 1 1 0 0 0 0 1 1

  n1 = n & mask       # N7 N6 0  0  0  0  N1 N0

  m1 | n1
end


n, m, i, j = 0b10000000, 0b10011, 2, 6
puts "N = #{bs(n)}"
puts "M = #{bs(m)}"
puts "i = #{i}, j = #{j}"
puts 'Calling merge_bits_at(10000000, 10011, 2, 6)'
merged_bits = merge_bits_at(n, m, i, j)
puts "#{ bs(merged_bits) } should be 11001100"


#### Using string representation ####
( "101".to_i(2) & "110".to_i(2) ).to_s(2)

Discussion (0)

pic
Editor guide