- let naive_highest_bit x =
- assert (x < 256);
- let rec loop i =
- if i = 0 then 1 else if x lsr i = 1 then 1 lsl i else loop (i-1)
- in
- loop 7
-
- let hbit = Array.init 256 naive_highest_bit
- (*
- external clz : int -> int = "caml_clz" "noalloc"
- external leading_bit : int -> int = "caml_leading_bit" "noalloc"
- *)
- let highest_bit x =
- try
- let n = (x) lsr 24 in
- if n != 0 then hbit.(n) lsl 24
- else let n = (x) lsr 16 in if n != 0 then hbit.(n) lsl 16
- else let n = (x) lsr 8 in if n != 0 then hbit.(n) lsl 8
- else hbit.(x)
- with
- _ -> raise (Invalid_argument ("highest_bit " ^ (string_of_int x)))
-
- let highest_bit64 x =
- let n = x lsr 32 in if n != 0 then highest_bit n lsl 32
- else highest_bit x
-
- let branching_bit p0 p1 = highest_bit64 (p0 lxor p1)
+ external int_of_bool : bool -> int = "%identity"
+
+ let hb32 v0 =
+ let v = v0 lor (v0 lsr 1) in
+ let v = v lor (v lsr 2) in
+ let v = v lor (v lsr 4) in
+ let v = v lor (v lsr 8) in
+ let v = v lor (v lsr 16) in
+ ((v + 1) lsr 1) + (int_of_bool (v0 == 0))
+
+ let hb64 v0 =
+ let v = v0 lor (v0 lsr 1) in
+ let v = v lor (v lsr 2) in
+ let v = v lor (v lsr 4) in
+ let v = v lor (v lsr 8) in
+ let v = v lor (v lsr 16) in
+ let v = v lor (v lsr 32) in
+ ((v + 1) lsr 1) + (int_of_bool (v0 == 0))
+
+
+ let branching_bit p0 p1 = hb64 (p0 lxor p1)