This is a
solution to
problem 16 on the
hard interview questions node. If you have not read the
question, the
following will make no
sense to you:
Below is a piece of code (in SML) that will do the trick. It's a function from int to bool list.
fun odd n = (n mod 2) = 1
fun f 0 false false acc = acc
| f 0 true false acc = false::acc
| f 0 evenp true acc = f 0 (not evenp) (not evenp) (true::acc)
| f n false carry acc = f (n div 2) true (odd(n) orelse carry) ((not(odd(n) = carry))::acc)
| f n true carry acc = f (n div 2) false (odd(n) andalso carry) ((not(odd(n) = carry))::acc)
fun minus2 n = f' n true false []
Sample output:
- minus2 5;
val it = [true,false,true] : bool list
- minus2 6;
val it = [true,true,false,true,false] : bool list