[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2004-05-15 (02:53) |
From: | Yaron Minsky <yminsky@g...> |
Subject: | Re: [Caml-list] Counting bits in a big_int |
Here's the fastest bitcounter I've been able to come up with. It's about an order of magnitude faster than just counting bit by bit. let ( *! ) = mult_big_int let ( +! ) = add_big_int let ( -! ) = sub_big_int let ( %! ) = mod_big_int let ( /! ) = div_big_int let ( **! ) = power_big_int_positive_int let ( <>! ) x y = not (eq_big_int x y) let ( =! ) = eq_big_int let ( <! ) = lt_big_int let ( >! ) = gt_big_int let ( <=! ) = le_big_int let ( >=! ) = ge_big_int let nbits_slow x = let rec loop i two_to_i = if two_to_i >! x then i else loop (succ i) (two *! two_to_i) in if x =! zero then 1 else loop 1 two let nbits x = let nwords = num_digits_big_int x in let wsize = Sys.word_size in let lowbits = (nwords - 1) * wsize in let lastword = x /! two **! lowbits in nbits_slow lastword + (nwords - 1) * wsize On Thu, 13 May 2004 14:41:01 +0200, Jean-Christophe Filliatre <jean-christophe.filliatre@lri.fr> wrote: > > > Yaron Minsky writes: > > What I'm actually interested in is finding the index of the rightmost > > set bit. So, for the int: > > 1000110, I'd want the answer to be 7, not 3. > > Ok; then Michael's suggestion should work, as follows: > > ====================================================================== > let count_bits b = > let rec loop i two_to_i = (* inv 2^(i-1) <= b *) > if gt_big_int two_to_i b then i > else loop (succ i) (mult_int_big_int 2 two_to_i) > in > if eq_big_int b zero_big_int then 1 else loop 1 (big_int_of_int 2) > ====================================================================== > > -- > Jean-Christophe > > ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners