[Haskell-cafe] bitSize

Daniel Fischer daniel.is.fischer at googlemail.com
Thu Aug 25 20:38:12 CEST 2011

```On Thursday 25 August 2011, 19:57:37, Andrew Coppin wrote:
> Quoting the Haddock documentation for Data.Bits.bitSize:
>
> "Return the number of bits in the type of the argument. The actual value
> of the argument is ignored. The function bitSize is undefined for types
> that do not have a fixed bitsize, like Integer."
>
> Does anybody else think it would be *far* more useful if bitSize applied
> to an Integer would tell you how many bits that particular Integer is
> using? Especially given that it can vary?

I'm not sure about that.

>
> Is there a way to actually determine how many bits are in an Integer?
>

Sure. The exact method depends on what result you want and which integer-*
package you use.

You have to handle 0 and negative n first (how to treat negative n is not
obvious).

Then, for n > 0, f you want 'index of highest set bit' (+1),

(1 +) integerLogBase 2 n

does the trick (integerLogBase is available from GHC.Float, as of 7.2.1,
it's decently fast).

If you want 'WORD_SIZE_IN_BITS * number of words used', you could use the
above and round up to the next multiple of WORD_SIZE_IN_BITS, or you could
make use of the representation of Integers; with integer-gmp,

data Integer
= S# Int#
| J# Int# ByteArray#

so

usedWords (S# _) = 1
usedWords (J# s# _) = I# s#

(nota bene, I don't think it's positively guaranteed that the highest order
word in a (J# _ _) is nonzero, so usedWords could give a higher answer than
rounding up from integerLogBase 2 n).

```

More information about the Haskell-Cafe mailing list