# Bit twiddling

Luke Gorrie luke@REDACTED
Thu Mar 31 20:04:32 CEST 2005

```"Joel Reymont" <joelr1@REDACTED> writes:

> I'm looking to figure out the highest and lowest bit set in an integer as
> well as count the number of bits set.

If it needs to be fast then be sure to see what mathematician
assembler hackers have to say!

hackmem
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html

Hacker's Delight
http://www.hackersdelight.org/

Count number of On bits in an integer
http://www-db.stanford.edu/~manku/bitcount/bitcount.html

Highest bit set is floor(log2(N)) if you figure out the floating
point, though Erlang doesn't have a log2 BIF. Tony Rogvall has a very
interesting "how many bits is this integer" function that makes the
runtime system do the real work in jungerl/lib/ssh/src/ssh_bits.erl:

isize(N) when N > 0 ->
case term_to_binary(N) of
<<?VERSION_MAGIC, ?SMALL_INTEGER_EXT, X>> ->
isize_byte(X);
<<?VERSION_MAGIC, ?INTEGER_EXT, X3,X2,X1,X0>> ->
isize_bytes([X3,X2,X1,X0]);
<<?VERSION_MAGIC, ?SMALL_BIG_EXT, S:8/big-unsigned-integer, 0,
Ds:S/binary>> ->
K = S - 1,
<<_:K/binary, Top>> = Ds,
isize_byte(Top)+K*8;
<<?VERSION_MAGIC, ?LARGE_BIG_EXT, S:32/big-unsigned-integer, 0,
Ds:S/binary>> ->
K = S - 1,
<<_:K/binary, Top>> = Ds,
isize_byte(Top)+K*8
end;
isize(0) -> 0.

i.e. encode the number in the binary Erlang external term format and
then pull that apart to see the length header :-)

```