Home     About     Download     Resources     Contact us

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Browse thread
[Caml-list] Counting bits in a big_int
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2004-05-15 (02:53) From: Yaron Minsky 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

```