by Aaron Patterson
Write a class that can represent a signed or unsigned number with an arbitrary number of bits. This class should support all bitwise operations ( & ^ ~ | ), basic math operations ( + - / * ), and comparison operators. It would behave like an integer in C (except with arbitrary length!), so an unsigned int 0xFFFFFFFF + 1 would equal 0x00000000.
One edge case is what to do in an overflow case ( see the first irb session number 2 ). Another is how to handle numbers that are wider than the specified number of bits. I'm not really sure how to handle that part, but what I do is just take the last N number of bits. So if 0xFFEE was passed in to my 8 bit vector, I would just take 0xEE.
Example irb sessions
Here is an example of using an 8 bit unsigned int with an initial value of 0xFF:
irb(main):001:0> n = UnsignedFixedWidthInt.new(0xFF, 8)
=> 255
irb(main):002:0> n += 2
=> 1
irb(main):003:0> n = n << 1
=> 2
irb(main):004:0> n = n >> 1
=> 1
irb(main):005:0> ~n
=> 254
irb(main):006:0> n += 12
=> 13
irb(main):007:0> n = n & 0x0E
=> 12
irb(main):008:0>
Now an example of an 8 bit signed int with an initial value of 0x01:
irb(main):001:0> n = SignedFixedWidthInt.new(0x01, 8)
=> 1
irb(main):002:0> n = n << 7
=> -128
irb(main):003:0> n -= 1
=> 127
irb(main):004:0> n = n >> 6
=> 1
irb(main):005:0> n -= 2
=> -1
irb(main):006:0> n = n ^ 0xF3
=> 12
irb(main):007:0> n = n | 0x01
=> 13
irb(main):008:0>
Here is an example of handling numbers that are too wide:
irb(main):001:0> n = UnsignedFixedWidthInt.new(0x0, 8)
=> 0
irb(main):002:0> n += 0xFFEE
=> 238
irb(main):003:0>
Quiz Summary
There was quite a bit of confusion over what we were after in the quiz. Ironically, I think that's all my fault for giving the author's simple quiz the name "C-Style Ints." Things are always complicated when you drag C into them and some solvers bent over backwards to dissect C's behavior. Luckily, that lead to some cool solutions for us to examine.
One way to tackle this problem is to rebuild all the needed math operations. That leads to quite a bit of code like this excerpt from Hank Lords's submission:
class UFWI
include Comparable
attr_reader :width
def initialize(int=0, width=8)
if block_given?
@width = int
@bits = Array.new(@width) {|index| Bit.new(yield( index)) }
else
@width = width
@bits = Array.new(@width) {|bit| Bit.new(int.to_i >> bit) }
end
end
def to_i
@bits.reverse.inject(0) {|num, bit| (num << 1) + bit.to_i}
end
alias :to_int :to_i
def coerce(*args)
to_int.coerce(*args)
end
# ...
def &(cint)
a = self.class.new(cint, width)
self.class.new(width) {|bit| @bits[bit] & a[bit] }
end
# ...
def / (cint)
# Binary euclidian division
b = self.class.new(cint, width)
raise DivisionByZero if b == 0
b0 = self.class.new(1, width)
width.times {
break if self < b0*b
b0 <<= 1
}
a0 = b0 >> 1
while b0 - a0 > 1 do
c = (a0 >> 1) + (b0 >> 1)
if c * b <= self
a0 = c
else
b0 = c
end
end
a0
end
end
# ...
Obviously, I'm showing only a couple of operations here and you can see that this code uses a Bit class (not shown). Hank did the work by teaching Ruby to work with ordinary bits and then building the needed number operations on top of that framework. You can see the numbers being constructed as an Array of Bits in initialize(), either from a provided integer or using a block to generate the bits iteratively.
The next couple of methods allow these numbers to be used in math operations with Ruby's native numbers. The first step is to provide a conversion for this UFWI to a normal Ruby Integer. Once we have that, a coerce() method is defined which Ruby uses to resolve numerical operations with custom objects. This version just converts our UFWI to a normal Integer, then delegates the call to the built-in coerce().
Finally, I've left in two example operations. You can see that Hank resolves these operations using handle-rolled bit math. In some cases (like &()), this can be done trivially, but others (like /()) get a little complicated. Hank did a top notch job creating all the needed operations. I've just left them out here to keep this summary reasonably small.
Hank's solution is solid, but it took a lot of work to create. What we really want to do is to get Ruby to do as much of that work for us as humanly possible. Many quiz solvers found ways to do this. Here's a lovely version by Boris Prinz:
def initialize(value, bits)
raise ArgumentError.new('number of bits must be > 0') if bits <= 0
@bits = bits
@value = value % 2**@bits
end
# operators returning a new FixedWidthInt
%w{& ^ | << >> + - * / +@ -@ ~@}.each do |operator|
define_method operator do |*other|
self.class.new(@value.send(operator, *other), @bits)
end
end
# methods forwarded to @value
%w{== < > <=> inspect to_s to_i to_int}.each do |meth|
define_method meth do |*other|
@value.send(meth, *other)
end
end
def coerce(other)
Integer == other ? [other, @value] : [Float(other), Float(@value)]
end
end
class SignedFixedWidthInt < UnsignedFixedWidthInt
def initialize(value, bits)
super(value, bits)
# value is negative if MSB is set:
@value -= 2**@bits if @value[@bits - 1] == 1
end
end
With this example, the majority of the work is done in the initialize() methods of UnsignedFixedWidthInt and SignedFixedWidthInt. They simply store the bit width and numerical value for future use. It the passed number is larger than the indicated width, it is truncated at this time. The SignedFixedWidthInt adds a check for the sign bit and negates the number when set.
Next Boris uses a little metaprogramming to quickly define a bunch of similar math operations. These methods just delegate to the proper math method on the actual numerical object and hand the results back to the class constructor. This insures that any result is truncated, if needed.
Boris also uses the metaprogramming trick to define a handful of methods that return native Ruby types. The end result is 20 method definitions in just a few lines of code. Very nice results.
Finally, Boris does add the coerce() method, similar to Hank's code, so the new integer types can be used in math operation with normal Ruby numerical types.
My thanks to all who took a stab at this quiz. Sorry my naming of it made it seem more involved than intended. Have a look at Daniel Martin's thorough C conversion for a great example of that solution path.
Tomorrow we will try our luck with a panagram problem... (I had to look that word up.)
