diffTrie.ml

let most_significant_bit =
  (-1) lxor ((-1) lsr 1)

let bprint_int_binary buf n =
  Buffer.add_string buf "0b";
  let rec loop started bit n =
    if bit = 0 then begin
      if not started then Buffer.add_char buf '0'
    end
    else
      let b = n land bit in
      if b = 0 then begin
        if started then Buffer.add_char buf '0';
        loop started (bit lsr 1) n
      end
      else begin
        Buffer.add_char buf '1';
        loop true (bit lsr 1) n
      end in
  loop false most_significant_bit n

let print_int_binary n =
  print_string "0b";
  let rec loop started bit n =
    if bit = 0 then
      begin if not started then print_char '0' end
    else
      let b = n land bit in
      if b = 0 then begin
        if started then print_char '0';
        loop started (bit lsr 1) n
      end
      else begin
        print_char '1';
        loop true (bit lsr 1) n
      end in
  loop false most_significant_bit n

let test low high =
  let buf = Buffer.create 16 in
  for i = low to high do
    Buffer.clear buf;
    bprint_int_binary buf i;
    let str = Buffer.contents buf in
    begin
      try assert (int_of_string str = i)
      with Failure _ ->
        Printf.printf "bad: %d %s\n" i str; assert false
    end;
  done

let _ = begin
  test (-100000) 1000000;
  test min_int (min_int + 10000);
  test (max_int - 10000) max_int;
end