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)
Top comments (0)