Smalltalk Squeak 4.x flavour, 570 bytes
First Try: define an operator in Object to evaluate any Object:
`x^self cull:x
We refine the eval message in Character to get the value:
`x^value
Then define bit ops with binary messages in Character:
&x^self class value:(x`1bitAnd:value)
|x^self class value:(x`1bitOr:value)
/x^self class value:((x`1bitXor:value)bitXor:$0`1)
/ is xor operator, because it looks like the truth table
01
10
Then add two more messages in Character for repeating in a String and concatanating
*n^String new:n withAll:self
,s^(String with:self),s
Or my favourite hack to gain 2 chars:
,s^'',(self`1+#[0]),s
Now create a new notation for accessing Array elements because (x at:i)
costs two much. The operator @ could be used for at: and <@ would then means that it starts from the right (0-based) because our bit-Strings are big-endian.
That would be
Object subclass:#At instanceVariableNames:'a i'classVariableNames:''poolDictionaries:''category:''
In At, we would define two methods for initializing and accessing:
a:b i:j a:=b.i:=j
`x^(a atWrap:0-i)`x
Since this costs to much, we will replace this nice thing by using Association. So we define the accessor message in String (or in SequenceableCollection)
<@i^self->i
And just define ` to retrieve the At value in Association:
`x^(key atWrap:0-value)`x
Now we are ready to implement the operations in String first, strip the $0 left:
\~c |x|(x:=self)size>1or:[^x].c=(x at:1)or:[^x].^x allButFirst\~c
Then the awfull bit sum +| (just a naive xor with carry)
+|y|x z c m n|(m:=(x:=self)size)<=(n:=y size)or:[^y+|x].c:=$0.z:=''.0to:m-1do:[:i|z:=c/(x<@i)/(y<@i),z.c:=c|(y<@i)&(x<@i)|(c&(y<@i))].m to:n-1do:[:i|z:=c/(y<@i),z.c:=c&(y<@i)].c=$0or:[^c,z].^z
Then the bit multiply *| :
*|y|x z|x:=self.z:='0'.0to:y size-1do:[:i|$0/(y<@i)=$0or:[z:=z+|x].x:=x,$0].^z
Then the bit subtraction -| is using two complement. Result is truncated to receiver length, so it must not be negative:
-|y|n x|n:=(x:=self\~$0)size.^(x+|'1'+|($1*n,(y collect:[:c|c/$1])))last:n
Then a test <| for bit less than:
<|y|m n|m:=self size.n:=y size.^m<n or:[m=n and:[self<y]]
Then the bit division /| (by subtraction) - this will also raise a zero divide exception when appropriate:
/|z| x y q t n|y:=z\~$0.x:=self\~$0.y='0'and:[1/0].n:=0max:x size-y size.q:=''.[n>=0]whileTrue:[t:=y,($0*n).n:=n-1.q:=q,(x<|t ifTrue:[$0]ifFalse:[x:=x-|t\~$0.$1])].^q
And finally the operation encoding - we reuse <@ to access right to left 0-based:
y:y o:o|x|x:=self.^({[x/|y].[x*|y].[x-|y].[x+|y]}<@o)`1\~$0
The small test suite:
self assert: ('01010' y:'10101' o:0) = '11111'.
self assert:('11110' y:'01010' o:1) = '10100'.
self assert:('0010' y:'1000' o:2) = '10000'.
self assert:('1011010' y:'0010001' o:3) = '101'.
The longer test suite:
| n |
n := 100.
0 to: n do: [:i|0 to:n do:[:j |
self assert: (i printStringBase:2)+|(j printStringBase:2)\~$0=(i+j printStringBase:2)]].
0 to: n do: [:i|0 to:n do:[:j |
self assert: (i printStringBase:2)*|(j printStringBase:2)\~$0=(i*j printStringBase:2)]].
0 to: n do: [:i|0 to:i do:[:j |
self assert: (i printStringBase:2)-|(j printStringBase:2)\~$0=(i-j printStringBase:2)]].
0 to: n do: [:i|1 to:n do:[:j |
self assert: (i printStringBase:2)/|(j printStringBase:2)\~$0=(i//j printStringBase:2)]].
And the score is given by:
{Object>>#`. SequenceableCollection>>#<@. Association>>#`}
, ({#`. #*. #&. #|. #/. #,} collect:[:selector | Character>>selector])
, ({#\~. #+|. #-|. #*|. #/|. #<|. #y:o:} collect:[:selector | String>>selector])
detectSum: [:method | method getSource size].
Which is 921 chars...
We can do much better if we use Boolean instead of Integer. They can be easily transformed in character:
Implement in True:
c^$1
And in False:
c^$0
Now transform a binary Character in Boolean, implement in Character:
b^self=$1
Now logical operations are expressed much simply in Character:
&x^(x b&self b)c
|x^(x b|self b)c
/x^(x b xor:self b)c
Plus the two operations to repeat and concatenate:
*n^String new:n withAll:self
,s^self*1,s
Now, the message size is long, let's create a shorter binary message in String:
\n^self size-n
We shorten the message for stripping leading chars in String:
~c|x|(x:=self)\1<1or:[c~=(x at:1)or:[^(x last:x\1)~c]]
Now we'd better implement binary >= rather than < for division, let's call it >~ in String:
>~y^self\0>(y\0)or:[self\0=(y\0)and:[self>=y]]
Now back to the operations, we will call them + - * / even if we have to override existing methods in String (they are presumably not used):
y:y o:o|x|x:=self.^({[x/y].[x*y].[x-y].[x+y]}<@o)value~$0
+y|x z c m n|(m:=(x:=self)\1)<=(n:=y\1)or:[^y+x].c:=$0.z:=''.0to:m do:[:i|z:=c/(x<@i)/(y<@i),z.c:=c|(y<@i)&(x<@i)|(c&(y<@i))].m+1to:n do:[:i|z:=c/(y<@i),z.c:=c&(y<@i)].c=$0or:[^c,z].^z
-y|n x|n:=(x:=self~$0)\0.^(x+'1'+($1*n,(y collect:[:c|c/$1])))last:n
*y|z|z:='0'.0to:y\1do:[:i|(y<@i)b and:[z:=self,($0*i)+z]].^z
/z| x y q t|y:=z~$0.x:=self~$0.y='0'and:[1/0].q:=''.(0max:x\0-(y\0))to:0by:-1do:[:n|t:=y,($0*n).q:=q,(x>~t and:[x:=x-t~$0.$1b])c].^q
The score is now
methods := {SequenceableCollection>>#<@. True>>#c. False>>#c}
, ({#b. #*. #&. #|. #/. #,} collect:[:selector | Character>>selector])
, ({#\. #~. #+. #-. #*. #/. #>~. #y:o:} collect:[:selector | String>>selector]).
methods detectSum: [:method | method getSource size].
That is 742 chars
Another snippet to browse our code alltogether:
methods do: [:e | e methodClass organization classify: e selector under: '*CodeGolfBinaryArithmetic'].
SystemNavigation default
browseMessageList:
(methods collect: [:e | MethodReference class: e methodClass selector: e selector])
name: 'CodeGolfBinaryArithmetic'
We can further reduce the division to repeated subtraction (slower):
/z|x y|y:=z~$0.x:=self~$0.y='0'and:[1/0].x>~y or:[^'0'].^x-y/y+'1'
We can also omit 1/0 for ZeroDivide exception, anyway the result will be infinite on a computer with infinite memory after an infinite time:
/z|x y|y:=z~$0.x:=self~$0.x>~y or:[^'0'].^x-y/y+'1'
We can also reduce addition to a recursive form:
+y|x|(x:=self)\0>0or:[^y].y\0>0or:[^x].^x<@0&(y<@0)*1+(x first:x\1)+(y first:y\1),(x<@0/(y<@0))
And we now are at 570 chars... Not bad for Smalltalk.
2I think you should rethink the "subtract 50" thing. I can see it being implemented in much less characters than that. Perhaps "10% up to 50" would be a better choice. – Polynomial – 2012-06-12T07:42:01.533
7When you say "binary numbers" you don't actually mean "binary numbers", do you? If you mean "strings containing only characters '0' and '1'" then say that. – Peter Taylor – 2012-06-12T08:19:36.123
2The binary numbers will be the same length, but can we assume that there will be no overflow, so the result is the same length? (Is "n1=11111, n2=11111, o=0" possible?) – schnaader – 2012-06-12T11:52:57.697
3How do we represent negative numbers (i.e. what is the basis 2^n/how do we write -1)? – Howard – 2012-06-12T12:53:45.953
1@schnaader The third example (multiply) shows otherwise. – Howard – 2012-06-12T12:54:53.223
Thank you for all your input. I have fixed the question, or at least I think I did. Keep it coming! – beary605 – 2012-06-12T19:01:28.530
@Howard: Two's Complement – beary605 – 2012-06-12T19:02:07.903
@beary605 In two's complement the most significant bit being set indicates a negative number - what is the word size we're working with here? – Gareth – 2012-06-12T20:13:33.587
Do we need to truncate leading zeros? – Keith Randall – 2012-06-12T20:16:56.690
@Gareth: Let's say a reasonable amount. Kieth Randall: Yes. – beary605 – 2012-06-12T23:04:01.717
@beary605 That's not very helpful, unfortunately. Let me ask it another way: if the input is
n1=0000, n2=0001, o=1
should the output be11111111
,1111111111111111
, or something else? – Gareth – 2012-06-13T07:13:22.717I see what you mean now. In that case, truncate the 1s to the length(n1)+length(n2). – beary605 – 2012-06-13T07:25:15.163
@beary605 Do we use this word size also for the input? That would mean that input numbers are always non-negative? – Howard – 2012-06-13T08:33:49.077
No, the input will be a random number of digits. – beary605 – 2012-06-13T16:10:05.457
1Truncating doesn't help in identifying negative numbers. I still think we need to know whether they're 8 digits long, 16, 32, 64 or something else. And btw.: My computer always calculates in binary. P.S.: The operator should be given as 0, 01, 10 or 11 respectively, just for aesthetic reasons. – user unknown – 2012-06-14T14:54:16.403
A negative number has a turned-on bit in the front; both inputs are the same length. To me, that should be sufficient enough information. – beary605 – 2012-06-14T23:49:23.283
I've never seen a datatype with 5 bits like in the examples 1 and 2. In example 3 you multiply 2 * -8, according to your last explanation. -16 is the decimal result, but it doesn't fit a 4 bit Int. Now you show a 5-bit Int as result, but in a 5 bit data type 1000 wouldn't be -8, but 8. So we have to assume an autowidening datatype? I'm fine with that, but it isn't evident from the examples alone. And, something else: You have to annotate an answer with @Name to make the system inform somebody, that you answered his comment. Tab completion works thereby. – user unknown – 2012-06-17T07:46:09.030