Re: [Caml-list] Counting bits in a big_int

[Yaron Minsky <yminsky@gmail.com>]

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